[SOLVED] Csci 5654: assignment #5

(Reading: Slides on ILP, Vanderbei Chapter 23)
P1. (10 points) Solve each of the problems below using a branch-and-bound method. Write
down the solution obtained and the enumeration tree obtained. You may use any LP solver of your
choice to solve the subproblems. Please do not use a ILP solver directly.
(A)
max 2×1 −3×2 −2×3 −x4
s.t. x1 −x2 +x3 ≤ 5
x1 −2×2 −x3 +x4 ≤ 3
x1 −x2 −x3 −x4 ≤ −1
x1, x2, x3, x4 ∈ [−5, 5]
x1, x2, x3, x4 ∈ Z
Hint: Use x4 as the variable to branch on.
(B)
max 2×1 +3×3 +x4
s.t. x1 −x2 +x4 ≤ 1
2×2 −x4 ≤ 2
x1 −x3 −2×4 ≤ −1
−x1 +x4 ≤ 1
x1 ∈ {−2, −1, 0, 1, 2}
x2 ∈ {−1, 0, 1}
x3 ∈ {0, 1}
x4 ∈ {−1, 0, 1}
P2. (10 points) Consider the final dictionaries for the LP relaxation of a few ILPs. Assuming all
variables are integers, write down all the cutting planes:
Dictionary # 1:
x1 0.666666666667 −0.666667×5 +0.333333×4
x2 1 −1×5
x3 2 +4×5 −1×4
z 1 −1×5
Dictionary # 2:
x4 4.33333333333 +0.333333×8 +0.666667×9 −0.333333×3
x5 8.66666666667 −0.333333×8 +0.333333×9 −2.666667×3
x6 10 −1×3
x7 3 −3×8 +1×9 −18×3
x1 5.66666666667 −0.333333×8 −0.666667×9 +0.333333×3
x2 1.33333333333 +0.333333×8 −0.333333×9 +2.666667×3
z 7 −1×9 −2×3
1
P3 (20 points). Consider the graph below which shows various locations and the driving times
between them in hours:
Our goal is to decide whether or not to place a hospital at each node. The following are the
cost of building a hospital at various nodes in millions of dollars:
Node Cost
1 3
2 3
3 1.5
4 1
5 1.2
6 1.3
7 0.9
8 0.8
The following constraints should apply to our placement of hospitals: each node should either
have a hospital or be within 1 hour driving distance of a hospital.
For your convenience, the table of pairwise shortest path distances is given as an excel spreadsheet.
(A) Let G be a graph with n nodes and W(i, j) denote the shortest path weight between nodes i
and j. Finally let c be a n × 1 vector of node costs. Write down an integer linear programming
formulation of the above problem.
(B) Formulate and solve your ILP for the given example.
P4 (15 points) Consider a polyhedron P given by the constraints
Ax ≤ b, ` ≤ x ≤ u .
(a) Write down mixed integer programs that will find the point x ∈ P with the largest number of
0 entries in x,
(b) Write down mixed integer programs that will find the point x ∈ P with the smallest number
of 0 entries in x.
2
(c) Write down a mixed integer program that will search for a solution x ∈ P maximizing an
objective function c
tx such that x does not satisfy a ≤ x ≤ b, for given a, b.
P5 (10 points) We are given sets of numbers hS1, . . . , Ski such that each Si ⊆ {1, . . . , n}. For
example, n = 10 and the sets are
S1 : {1, 3, 6}, S2 : {2, 7, 8}, S3 : {1, 8, 9}, S4 : {1, 6, 5, 3} .
Our goal is to select a subset S ⊆ {1, 2, . . . , n} such that S ∩ Si 6= ∅ for i = 1, . . . , k and the
sum of elements in the chosen set S is minimized.
Formulate a 0−1 ILP for the problem for given n, k,hS1, . . . , Ski. Also, solve it for the example
above.
3