CS524- Homework 8- Integer programs and duality Solved

1.   ABC Investments. ABC Inc. is considering several investment options. Each option has a minimum and maximum investment allowed (only if the option is chosen). These restrictions, along with the expected return are summarized in the following table (gures are in millions of dollars):

Option
Minimum

investment
Maximum

investment
Expected return (%)
1
3
27
13
2
2
12
9
3
9
35
17
4
5
15
10
5
12
46
22
6
4
18
12
Because of the high-risk nature of Option 5, company policy requires that the total amount invested in Option 5 be no more that the combined amount invested in Options 2, 4 and 6. In addition, if an investment is made in Option 3, it is required that at least a minimum investment be made in Option 6. ABC has $80 million to invest and obviously wants to maximize its total expected return on investment. Which options should ABC invest in, and how much should be invested?

2.   Lagrangian duality.               Consider the problem

                                                    )        subject to 1        x1       0:

(a)   Write down the solution of this problem and the optimal primal value p .

(b)   Derive the Lagrangian dual function g( ) for 2 R .

(c)   Find the solution of the Lagrangian dual problem max 0 g( ) and write down the optimal dual objective d .

(d)   Is the Slater condition satised for this problem? Does strong duality hold, that is, p = d ?

3.   Laurent goes to the gym. Laurent has a regular weight liting program. Today, he will be doing deadlifts and front squats. For each exercise he does 8 sets, with several repetitions per set (i.e., x3 means 3 repetitions). In the table below, you can see the weight he lifts in each set (given in lbs) and the number of repetitions for both deadlifts and front squats.

S et
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
Deadlift
310
x5
355
x3
395
x1+
375
x3
355
x3
330
x3
310
x3
290
x3
Front Squat
100
x5
130
x5
160
x3
160
x5
160
x7
160
x4
160
x6
160
x8
For both the deadlifts and the front squats, Laurent uses a steel bar which weighs 45 lbs. There are many available bumper plates (weights which are put on each side of the bar) with a weight of 2.5 lbs, 5lbs, 10 lbs, 25 lbs, and 45 lbs. Remember that there has to be the same amount of weight and the same type of plates on each side!

(a)   Laurent would prefer to not think to much while he is at the gym (lifting takes a lot of concentration). Can you help him solve an optimization problem which takes the current weight (considering one set and one exercise at the time) and minimizes the number of plates he has to put on the barbell? Make a schedule that shows which bumper plates Laurent should use for each weight.

1  of 2

CS/ECE/ISyE 524                                                      Introduction to Optimization                                             L. Roald,      Spring 2020

(b)   Because of COVID-19, Laurent can no longer go to the gym and has decided to invest in lifting equipment which he will install in his basement. He would like to continue doing the same exercises as in the table above, but now wants to minimize the total number of bumper plates that he has to order (while being able to combine them to give all of the above weights). Solve an optimization problem to determine which bumper plates Laurent should invest in.

(c)   Resolve the problem from (a), but consider that Laurent only has access to the bumper plates that he decided to buy. Print the new schedule that shows which bumper plates to put on the barbell for each exercise.

2  of 2