Suppose the witch Agnesi also goes into the business of selling food, meat sandwiches and meat pies. Each day she is able to acquire 50 oz of mystery meat (don’t ask) and 30 oz of flour. The sandwiches take 8 oz of meat and 2 oz of flour, the pies take 3oz of meat and 5 oz of flour. She is able to sell the sandwiches for 10 gold pieces and the pies for 7 gold pieces.
Agnesi wishes to be able to produce sandwiches and pies in a way to maximize her income. Set up this problem as a linear optimization problem and solve.
After the local barber has been arrested, demand for Agnesi’s pies sees an increase, and she is able to now sell them for 12 gold pieces. Now what production level maximizes her income?
Come up with three realistic optimization problems which are best modeled by an integer optimization problem. You do not need to work out all the details or solve the problems.
Consider an integer optimization maximization problem whose relaxation achieves an optimal solution. Which of the following are true about the integer optimization problem?
Let \(x_1\) be the number of sandwiches sold, and consider the current optimal \(x_1\) from the relaxation. Which two of the following potential additional constraints would force the value of \(x_1\) to be an integer, while remaining as close to the optimal solution of the relaxation as possible.
Consider the additional constraint \(x_2\leq 4\text{.}\) Solve this maximization problem. Why do we no longer need to adjust \(x_1\text{?}\) Are we guaranteed that this solution is optimal?
We consider the constraint \(x_2\geq 5\) instead. Solve this maximization problem. Even though the solution is not integral, why do we no longer need to pursue the case where \(x_1\leq 4, x_2\geq 5\text{?}\)
We return to the other possible initial constraint for \(x_1\text{,}\)\(x_1\geq 5\text{.}\) Solve this maximization problem. What are the possible constraints we could now add for \(x_2\text{?}\)
We consider now the constraint \(x_2\leq 3\text{.}\) Solve this maximization problem. How does this solution compare to the previous integral solution we found?
Instead we now consider the constraint \(x_2\geq 4\text{.}\) Solve this maximization problem. Why do we no longer need to consider the case where \(x_2\geq 4\text{?}\)
For some \(x_i^*\) in the optimal solution found in the previous step, define two sub problems, one with additional constraint \(x_i\leq \lfloor x_i^*\rfloor\) and \(x_i\geq \lceil x_i^*\rceil\text{.}\)
We start at Node 0, and identify the two subproblems. Next, we examine the subproblem where \(x_1\leq 4\) in Node 1, and again identify two subproblems. Examining Node 2 causes us to stop and return because the solution was integral. When examining Node 3, we also stop and return even though the solution is not integral, since the optimal solution for that subproblem was already less than the solution found in Node 1, and any further exploration would lead to a lower value still.
Next, we return to the starting node and to the other initial subproblem in Node 4, were \(x\geq 5\text{.}\) When we split into the two subproblems, \(x_2\leq 3\) gives an integral solution in Node 5, and the constraint \(x_2\geq 6\) gives an infeasible problem.
As the demand for meat pies skyrockets, Agnesi is now able to acquire 40 oz of floor a day, but now uses 10 oz of floor per meat pie to thicken the gravy. She is able to sell these for 40 gp each. Use the Branch and Bound Algorithm Definition 8.1.5 to find her new optimal production level.
