Description
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?
4
