Starting from:
$30
CS524- Homework 1- Linear programs Solved
maximize 6x1 x 1 ;x 2 ;x 3
2x2 + 3x3
(1)
subject to: 2x1
x2 x3 + 2
(2)
0 x j 3; j 2 f1; 2; 3g (3)
a) Given the choice of the solvers Cl p, 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, riboavin, 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 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020 b) Implement the optimization problem in Julia. To get you started, Stigler’s original data is provided in st i gl er . csv, and the IJulia notebook st i gl er . i pynb 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 nonvegetarian solution? Is this as expected?
3. [2 points] Polyhedron modeling. We saw that the set of x such that Ax b where A 2 R m n and b 2 R m describes a polyhedron. For each polyhedron below, nd a matrix A and vector b such that Ax b describes the polyhedron. H int: since each inequality describes a dierent face, m should be equal to the number of faces. Make sure the inequalities go the right way!
(a) Regular cube centered at the origin (b) Regular octahedron centered at the origin with vertices at ( 1; 1; 1). with vertices at ( 1; 0; 0), (0; 1; 0), (0; 0; 1).
4. [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 cT x
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 (4). 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 2
2x2 + 3x3
(1)
subject to: 2x1
x2 x3 + 2
(2)
0 x j 3; j 2 f1; 2; 3g (3)
a) Given the choice of the solvers Cl p, 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, riboavin, 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 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020 b) Implement the optimization problem in Julia. To get you started, Stigler’s original data is provided in st i gl er . csv, and the IJulia notebook st i gl er . i pynb 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 nonvegetarian solution? Is this as expected?
3. [2 points] Polyhedron modeling. We saw that the set of x such that Ax b where A 2 R m n and b 2 R m describes a polyhedron. For each polyhedron below, nd a matrix A and vector b such that Ax b describes the polyhedron. H int: since each inequality describes a dierent face, m should be equal to the number of faces. Make sure the inequalities go the right way!
(a) Regular cube centered at the origin (b) Regular octahedron centered at the origin with vertices at ( 1; 1; 1). with vertices at ( 1; 0; 0), (0; 1; 0), (0; 0; 1).
4. [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 cT x
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 (4). 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 2
1 file (8.1KB)
