[SOLVED] Isye6669 homeworks 1 to 5 and project solution

1 A warm-up for using Xpress
This exercise is an introduction to Xpress, the main modeling language that we will use in this class.
The best way to learn Xpress is to use it to model and solve optimization problems. We will solve
the following facility location problem using Xpress.
Suppose A = (x1, y1) and B = (x2, y2) are the coordinates of two new facilities you want to
locate. There are three existing facilities at C = (300, 1200), D = (0, 600), and E = (600, 0). You
want to minimize the sum of `1 distances between A and B, A and C, A and D, B and D, and B
and E. The two new facilities should be located within the rectangular region (0, 900) for the x-axis
and (0, 1500) for the y-axis.
1. Write down an optimization model for the above facility location problem using absolute-value
functions in the objective.
2. Write down a linear programming reformulation of the above problem.
3. We have implemented your LP model in Xpress (see hw1prob1Fac.mos). The code is quite selfexplanatory and I have added comments in the code to help you understand its key features.
Go over the code and make sure you understand how the variables are declared and how the
objective and constraints are modeled. Now run the code by clicking on the green button with
a right arrow on it. The optimal solution should be printed out in the “Output/Input” tab
on the right panel of the Xpress window. Write down the optimal solution in your homework
submission. Do the two facilities overlap each other?
4. Now suppose facility A needs to be located close to the facility C within a distance of 500,
and the facility B needs to be located close to the facility E within a distance of 700. First,
model these conditions by constraints involving absolute value functions. Write down these
constraints in your homework paper submission. Second, reformulate them as linear constraints. Also write down your reformulation in the paper submission. Third, modify the
hw1prob1Fac.mos code to implement the new linear constraints. Solve the new model and
write down the optimal solution. Do the two new facilities overlap? You need to submit all
your code on t-square.
2 Quadratic programming and piecewise linear approximation
Consider the following nonlinear optimization problem involving absolute value functions:
(P) min f(x) = (x1 − 1.5)2 + (x2 − 0.8)2
s.t. |x1| + |x2| ≤ 1. (1)
1
1. First, reformulate (P) by rewriting the constraints in (P) as linear constraints. This feasible
region is called the `1 unit ball, because it is defined by all the points with `1-distance being 1
from the origin. Such a program is called a quadratic program (QP) with linear constraints.
2. Suppose you are given 10 feasible points, denoted as x
i = (x
i
1
, xi
2
) for i = 1, …, 10. Form
a convex piecewise linear function ˆf(x) using these 10 points such that ˆf(x) ≤ f(x) for all
x ∈ R
2
, and ˆf(x
i
) = f(x
i
) for i = 1, . . . , 10, i.e. ˆf(x) is a supporting lower envelope of f(x).
3. Formulate a linear program of minimizing ˆf(x) over the `1 unit ball.
4. Generate 10 feasible points for (P), write down their numerical values. You can do this by a
computer or by hand. You need to make sure the 10 points are all feasible.
5. Implement the above linear program in question 3 with the 10 points you generate in question
4 using Xpress. You need to submit the mos file on t-square and write down the optimal
solution in your paper submission. NOTICE: Xpress assumes that all the mpvar variables
are constrained to be nonnegative! So there is no need to specify non-negativity on variables.
However, if you want to have a free variable, you need to specify it explicitly as “x(i) is free”.
6. Now, implement the quadratic program with linear constraints that you formulated in question
1 and solve it in Xpress. Use the code hw1prob2QP.mos as the template (notice the code calls
“mmquad” and uses “qexp”). Compare the optimal solution and objective values of the QP
and the LP approximation. Later in the course, you will implement an automatic cutting plane
algorithm that generates supporting linear cuts on-fly to approximate a nonlinear function.
3 Production planning by a computer manufacturer
This is a problem that Digital Equipment Corporation (DEC) had faced in 1988, which illustrates
the usefulness of mathematical modeling for making important strategic decisions. DEC was a
major US computer company in 1950s-1990s. It was acquired by Compaq in 1998, which was at
the time the largest merger in the computer industry. Compaq later merged with HP in 2002.
In the beginning of 1988, DEC introduced a new family of single CPU computer systems and
workstations: GP-1, GP-2, and GP-3, which are general purpose computer systems with different
memory, disk storage, and expansion capabilities, as well as WS-1 and WS-2, which are workstations.
In the following table, we list the models, the list prices, and the memory usage. For example, GP-1
uses four 256k memory boards, and sells at $60,000.
System Price #256K boards
GP-1 $60,000 4
GP-2 $40,000 2
GP-3 $30,000 2
WS-1 $30,000 2
WS-2 $15,000 1
The following difficulties were anticipated:
1. The in-house supplier of CPUs could provide at most 7,000 units, due to debugging problems.
2
2. The supply of 256K memory boards was limited to be no more than 8,000 units.
On the demand side, the marketing department established the following:
1. The maximum demand for the first quarter of 1989 would be 1,800 for GP-1 system, 300 for
GP-3 system, 3,800 for the whole GP family, and 3,200 for the whole WS family.
2. Included in these projects were 500 orders for GP-2 system, 500 orders for WS-1, and 400
orders for WS-2 that had already been received and had to be fulfilled in the first quarter of
1989.
DEC needed to make a production plan for the first quarter of 1989 to consider all the above
production limitations and demand projections and to maximize the revenue.
(a) In order to model the problem that DEC faced, we introduce variables x1, x2, x3, x4, x5 that
represent the number (in thousands) of GP-1, GP-2, GP-3, WS-1, and WS-2 systems, respectively, to be produced in the first quarter of 1989. Strictly speaking, the 1000xi should be an
integer to represent the number of units. But for now, we ignore the integrality constraint
on 1000xi
. Formulate the problem as a linear program. Fill in objective and constraints
according to the descriptions.
max (total revenue):
s.t. (CPU availability):
(256K availability):
(max demand for GP-1):
(max demand for GP-3):
(max demand for GP family):
(max demand for WS family):
(min demand for GP-2):
(min demand for WS-1):
(min demand for WS-2):
(any other constraints?):
(b) Create an XpressMP model to solve the above complete LP problem. Hand in a printout of
your .mos and .dat files as well as the solution output.
4 Convex functions
1. Prove the piecewise linear function f(x) = max{a
>
1 x+b1, . . . , a
>
mx+bm} for x ∈ R
n
is convex
using the Jensen’s inequality.
2. Prove the following functions are convex, using one of your favorite conditions (Jensen’s inequality, the first-order condition, or the second-order condition):
(a) f(x) = e
ax for x ∈ R and any a ∈ R. Plot it.
(b) f(x) = x
a
for x > 0 and a ≥ 1 or a ≤ 0. Is such a function convex or concave for
0 ≤ a ≤ 1? Plot f(x) for a ≥ 1, a ≤ 0, and 0 ≤ a ≤ 1, separately.
3
(c) f(x) = − log(x) on x > 0. Plot it.
(d) f(x) = x log(x) for x > 0. This function is called the negative entropy function. Plot it.
(e) f(x, y) = x
2/y over x ∈ R and y > 0. Plot it.
(f) f(x1, x2) = (|x1|
p + |x2|
p
)
1/p for (x1, x2) ∈ R
2 and p ≥ 1. This is called the `p norm. We
have seen examples for p = 1, p = 2.

1 Convex Sets
1. Prove that if sets S1 and S2 are convex sets in R
n
, then their intersection S1 ∩ S2 is a convex
set, using the definition of convex sets.
Hint: This should be an easy argument following from the definition. Also, we always take an
empty set as a convex set.
Remark: This exercise tells us an important property that the intersection of two convex sets
is a convex set, in short we say, intersection preserves convexity.
2. Extend the above result to argue that S1 ∩ S2 ∩ … ∩ Sm is convex if all S1, . . . , Sm are convex
sets in R
n
for any m ≥ 1.
3. Show that a halfspace H+ = {x ∈ R
n
: a
>x ≥ b} is a convex set using the definition of a
convex set.
4. Show that a hyperplane H = {x ∈ R
n
: a
>x = b} is a convex set by using the conclusion of
questions 1 and 3.
5. Argue that a polyhedron is always a convex set by using the results from questions 2 and 3.
6. Show that the convex hull S of a finite number of points x
1
, . . . , x
m in R
n
is a convex set.
Hint: Use the definition of a convex set.
7. Give an example to show that a nonempty convex set may not be the convex hull of a finite
number of points.
8. Draw the following sets by hands using ruler and pencil (your circles do not have to be perfect).
State if each set is a convex set, and list all the extreme points of each set. If a set does not have
an extreme point, just say so. Hint: The definition of an extreme point applies to nonconvex
sets.
(a) T1 = {x ∈ R
2
: x1 + x2 ≤ 1}.
(b) T2 = conv −1
1

,

−2
0

,

−1
−1

,

1
−1

,

2
0

,

1
1

,

0
0
.
(c) T3 = {x ∈ R
2
: |x1| + |x2| ≤ 1}.
(d) T4 = {x ∈ R
3
: |x1| + |x2| + |x3| ≤ 1}.
(e) T5 = {x ∈ R
2
: 1 ≤ x
2
1 + x
2
2 ≤ 4}.
(f) T6 = {0, 1, 2, 3, 4} ⊂ R.
1
2 Convex Functions
1. Give an example of a function f : R → R that is both convex and concave.
2. Let f1 : R
n → R and f2 : R
n → R be two convex functions. Prove that the sum f = f1 + f2
is always a convex function. What about af1 + bf2 for any nonnegative constants a, b? Hint:
This should be a straightforward argument from the Jensen’s inequality, and this shows linear
combination of convex functions with nonnegative weights is again a convex function.
3. Let f1 = |x| and f2 = |x+1|. Notice that both f1 and f2 are convex functions. Let f = f1−f2.
Draw f1(x), f2(x), and f(x) for x ∈ [−2, 2] on the same plot by hand, i.e. using ruler and
pencil on a piece of paper by hand. Is f a convex function on [−2, 2]? Hint: Your answer
should show that the difference of two convex functions may not be a convex function any
more. Contrast this with the previous question.
4. Let f0 = x
2
, f1 = (x − 1)2
, …, fk = (x − k)
2
for all x ∈ R. Let gk(x) = max{f1(x), …, fk(x)}
for all x ∈ R. Draw f0, f1, f2, and g1(x) and g2(x) on two separate plots. Are they convex
sets?
5. Let f1(x), …, fk(x) be convex functions on R. Prove g(x) = max{f1(x), . . . , fk(x)} is a convex
function. Hint: Use the Jensen’s inequality and a similar argument that you used in Homework
1 for proving a similar result. This exercise shows that the pointwise max operation preserves
convexity of functions.
6. Define a set S = {(x, y) ∈ R
2
: y = sin(x)}, i.e. S is the graph of the sine function on the
entire real axis. Draw S. Is S a convex set in R
2
? Find the convex hull of S by drawing
it. Write down the inequalities that define the convex hull of S. Hint: This exercise requires
you to find the convex hull of an infinite number of points. Your intuition of how to form the
convex hull of a finite number of points should suffice to guide you.
3 LP geometry and the simplex method
1. Consider the following linear program:
min −2×1 − 3×2
s.t. x1 + x2 ≤ 4
−x1 + x2 ≤ 2
x1 − x2 ≤ 2
x1 ≥ 0, x2 ≥ 0.
Draw the feasible region of this linear program.
2. To solve this problem using the simplex method, first transform it into a standard form LP.
Denote x = [x1, x2, x3, x4, x5]
> as the vector of variables, and use the standard form notation:
min c
>x
s.t. Ax = b, x ≥ 0,
specify c, A, b for the above problem.
2
3. Now we want to solve the above standard-form linear program by the simplex method. If in
an iteration of the Simplex method, there is any ambiguity about which nonbasic variable to
enter the basis or which basic variable to exit the basis, use the Bland’s rule.
(a) For each iteration of the simplex method, write down the following information in the
format given below:
• Iteration k = numerical value, e.g. 1, 2, …;
• Basis B = [Ai
, Aj , Ak] = numerical value (i.e. you need to specify i, j, k as well as
the numerical values of the columns);
• Basis inverse B−1 = numerical value;
• Basic variable xB = [xi
, xj , xk] = numerical value (you need to specify i, j, k and
numerical values of xi
, xj , xk);
• Nonbasic variable xN = [xp, xq] = numerical value (you need to specify p, q and
numerical values of xp, xq);
• Reduced cost for each nonbasic variable ¯cp = cp − c
>
BB−1A? = numerical values;
Same for ¯cq; (you need to the index “?” for A?);
• Is the current solution optimal? If not, which nonbasic variable to enter the basis?
• Direction dB = −B−1A? = numerical value. Does the simplex method terminate
with an unbounded optimum?
• Min-ratio test θ
∗ = mini:dB(i)<0
{xB(i)/(−dB(i)
)} = min{numerical values of the ratios} =
numerical value of θ
∗
.
• Which basic variable to exit the basis?
Start at iteration k = 1 with the basis B1 = [A3, A4, A5]. Solve the above linear program
with simplex method and write down all the information required above for each iteration.
Also indicate the basic feasible solution at each step on the picture in (x1, x2). What is
the optimal solution of the above LP in (x1, . . . , x5)? What is the optimal cost?
From this exercise, you can see how the simplex method works and geometrically what each
step is doing.
4 Modeling exercise: least squares and robust regressions
Given a set of training data {xi
, yi}i=1,…,N , where xi
is an n-dimensional feature vector and yi
is a
label of value either 0 or 1. Think about each xi represents a vector of lab test data of a patient i
and yi
labels if this person has a certain disease. We want to build a linear classifier, i.e. a linear
function f(x) = β0 +
Pn
j=1 βjxj , so that for a given feature vector x, if f(x) ≥ 0.5, then x is
classified as y = 1, otherwise classified as y = 0.
There are many ways to build this linear classifier. Most of them try to find the coefficients of
the linear function by minimizing certain distance metric over the training data. A very popular
method is called the absolute deviation regression (ADR). ADR is also called robust regression.
The optimization model of ADR is described below.
(ADR) min
β0,…,βn
X
N
i=1

yi − β0 −
Xn
j=1
βjxij

,
3
where xij is the jth component of vector xi and both xij ’s and yi
’s are the given data, while βi
’s are
the decision variables. Note that the (ADR) model in the above form is a nonlinear optimization
problem, which cannot be directly solved by Xpress.
Answer the following questions.
1. Is the objective function of (ADR) a convex function in β0, . . . , βn? (The answer should be
yes.) But explain why, using the conclusion of question 2.2.
2. Write down a linear programming reformulation of (ADR).
3. Code your LP reformulation of (ADR) in Xpress, using the data file and the partial mos file
provided. Pay attention to the format of the data file and how it is handled in the mos file.
Submit your mos code in t-square. And write down your solution in the hardcopy of your
homework.
4. Use the MATLAB code to plot the hyperplane obtained from (ADR). Submit a hard copy of
the plot.

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.

Question 1: Cutting Stock Problem 1
In this problem, we want to walk you through one iteration of the column generation in solving the
cutting stock problem. Consider the following formulation
min Xn
j=1
xi
s.t. X
N
j=1
Ajxj = b
xj ≥ 0, ∀j = 1, . . . , N.
The problem has the following data. Customers need three types of smaller widths: w1 = 20, w2 =
40, w3 = 50 with quantities b1 = 250, b2 = 120, b3 = 100, respectively. The width of a big roll is
W = 170.
1. Assume the column generation algorithm starts from the following initial patterns:
A1 =


4
0
0

 , A2 =


0
4
0

 , A3 =


0
0
2

 .
Write down the restricted master problem (RMP) using these patterns.
2. Solve RMP in Xpress. Write down the optimal solution, the optimal basis B, and its inverse
B−1
. Find the optimal dual solution yˆ
> = c
>
BB−1
. To take the inverse of B, you can use
your favorite calculator or computer program. In this iteration, you could solve this LP by
hand. But we ask you to set up the code in Xpress and solve it using Xpress. This code will
be used in later iterations.
3. Write down the pricing problem, i.e. the knapsack problem using the above data and the
optimal dual solution you found.
4. Solve the pricing problem in Xpress. Should we terminate the column generation algorithm
at this point? Explain. If the column generation should continue, what is the new pattern
generated by the pricing problem?
5. If the column generation should continue, then augment (RMP) with the new column and solve
it in Xpress again. You can easily modify your Xpress code by incorporating the new column.
Write down the optimal solution, the optimal basis B, and the inverse B−1
. Compute the dual
variable. Then solve the pricing problem again by modifying the date in your code. Should you
terminate the column generation at this iteration? Explain. If the column generation should
continue, do the same for all the following iterations until the column generation terminates.
1
6. Write down the final optimal solution, the optimal basis, and the optimal objective value.
7. For this problem, you need to submit on t-square all your codes for all the steps separately.
Name them as question1 RMP step1.mos, question1 Pricing step1.mos, question1 RMP step2.mos,
and so on.
Question 2: Dantzig-Wolfe decomposition
Consider the following linear program:
min x1 − 2×2 + 3×3 − 4×4 (1)
s.t. x1 − x2 + x3 − x4 ≤ 1 (2)
x1 + x2 ≤ 1 (3)
− x1 + x2 ≤ 1 (4)
x2 ≥ 0 (5)
0 ≤ x3 ≤ 1 (6)
0 ≤ x4 ≤ 1 (7)
Consider constraint (2) as the complicating constraint and the rest (3)-(7) as easy constraints.
Notice that the easy constraints are separable, i.e. constraints (3)-(5) only involve x1 and x2, while
constraints (6)-(7) only involve x3 and x4. Therefore, define the polyhedron for variables x1 and x2
defined by (3)-(5) as P1, and P2 as the polyhedron for x3 and x4 defined by (6)-(7).
1. First, prove that both P1 and P2 are bounded.
2. Write down the master problem of the Dantzig-Wolfe decomposition. Since P1 and P2 are
separable, we will use extreme point representation for P1 and P2 separately. That is, for every
(x1, x2) ∈ P1, we write (x1, x2) = PN1
i=1 λi(x
i
1
, xi
2
) and λi
’s sum to one and are nonnegative,
where (x
i
1
, xi
2
) is an extreme point of P1 and N1 is the number of extreme points of P1.
Similarly, for every (x3, x4) ∈ P2, we write (x3, x4) = PN2
j=1 βj (x
j
3
, x
j
4
) and βj ’s are convex
weights. Use this representation to write down the Dantzig-Wolfe decomposition’s master
problem. How many columns are there in the master problem?
3. Write down a reduced master problem (RMP) by choosing the smallest number of columns
(i.e. just enough to form a basis) to start the Dantzig-Wolfe decomposition. Here, you need to
write explicitly the numerical values of the objective coefficients and the matrix of the RMP.
You do not need to solve this RMP.
4. Write down the pricing problem. Note that since the easy constraints are separable into P1
and P2, your pricing problem should also be separable into subproblems only involving P1 or
P2. You can denote the dual variables of RMP using some letters like y or z, i.e. since you
are not asked to solve the RMP, you can assume you know the dual variables and denote them
as some vectors.
5. Write down the condition under which the Dantzig-Wolfe decomposition should continue.

1 Two-Stage Stochastic Programming
Consider the following two-stage stochastic linear program appeared in the lecture note.
Z
∗ = min
x1,x2,y1,y2
100×1 + 150×2 +
X
2
s=1
ps(q
s
1
y
s
1 + q
s
2
y
s
2
)
s.t. x1 + x2 ≤ 120,
x1 ≥ 40,
x2 ≥ 20,
6y
s
1 + 10y
s
2 ≤ 60×1, ∀s = 1, 2,
8y
s
1 + 5y
s
2 ≤ 80×2, ∀s = 1, 2,
0 ≤ y
s
1 ≤ d
s
1
, ∀s = 1, 2,
0 ≤ y
s
2 ≤ d
s
2
, ∀s = 1, 2,
where the random data has two scenarios: (d
1
1
, d1
2
, q1
1
, q1
2
) = (500, 100, −24, −28) with probability 0.4
and (d
2
1
, d2
2
, q2
1
, q2
2
) = (300, 300, −28, −32) with probability 0.6, the first-stage decision is x = (x1, x2),
and the second-stage decision is y
s = (y
s
1
, ys
2
) for scenarios s = 1, 2.
The lecture note implemented two iterations of the Benders decomposition algorithm. Now we
want to carry on the steps until an optimal solution of the two-stage stochastic program is found.
1. Write an Xpress code to solve the subproblem in each iteration. You will use this code to solve
all the subproblems by entering the corresponding parameter values. You need to submit your
code on t-square and turn in a hard-copy with your homework.
2. Write an Xpress code to solve the restricted master problem (RMP) in each iteration. You
will update this code by adding a Benders cut in each iteration. You should incorporate the
two Benders cuts found in the first two iterations of the Benders decomposition. You need to
submit your code on t-square and turn in a hard-copy with your homework.
3. Now carry out the Benders decomposition from the third iteration. Follow the format given
in the numerical example of the lecture, i.e. write down the RMP, write down scenario
subproblems, solve them by the codes your build above, write down the optimal solutions,
find the upper bound UB and the lower bound LB, and construct the optimality cut. You
should only terminate when UB is equal to LB.
4. Write an Xpress code to solve the extensive formulation. Record the optimal solution and
objective value. Compare it to the result of the Benders decomposition. Are they the same?
1
2 IP modeling
1. Let three binary variables x1, x2, x3 represent “event i is chosen if xi = 1, and event i is not
chosen if xi = 0” for i = 1, 2, 3. Write down all feasible binary solutions of the nonlinear
constraint (1 − x1)·(1 − x2)· x3 = x1. Then, reformulate the nonlinear constraint using linear
constraints to describe the same set of feasible binary solutions.
2. Write one linear constraint to model the disjunction “Either event 1 is chosen or event 2 is
chosen or event 3 is not chosen”. Note that the “or” is inclusive without specification. Use
binary variable xi = 1 if event i is chosen, and xi = 0 if event i is not chosen.
3. Write linear constraints for the disjunction: “2×1 + x2 ≤ 2 or −x1 + 2×2 ≥ 2”. Here x1, x2
are continuous variables in the box [−3, 3] × [−3, 3] (i.e. −3 ≤ x1 ≤ 3 and −3 ≤ x2 ≤ 3). If
you need to use a big M in a constraint, then you need to find the smallest valid value for M
for each constraint. Draw the feasible region by hand.
4. Write linear constraints for the exclusive or (xor) statement: “2×1+x2 ≤ 2 or −x1+2×2 ≥ 2
but not both” and x1, x2 are in the box [−2, 2] × [−2, 2]. Find the best big M’s in your
formulation. Then, draw the feasible region defined by the above xor statement in the plane
of (x1, x2).
5. We have to place n facilities in n locations. The data are the amount fkl of goods that has to
be shipped from facility k to facility l, for k = 1, . . . , n and l = 1, . . . , n, and the distance dij
between locations i, j, for i = 1, . . . , n and j = 1, . . . , n. The problem is to assign facilities to
locations so as to minimize the total cumulative distance traveled by the goods. For example,
if f12 = 2, d34 = 3 and facility 1 is placed at location 3 and facility 2 is placed at location 4,
then the total distance traveled by the goods from facility 1 to facility 2 is f12d34 = 6. Now
define variable xki to be 1 if facility k is placed at location i, and 0 otherwise.
(a) Write down an integer programming model for this problem in the xki variables defined
above. The objective function should be a quadratic function. You need to explain each
constraint and the objective of your model.
(b) Write an equivalent linear integer programming model that linearizes the quadratic objective function. You need to introduce new variables for this purpose. Call these new
variables y and you can name each y with appropriate sub-index.
6. A company sets an auction for n objects numbered N = {1, 2, . . . , n}. Bidders submit their
bids for some subsets of the n objects that they like. The auction house has received m bids,
namely bids bj dollars for subset Sj ⊆ N of objects, for j = 1, . . . , m. We can use a matrix A
to store the Sj ’s in the following way: each row Ai of A corresponds to bidder i’s bid and the
component Aij = 1 if bidder i chooses object j and 0 otherwise. So A is a given 0-1 matrix of
m rows and n columns.
The auction house is faced with the problem of choosing the winning bidders so that profit is
maximized and each of the 10 objects is given to at most one bidder (multiple winning bidders
can be chosen). Formulate a linear integer program for the auction house to solve this problem
using the matrix A defined above. You need to define all variables carefully and explain each
constraint in your IP.
2
7. The demand for a product is known to be dt units in periods t = 1, . . . , n. If we produce the
product in period t, we incur a machine setup cost ft which does not depend on the number
of units produced plus a production cost pt per unit produced. We may produce any number
of units in any period. Any inventory carried over from period t to period t + 1 incurs an
inventory cost rt per unit carried over. Initial inventory is s0. Formulate a mixed integer
linear program in order to meet the demand over the n periods while minimizing overall costs.
8. Sharpen your pencil and try if you can crack the following Sudoku by hand. You can take as
long as you need. Now write down a binary program to solve the Sudoku. Then code it in
Xpress, solve it, and fill in your answer in the blanks. For your Xpress code, you can define a
list, e.g. {1, 3, 5}, inside declarations by L = [1, 3, 5].
8
3 6
7 9 2
5 7
4 5 7
1 3
1 6 8
8 5 1
9 4
P.S. Either you cracked this Sudoku by hand or by your binary program, congratulations! You
just solved the world’s hardest Sudoku.
3 Convex hull of mixed-integer program
1. Consider the following integer program.
(P) max − x1 + 2×2
s.t. − x1 + x2 ≤ 1.2
− 2×1 + x2 ≤ 1
6×1 + x2 ≤ 12
x2 ≥ 0
x1 ∈ Z, x2 ∈ Z.
(a) Draw the feasible region of (P).
(b) Find the optimal solution and optimal objective value of the linear relaxation of (P) by
inspection.
(c) Draw the convex hull of the feasible region of (P), denoted as conv(P).
(d) Write down the minimal set of linear constraints for conv(P).
(e) Find the optimal solution and optimal objective value of (P) by inspection.
3
2. Consider the following mixed-integer set.
S =

(x1, x2, y) : y + x1 ≤ 1.5, y + x2 ≤ 2, x1 ∈ Z+, x2 ∈ Z+, y ≥ 0

,
where x1, x2 are nonnegative integer variables and y is a continuous nonnegative variable.
(a) Draw the set S in of (x1, x2, y), with y as the axis vertical to the plane (x1, x2).
(b) On the same plot as in the above question, draw the convex hull of S, denoted as conv(S).
You need to be careful about the facets of the conv(S).
(c) Conv(S) should be a polyhedron. Write down a minimal set of linear constraints for
conv(S).
(d) On a different plot, draw the feasible region of the linear programming relaxation of S,
denoted as S
0
. Is S
0
the same as conv(S)?
4 Integer Hull, Branch-and-Bound, and Cutting-Plane
Consider the following integer programming problem:
(P) min − x1 − 2×2
s.t. 14×1 + 10×2 ≤ 39 (1)
− 5×1 + 4×2 ≤ 10 (2)
2×1 − 3×2 ≤ 3 (3)
x1, x2 ≥ 0, integer.
1. Solve the LP relaxation of (P) graphically. What are the optimal cost and optimal solution
of the linear programming relaxation?
2. Solve the IP graphically. What are the optimal cost and optimal solution of the integer
programming problem?
3. What is the integer hull of the set of feasible integer solutions? Find the minimal set of
defining linear inequalities for the integer hull.
4. Solve the problem by branch-and-bound. At the root node, branch on x1 variable. Solve the
LP relaxations in the bounding process graphically.
5. Now we want to derive a Chvatal-Gomory cut following the lecture notes. First write (P)
in standard form. After you solve the LP relaxation of (P) graphically, you will find that
x1, x2 are both basic variables. Use the standard form of Eq. (1) and Eq. (2) to derive a
new linear equality which has no x1 term and has x2 term with coefficient 1. Write down
this linear equality. Now do rounding down on both sides of it and write down the resulting
Chvatal-Gomory cut. Does it cut off the LP relaxation solution?

Problem 1: Column Generation for the Diet Problem
In this problem, we will solve a large diet problem. There are 7146 kinds of food listed, and 30 nutrients.
We want to find a diet that has the minimum level of cholesterol intake and at the same time satisfies all the
nutritional requirement.
For each nutrient i, let mi be the minimum daily intake of i and let Mi be the maximum daily intake of
i. For each food j, let aij be the amount of nutrient i in food j. Let cholj be the amount of cholesterol in
food j, and define variables xj to be the amount of food j in the daily diet. Then, the formulation of the
diet problem is:
min
7146
X
j=1
cholj · xj (1)
s.t.
7146
X
j=1
aijxj ≤ Mi
, ∀i = 1, . . . , 27 (2)
7146
X
j=1
aijxj ≥ mi
, ∀i = 1, . . . , 27 (3)
xj ≥ 0, ∀j = 1, . . . , 7146 (4)
Suppose you wanted to solve it using the student (free) version of Xpress, which cannot handle 7146 variables.
Apparently, you need to solve the problem in a more clever way. Column generation is an ideal approach.
Attached file (diet.colgen.partial.mos) gives the general framework of column generation, but it is missing
the crucial part.
Questions:
1. Complete the construction of the column generation code and submit the mos file online and also submit
a physical copy with the final report.
2. Print out the final solution from the code, and submit it in the final report.
3. Now, you want to find an optimal diet with the total calorie intake between 1800 cal and 2000 cal.
Modify the data file diet.xls (the minimum and maximum levels in the calorie column), and resolve the
above problem. Report in the final report the composition of optimal diet and the total amount of each
nutrient provided by the diet.
HINT:
1. getdual(name) is the Xpress function to retrieve the optimal dual variable (also called shadow price) of
a constraint called “name”. To store that shadow price, you need to save that value in the array given
to you.
2. A general way to add a new column to a constraint or the objective function is: name += XXX, where
name is the name of the constraint or the objective function, and XXX is the part of the constraint
that comes with the new variable.
2
Problem 2: Solution Strategies for the Cutting Stock Problem
The cutting stock problem formulation that we learned in class is due to P. C. Gilmore and Ralph E. Gomory.
They published this formulation in their 1961 paper “A linear programming approach to the cutting-stock
problem”, Operations Research, 8 (1961), 849-859. We call this formulation the Gilmore-Gomory formulation.
A little history here: Ralph E. Gomory is a renowned mathematician and a key figure in the development
of both theoretical understandings and computational methods for integer programming. He has also been
very influential in bringing operations research to the real world. He first worked at IBM as a research
mathematician and later became IBM’s Senior Vice President for Science and Technology. He helped IBM
attain some of the best minds for OR for over 20 years. He still maintains a blog in the Huffington Post on
interesting topics such as technology development and industry research1 at an advanced age.
An alternative optimization formulation for the cutting stock problem was proposed by the Soviet mathematician and economist Leonid V. Kantorovich in 1939. His paper was published in English in 1960 (“Mathematical Methods of Planning and Organising Production” Management Science, 6 (1960), 366-422. You can
get the paper online through Tech’s library.) Later, Kantorovich won the Nobel Prize in Economics in 1975,
shared with another pioneer of operations research Tjalling Koopmans, “for their contributions to the theory
of optimal allocation of resources.”
Kantorovich’s formulation for the cutting stock problem is very different from the Gilmore-Gomory formulation. In this problem, we lead you through steps to formulate the Kantorovich formulation and implement
in Xpress. Then, we ask you to implement Column Generation on the Gilmore-Gomory formulation. The
purpose is to compare these two different formulations and solution strategies for solving the same cutting
stock problem. Through this exercise, you will learn that the compact formulation of an optimization problem
might not always be computationally easier to solve than a larger formulation. You will also see the power
of column generation as a solution strategy to solve large-scale linear programs.
Problem 2.1: The Kantorovich Formulation: A Modelling Exercise
The Kantorovich formulation uses the following data and decision variables:
1. Data:
• wi
, i = 1, . . . , m: the width of small roll item i.
• bi
, i = 1, . . . , m: the demand for item i.
• W: the width of the large rolls.
• K: the total number of large rolls. (Note that this data is not required in the Gilmore-Gomory
formulation.)
2. Decision variables:
• y
k
: if large roll k is cut then y
k = 1, otherwise y
k = 0, for k = 1, . . . , K.
• x
k
i
: number of times that item i of width wi
is cut on the large roll k.
Now we lead you through the steps to formulate the Kantorovich model.
• The objective is given as to minimize the number of large rolls cut to satisfy demand:
min X
K
k=1
y
k
1https://www.huffingtonpost.com/ralph-gomory/
3
• Constraint 1: Demand must be satisfied with equality for each item i = 1, . . . , m.
• Constraint 2: The width of a large roll can not be exceeded for each large roll k = 1, . . . , K. Here you
should consider that Constraint 2 is only needed when a large roll is cut, which involves the y
k variable.
• Constraint 3: Variable bounds and integrality constraints.
Questions:
1. How many variables and constraints are there in this formulation?
2. Use the files cs.Kantorovich.partial.mos as a starting point. Finish the Xpress code and solve the
problem using the data file kant1.dat. Submit the mos file online and also submit a physical copy with
the final report. Print out the optimal objective value and the optimal solution in the report. Since
there are many variables, to save space, only print out the non-zero optimal variables for both x
k
i
’s and
y
k
’s.
3. Next change K to 600 and change m to 10 and use the data file cs1.dat. What do you observe? Is it
easy or hard to solve the problem using the Kantorovich formulation? You can keep the solver running
as long as you want, when it terminates (or when you run out of patience and stops it manually, click
on the red cross button), answer the following questions:
• How many branch-and-bound (BB) nodes are searched by the BB algorithm?
• What is the objective value of the best lower bound and the objective value of the best integer
solution found?
• What is the optimality gap given by the above two numbers?
• How many integer solutions are found by the BB algorithm?
• How many seconds did the algorithm take?
For these questions, click on the “Stats” tab on the right-hand side panel in Xpress. Look at the results
after “Current node”, “Best Bound”, “Best solution”, “Gap”, “Status”, and “Time”. Lastly, relax the
integrality constraints. Write your answers in the report.
4
Problem 2.2: The Gilmore-Gomory Formulation: Use Column Generation
You should encounter some difficulty with the Kantorovich formulation for the larger data set. In this part,
we want to solve the Gilmore-Gomory formulation (exactly the same formulation we discussed in class) using
column generation. The master problem is given below.
min X
N
j=1
xj
s.t. X
N
j=1
aijxj = bi
, ∀i = 1, . . . , m (Demand Constraints)
xj ≥ 0, ∀j = 1, . . . , N.
Attached file (cs.colgen.partial.mos) gives the general framework of the column generation algorithm. It
also has detailed instructions on how to complete the code. The programming experience you gained in
solving Problem 1, the diet problem, will be useful here. You need to do the following.
Questions:
1. Complete the column generation code. Submit the completed mos file online and also submit a physical
copy with the final report.
2. Print out solution summary for each test instance (cs1.dat, cs2.dat, cs3.dat), following the instructions in the cs.colgen.partial.mos file.
3. In your report, discuss the differences between the LP solutions and the integer solutions obtained in the
three test instances, also the differences between the integer solutions of the two approaches (rounding
and resolving). Which approach produces better solution?
4. Now, change the demand constraint from = to ≥, that is, PN
j=1 aijxj ≥ bi
. Solve the LP relaxation
of the resulting cutting stock problem and obtain the integer solutions using the same procedure as in
the above question for kant1.dat, cs1.dat, cs2.dat, cs3.dat. Compare the results to the ones of the
equality demand constraint. If the two formulations give different solutions, elaborate how the solutions
are different for each test case.
HINT:
1. The Xpress code uses dynamic array to implement an array whose size can change dynamically. To
create a new variable, use create(variable name).
2. You can use a similar way to add new columns to constraints and the objective function as hinted in
problem 1.
Problem 2.3: An Alternative Objective – Minimize Total Waste
Now let us consider an alternative objective of minimizing the total wasted paper for satisfying demand.
More specifically, the total wasted paper of a cutting stock solution is the total amount of paper that is cut
but not used to satisfy the demand. For instance, if a large roll of width 100 is cut into 3 copies of width 30
and the remaining 10 = 100 − 3 × 30 units of width is thrown away, then that 10 units of paper is counted
as wasted paper of this roll. The total amount of wasted paper is the sum of wasted paper from each large
roll that is cut to satisfy demand. We call the new cutting stock problem, CS-min-waste.
Answer the following questions.
Questions:
5
1. Modify the Gilmore-Gomory formulation (the LP version) to incorporate the objective of minimizing
the total wasted paper. The demand constraint is still an equality constraint. Write down the new
formulation.
2. Use column generation to solve CS-min-waste. Write down the reduced master problem (RMP) and
the pricing problem. In particular, the pricing problem should be written first as an enumerate problem
and then be transformed into an optimization problem.
3. Write a new .mos file (name it cs.colgen.minwaste.mod) to implement the column generation for CSmin-waste. Your code should also include the capability to get an integer solution through resolving.
Hand in your code on t-square.
4. Run your code cs.colgen.minwaste.mod on all four test cases kant1.dat, cs1.dat, cs2.dat, cs3.dat.
Compare CS-min-waste with the original cutting-stock formulation in Problem 2.2. For each test case,
does the LP solution of CS-min-waste have the same optimal objective with that of the original cuttingstock problem? What about the optimal LP solution? Does the integer solution of CS-min-waste have
the same objective with the original problem? Compare the total amount of wasted paper of the integer
solution of the cs-min-waste model with that of the original model? How much different are they?
5. After you run the test cases, does your results suggest some interesting relation between the LP solutions
of the two cutting stock models? Prove that these two models (both the LP relaxation and the integer
version of the CS-min-waste and the original cutting-stock problems) are in fact equivalent, thus always
give the same optimal objective value. Or argue that your experimental results disprove the above
statement.
6. Now change the demand constraint to ≥ as in Problem 2.2 Question 4. Modify your cs.colgen.minwaste.mod
code and rerun all the four test cases. Answer Problem 2.3 Question 4 again with the new results. Can
you explain why the new results with demand constraint of ≥ are different or the same as the ones with
demand constraints of = sign you obtained in Problem 2.3 Question 4?
6
Problem 3: TSP using Dantzig-Fulkerson-Johnson Formulation
In this problem, we study the classic formulation for the TSP problem, namely the Dantzig-Fulkerson-Johnson
(DFJ) formulation, and implement a constraint generation algorithm to solve it.
DFJ Formulation
The DFJ formulation was first proposed by G. Dantzig, D. Fulkerson, and S. Johnson. All three of them made
significant contributions to operations research and optimization. The original paper where they first proposed
the formulation has become a classic “Solutions of large scale travelling salesman problem”, Operations
Research, 2:393-410, 1954.
(DF J) min Xn
i=1
Xn
j=1
dijxij (5)
s.t. Xn
j=1
xij = 1 for all cities i = 1, 2 . . . , n (6)
Xn
j=1
xji = 1 for all cities i = 1, 2 . . . , n (7)
X
i∈S
X
j∈S
xij ≤ |S| − 1 for all subset S ⊂ N and S 6= N (8)
xij ∈ {0, 1} for all cities i, j = 1, 2, . . . , n
The decision variables xij = 1 if the tour goes directly from city i to city j, xij = 0 otherwise. The objective
is to minimize the total travel distance of the tour Pn
j=1 dijxij , where dij is the distance between cities i
and j. Constraint (6) ensures that the tour goes from city i to exactly one other city, and Constraint (7)
ensures that the tour goes into city i exactly from one other city. These two types of constraints together are
called the assignment constraints. However, as we know, they are not enough to characterize a correct tour,
because the solution to the assignment constraints may contain subtours of smaller cycles around subsets of
cities. We need constraints (8) to eliminate all the subtours. Here N = {1, 2, . . . , n} is the set of all n cities,
and S is any strict subset of N with |S| number of cities.
The DFJ formulation has n
2 binary variables. However, the number of constraints is astronomical! Indeed,
we need a subtour elimination constraint (8) for each non-empty subset S of N, excluding N itself (why?).
There are 2n − 2 such constraints. That’s why we say the number of constraints is exponentially many in the
number of variables. For a problem of 48 cities, there will be 248 − 2 = 281, 474, 976, 710, 654 (281 trillion)
subtour elimination constraints. It will be completely nonsensical to enter such a model into Xpress!
Constraint Generation Algorithm
In the following, we outline a constraint generation procedure that can be implemented quite easily in
Xpress and can find an optimal (yah!) solution fairly fast. The strategy is as follows:
1. First form the restricted master problem with a subset of constraints (8). In the following we will
explore different options for the initial set of constraints.
2. Solve the restricted master problem.
3. Check if any subtour elimination constraint is violated by the current solution. There are many ways
to do this. We choose the following method: Find a tour starting at City 1 (which is Atlanta). Such a
tour always exists and is unique (Why?). Then, if this tour contains less than 48 cities, then this is a
subtour and we can add the corresponding subtour elimination constraint (8) to the restricted master
7
problem. Go to Step 2 and repeat. Otherwise if the tour has all 48 cities, then it is a legitimate TSP
tour, and in fact optimal, then we are done.
Steps to Implement the Algorithm
The above outlined framework of constraint generation is partially coded in TSP-partial.mos. The data file
US48.dat contains coordinates of the 48 state capitals. You need to fill in the parts that are marked “!!!!!!!!!
fill in your code here !!!!!!!!!!!”. In particular, you need to do the following to complete the code:
1. Formulate the objective function, all the assignment constraints.
2. Write small subtour elimination constraints for subsets of 1 city, 2 cities, 3 cities, and 4 cities.
3. Finish the constraint generation part:
(a) Write code to find a subtour starting at Atlanta (City 1). Hint: One way to find such a tour is
to start at Atlanta and see which city comes next, then see which city comes after that, etc, until
you trace back to Atlanta. Mark all the cities on the subtour.
(b) Write code to generate the corresponding subtour elimination constraints and add it to the restricted problem.
Computational Experiments
1. Begin with all of the small subtour elimination constraints commented out (So, these will be generated
by your constraint generation code if necessary.) Use your Xpress code to solve the problem. If it runs
for more than 20 minutes, stop Xpress in the middle — report “Reach time limit of 20 min”. If it does
finish quickly, record how long it takes and how many constraints were generated. You can find the
running time in the “Stats” tab in Xpress.
2. Now un-comment the 1-city subtour elimination constraints, so that the formulation begins with those
constraints already in it. Use your Xpress code to solve the problem. If it runs for more than 20
minitues stop Xpress in the middle and report “Reach time limit of 20 min”. If it does finish quickly,
record how long it takes and how many constraints were generated.
3. Now start the formulation with both 1-city and 2-city subtour elimination constraints. Use your Xpress
code to solve the problem. If it runs for more than 20 minitues stop Xpress and report “Reach time
limit of 20 min”. If it does finish quickly, record how long it takes and how many constraints were
generated.
4. Now start the formulation with 1-city, 2-city, and 3-city subtour elimination constraints. Use your
Xpress code to solve the problem. If it runs for more than 20 minitues stop Xpress and report “Reach
time limit of 20 min”. If it does finish quickly, record how long it takes and how many constraints were
generated.
5. Now start the formulation with 1-city, 2-city, 3-city, and 4-city subtour elimination constraints. Use your
Xpress code to solve the problem. If it runs for more than 20 minitues stop Xpress and report “Reach
time limit of 20 min”. If it does finish quickly, record how long it takes and how many constraints were
generated.
6. For each of (i)-(v), how many subtour elimination constraints did the formulation begin with?
7. Plot the optimal TSP tour you found, using the Matlab code US48TourPlot.m.
8. Figure out each city’s name (City 1 is Atlanta). Write the TSP tour in the names of the state capitals.
8
9. Select 26 cities that you want to visit. Create a new data file US26.dat. You will need to use this data
set for the next part as well. Run your Xpress code to find an optimal TSP tour. Report the optimal
tour. Modify the Matlab code and generate a similar plot of the tour over these 26 cities. You need to
hand-in the new data file for this part.
Deliverables
1. Complete and well-commented Xpress codes (both .mod and US26.dat). Include all of the 1-city, 2-city,
3-city, and 4-city subtour constraints, but comment out the 3-city and 4-city subtour constraints. Data
initialization part uses the 48-city data.
2. Matlab code for reading data and generating the plot for 26-city tour.
3. In the final report, answer all the questions in steps 1-6 of Section , and print out the optimal 48-city
TSP tour and the optimal 26-city TSP tour, their total distances, and the plots generated by the Matlab
code. For the 26-city tour, you need to clearly state the indices and the names of the 26 cities you
select, and attach the data file you used in Xpress. Attach the complete Xpress and Matlab code in the
end.