Description
1 Form the dual in two different ways and form the dual of the
dual
Consider the following linear program:
(P) min x1 − x2 + x3 (1)
s.t. x1 + x2 − x3 + 2×4 ≥ 0 (2)
3×1 + x2 + 4×3 − x4 = 4 (3)
− x1 − x2 + 2×3 + x4 ≤ 5 (4)
x1 ≥ 0, x2 ≤ 0, x3, x4 free (5)
1. Form the Lagrangian relaxation problem by relaxing the three complicating constraints (2)-
(4), which should be a minimization problem in the x variable.
2. Write down the closed-form solution of this Lagrangian relaxation problem
3. Write down the dual maximization problem.
4. Denote the dual maximization problem obtained above as (D). Now formulate the dual of (D)
using Lagrangian relaxation. You should develop a similar procedure, except here you need to
obtain the best upper bound of (D). Be careful about the signs of variables and constraints.
Compare the dual of the dual with the primal. Are they equivalent?
5. Form another dual program of (P) by relaxing all the constraints including the nonnegative
constraints on the variables. You need to write down the corresponding Lagrangian relaxation,
solve the Lagrangian relaxation in closed form, and finally write down the dual. Denote this
dual as (D0
).
6. Are (D) and (D0
) equivalent? Prove your claim.
2 More duals
Now hopefully you are getting familiar with the patterns of taking the dual. Do the following
exercises and try to write down the dual directly without going through the intermediate steps of
forming the Lagrangian relaxation problem.
1. Write down the dual.
(P) min − x1 + x2
s.t. − 2×1 − 3×2 ≤ −4
− x1 + x2 ≤ −1
x1, x2 ≥ 0.
1
2. Write down the dual.
(P) min x1 − 2×2 − x3
s.t. − x1 + 3×2 ≤ 0
3×1 − x3 ≤ 0
x2 + 2×3 ≤ 0
x1 ≥ 0, x2 ≥ 0, x3 free.
3 Use weak and strong duality theorems
Consider the following LP problem:
(P) max Xn
j=1
cjxj
s.t. Xn
j=1
aijxj ≤ 0, for all i = 1, . . . , m,
xj ≥ 0, for all j = 1, . . . , n.
1. Write down the dual of (P).
2. Can the dual LP’s optimal objective value be unbounded? Prove your statement.
3. Can the primal LP have unbounded optimal objective value? Prove your statement.
4. Suppose the dual LP is feasible. Does this information help you determine if the primal
problem has a finite optimal cost? If yes, what is primal problem’s optimal cost? Provide the
numerical value. If no, why? Articulate your reasoning.
4 Treasure Island and complementary slackness
Long John Jarvis discovered a vast treasure hidden on a deserted island. There was an unlimited
amount of gold and silver coins, jewel-encrusted plates, and ivory statues, all of which were completely unguarded and could be taken at no risk. Unfortunately, Long Jong’s ship had been sunk,
and he only had a small rowboat to put his treasure. The rowboat could hold up to 700 pounds of
treasure with a volume up to 700 cubic feet. The following table gives the value, size, and weight
of each type of treasure:
Unit Value (thousands of dollars) Size (cubic feet) Weight (pounds)
Gold coin 2 4 4
Silver coin 1 1 2
Jewel-encrusted plate 4 2 1
Ivory Statue 15 3 5
2
Being a very worldly and intelligent pirate, Long John was familiar with the basic principles
of linear programming. He came up with the following decision variables x1, x2, x3, x4 to be the
numbers of gold coins, silver coins, jewel-encrusted plates, and ivory statues that he would take.
Then, he set up the following LP to decide how much each treasure he should take in order to
maximize his wealth.
(P) max 2×1 + x2 + 4×3 + 15×4
s.t. 4×1 + x2 + 2×3 + 3×4 ≤ 700
4×1 + 2×2 + x3 + 5×4 ≤ 700
x1, x2, x3, x4 ≥ 0.
Because the rowboat’s limits were merely estimations, Long John was not concerned with restricting his variables to be integers; he could just round up the solution to the nearest integers if
necessary.
A much more important problem for Long John was that his laptop with Xpress and Matlab
was destroyed when his ship was sunk, so he could only solve LPs graphically by drawing on the
sand with a stick. However, since his LP had four variables, it would require a 4-dimensional graph
to solve, which was obviously impossible for Long John to draw.
Not knowing how to solve his LP, Long John just grabbed as many ivory statues (140 statues)
as he could and returned home with a wealth of $2100K. However, as a more advanced student of
linear programming than Long John was, you can do better! Work through the following steps to
retrieve more treasure!
1. Form the dual minimization problem of the above LP that Long John came up with. Think
about how to construct the dual by using the logic of finding the best upper bound to the
primal maximization problem. Extra credit will be awarded if you can articulate the reasoning
similar to the three examples shown in class.
2. Draw the feasible region of your dual problem. Hopefully you don’t need a 4-dimensional
graph!
3. Point out on the graph the optimal solution of the dual problem. Find out the numerical
values of this optimal dual solution. Hint: You might need to solve a simple set of linear
equations, which you can do by writing on the sand, but no need to run any simplex method.
4. What is the optimal objective value of the dual problem? So, how much more wealth can you
get than Long John did? Notice that we haven’t figured out the primal optimal solution yet.
So continue.
5. By just looking at the dual problem, decide which primal constraints must be active at the
primal optimal solution. Hint: Look at which dual optimal variables are nonzero. Then use
the Primal Complementary Slackness.
6. By just looking at the dual problem, decide which primal variables of the optimal primal
solution must be zero. Hint: Look at which dual constraints are active, and which are not
active at the dual optimal solution. Then, use the Dual Complementary Slackness.
7. Now, find out the primal optimal solution. This again you can do by just writing on the sand.
You can grab the treasure now!
3
5 Lagrangian relaxation for solving a hard combinatorial optimization problem
The title of this problem seems a bit scary, but don’t be scared. It is a simple example to show you
that the principle of Lagrangian relaxation that we learned in class for linear programming can be
used to solve difficult combinatorial and integer programming problems. Here is the problem.
You are going on a trip for your fall break (!). Before the trip, you need to pack up your bag
with the stuff you want to bring with you (toothbrush, camera, clothes, food, books, etc). Say you
have n items. Each one has a price pi
indicating how valuable the item i is for your trip. Each
item also has a weight wi
. Your bag can hold up to W total weight. You want to find a selection of
items that maximizes the total value and still is feasible for your bag to hold. In order to do this,
you decide to solve the following problem:
Z
∗ = max Xn
i=1
pixi (6a)
s.t. Xn
i=1
wixi ≤ W (6b)
xi ∈ {0, 1} ∀i = 1, . . . , n. (6c)
This is a famous problem in optimization called the “knapsack problem”. Notice the decision
variable xi
is a binary variable. If you have a lot of items to choose from, this problem can be quite
hard to solve. Now you want to get a good estimate on how much Z
∗ by a fast method. In other
words, you want to find an upper bound on Z
∗
. Here are the steps how you do this.
1. Form the Lagrangian relaxation problem of the knapsack problem (6). You need to introduce
a parameter y for constraint (6b). Note that the primal problem is a maximization problem,
so you need to careful about the sign of y. You should state clearly the sign of y for your
Lagrangian relaxation problem, and why you choose the sign this way.
2. Denote the optimal cost of the Lagrangian relaxation (LR) problem you formed above as
ZLR(y). Now we want to solve for ZLR(y). Inspect the LR problem. Does it have a decoupled
structure? If yes, can you decompose the LR into subproblems for each variable xi? (Hint:
the answer should be yes!) Solve each subproblem in closed form (the principle is similar
to what we did in class). Denote the optimal cost of each subproblem i as Zi(y). Find a
closed-form expression for Zi(y) [Hint: You may find out that Zi(y) can be expressed as
Zi(y) = max{ai
, 0}, where ai
is some expression involving y.]
3. Now, formulate the Lagrangian dual (LD) problem. In its primitive form, this dual problem
should be a nonlinear program involving piecewise linear functions in the objective. But you
should be very quick to reformulate it as a linear program. Write down both the nonlinear
program and the linear reformulation.
4. We want to test how good the upper bound given by the Lagrangian dual is. Here is a set of
test data.
(a) c = [10, 7, 13, 17, 19, 21, 6, 8], w = [4, 2, 7, 8, 5, 10, 2, 3], W = 10.
4
(b) c = [10, 7, 13, 17, 19, 21, 6, 8], w = [4, 2, 7, 8, 5, 10, 2, 3], W = 25.
(c) c = [10, 7, 13, 17, 19, 21, 6, 8], w = [4, 2, 7, 8, 5, 10, 2, 3], W = 35.
Write Xpress code to solve the original knapsack problem (6) and your Lagrangian dual
problem (the LP reformulation). The knapsack problem is an integer programming problem.
In Xpress, you can use the following code to specify the variable type of xi
: x(i) is binary. Once
you build up the optimization models. Solve them using the above three groups of data. For
each group, record the optimal costs of the primal knapsack problem and the dual problem
(denoted as ZD). Compute the percentage duality gap as (ZD − Z
∗
)/Z∗
. Submit on t-square
your code. Also submit a physical copy of your code and the numerical results. [You may
wonder if we can solve the primal, why bother with the dual. Here we are only solving some
very small sized problems. But the primal is an integer program, which will be very hard to
solve once the number of items n becomes really large. That’s where the dual becomes very
valuable.]
6 Economics and sensitivity analysis
Consider the linear program:
max x1 + 3×2
s.t. x1 + x2 ≤ 8 (resource 1)
− x1 + x2 ≤ 4 (resource 2)
x1 ≤ 6 (resource 3)
x1 ≥ 0, x2 ≥ 0.
1. Draw the feasible region of the above LP.
2. Graphically determine the optimal solution.
3. Graphically determine the shadow prices on the three resource constraints.
4. Graphically determine the range on the objective coefficient of each variable, holding the
coefficient of the other variable at its current value, for which the solution to part 6.2 remains
optimal.
5. Graphically determine the range on the availability of each resource (i.e. the right-hand side
constant), holding the availability of the other resources at their current values, for which the
shadow prices in part 6.3 remain optimal.
5
