CS/ECE/ISyE 524 Homework 2: Linear programs

    1. [2 points] Warmup. Model the following problem in JuMP.


maximize
6x1
2x2 + 3x3
(1)
x1;x2;x3




subject to:
2x1
x2
x3 + 2
(2)

0   xj   3;
j 2 f1; 2; 3g
(3)

        a) Given the choice of the solvers Clp, ECOS, and SCS, which one would you choose? Why?

        b) Solve the problem using your selected solver. Print the termination status to check whether you have indeed obtained the optimal solution.

        b) What is the optimal objective value? What is the optimal solution for the variables x1 and x2?

        c) Can you change one of the problem parameters to make the problem infeasible? Solve the new problem in JuMP and print the termination status to demonstrate that the problem is infeasible.


    2. [2 points] Stigler’s diet. True story! In 1945, American economist (and future Nobel laureate) George Stigler published a paper investigating the composition of an optimal diet; minimizing total cost while meeting the recommended daily allowance (RDA) of several nutrients. To answer this question, Stigler tabulated a list of 77 foods and their nutrient content for 9 nutrients: calories, protein, calcium, iron, vitamin A, thiamine, ribo avin, niacin, and ascorbic acid. Here is what the rst few rows and columns of his table looked like:


Calories (1000)
Protein (g)
Calcium (g)
Iron (mg)
. . .






Wheat Flour (Enriched)
44.7
1411
2
365
. . .






Macaroni
11.6
418
0.7
54
. . .






Wheat Cereal (Enriched)
11.8
377
14.4
175
. . .








.
.
.
.
.
.
.

.
.
.
.
.


.
.
.
.
.
.




To make calculations easier, Stigler normalized his data so each row shows the nutrients contained in $1’s worth of the given food item. Back then, $1 could buy you quite a lot!

When Stigler posed his diet problem, the simplex method had not yet been invented. In his paper, he wrote: \...the procedure is experimental because there does not appear to be any direct method of nding the minimum of a linear function subject to linear conditions." Nevertheless, through a combination of what he called \trial and error, mathematical insight, and agility", he eventually arrived at a solution: a diet costing only $39.93 per year. Though he confessed: \There is no reason to believe that the cheapest combination was found, for only a handful of the [many] possible combinations of commodities were examined."

In this exercise, you will help Stigler formulate and solve the diet problem as a linear program (LP).

    a) Formulate the optimization problem:

What are the decision variables in this problem?

What is the objective of this optimization problem?

What are the constraints of the optimization problem?

Answer both with an explanation in words and with the mathematical model.

1 of ??
CS/ECE/ISyE 524    Introduction to Optimization    L. Roald,    Spring 2022


        b) Implement the optimization problem in Julia. To get you started, Stigler’s original data is provided in stigler.csv, and the IJulia notebook stigler.ipynb imports the data and puts it into a convenient matrix format.

        c) Analyze your result. Did you nd the optimal solution? How does your cheapest diet compare in annual cost to Stigler’s? What foods make up your optimal diet?

        d) Suppose we wanted to nd the cheapest diet that was also vegetarian. Implement the new problem in Julia and nd the optimal solution. Is this solution cheaper or more expensive than the non-vegetarian solution? Is this as expected?


    3. [2 points] Standard form with equality constraints. Rather than using the standard LP form we saw in class, some prefer using a form where all variables are nonnegative, all constraints are equality constraints, and the cost function is a minimization. So a general LP would look like:


minimize
cTx





subject to:
Ax = b


(4)



x  0




Consider the following LP:







maximize
3z1
z2





z1;z2;z3;z4







subject to:
z1
+  6z2
z3
+
z4

3


7z2

+
z4
=
5



z3
+
z4

2
1   z2    5;
1   z3    5;
2   z4    2


    a) Transform the above LP into the equality-constrained standard form of (??). What are A, b, c, and x? Be sure to explain how the decision variables of your transformed LP relate to those of the original LP.

    b) Solve both versions of the LP using JuMP and show that you can recover the optimal z and objective value by solving your transformed version of the LP.

























2 of ??