ALL 14 CHAPTERS COVERED
SOLUTIONS MANUAL
, 1
Integer Programming: 2nd Edition
Solutions to Certain Exercises in IP Book
Chapter 1. Exercises 3, 6–8, 10, 16
Chapter 2. Exercises 1, 3, 7, 9, 11
Chapter 3. Exercises 2, 3, 8, 12, 14, 16
Chapter 4. Exercises 2, 6, 9, 12, 13
Chapter 5. Exercises 4, 5, 8, 11
Chapter 6. Exercises 1, 5, 9, 11, 12
Chapter 7. Exercises 3, 4, 10, 12
Chapter 8. Exercises 2, 4, 6, 8, 12, 17
Chapter 9. Exercises 3, 6, 16, 17
Chapter 10. Exercises 2, 4, 5, 6
Chapter 11. Exercises 1, 3
Chapter 12. Exercises 1, 2, 4
Chapter 13. Exercise 1
Chapter 14. Exercises 1, 3, 5
Solutions to Certain Exercises in Chapter 1
3. Modeling disjunctions.
(i) Extend the formulation of discrete alternatives of Section 1.5 to the
union of two bounded polyhedra (polytopes) Pk = {y ∈ Rn ∶ Ak y ≤ bk ,
0 ≤ y ≤ u} for k = 1, 2 where maxk maxi {aki y − bki ∶ 0 ≤ y ≤ u} ≤ M.
Integer Programming, Second Edition. Laurence A. Wolsey.
© 2021 John Wiley & Sons, Inc. Published 2021 by John Wiley & Sons, Inc.
Companion website: www.wiley.com/go/wolsey/integerprogramming2e
,2 Integer Programming: 2nd Edition
(ii) Show that an extended formulation for P1 ∪ P2 is the set Q:
y = 𝑤1 + 𝑤2
Ak 𝑤k ≤ bk xk for k = 1, 2
0≤ 𝑤k ≤ uxk for k = 1, 2
x1 + x2 =1
y ∈ ℝn , 𝑤k ∈ ℝn , xk ∈ {0, 1} for k = 1, 2.
Solution:
(i) Ak y ≤ bk +M𝟏𝛿k k ∈ [1, 2]
0≤y ≤ u
𝛿 1 + 𝛿2 = 1
𝛿k ∈ {0, 1} k ∈ [1, 2]
(ii) First we show that projy (Q) ⊆ P1 ∪ P2 .
If x1 = 1, then 𝑤2 = x2 = 0 leaving
y = 𝑤1 , A1 𝑤1 ≤ b1 , 0 ≤ 𝑤1 ≤ u
and thus y ∈ P1 . Similarly, if x2 = 1, it follows that y ∈ P2 .
Conversely, if y ∈ P1 ∪ P2 , suppose wlog that y ∈ P1 . Then (y, 𝑤1 , 𝑤2 ,
x1 , x2 ) ∈ Q with 𝑤1 = y, 𝑤2 = 0, x1 = 1, x2 = 0.
6. Prove that the set of feasible solutions to the formulation of the traveling
salesman problem in Section 1.3 is precisely the set of incidence vectors of
tours.
Solution: The solutions of the set
{ ∑ ∑ }
x ∈ ℤ+n(n−1) ∶ xij = 1 i ∈ [1, n], xij = 1 j ∈ [1, n]
j∶j≠i i∶i≠j
are assignments, namely a set of disjoint cycles, see Figure 1.2. The sub-
tour elimination constraints eliminate any solution consisting of two or more
cycles. Thus, the only solutions remaining are the tours.
7. The QED Company must draw up a production program for the next nine
weeks. Jobs last several weeks and once started must be carried out with-
out interruption. During each week, a certain number of skilled workers are
required to work full-time on the job. Thus, if job i lasts pi weeks, li,u workers
are required in week u for u = 1, … , pi . The total number of workers available
in week t is Lt . Typical job data (i, pi , li1 , · · · , lipi ) is shown below.
, Integer Programming: 2nd Edition 3
Job Length Week1 Week2 Week3 Week4
1 3 2 3 1 —
2 2 4 5 — —
3 4 2 4 1 5
4 4 3 4 2 2
5 3 9 2 3 —
(i) Formulate the problem of finding a feasible schedule as an IP.
(ii) Formulate when the objective is to minimize the maximum number of
workers used during any of the nine weeks.
(iii) Job 1 must start at least two weeks before job 3. Formulate.
(iv) Job 4 must start not later than one week after job 5. Formulate.
(v) Jobs 1 and 2 both need the same machine, and cannot be carried out
simultaneously. Formulate.
Solution:
(i) Let xti = 1 if job i starts in period t.
Each job i must start in some period and terminate before the end of the
time horizon
∑
9−pi +1
xui = 1 i ∈ [1, 5].
u=1
If job i starts in period u, the number of workers required by job i in
period t is 𝓁i,t−u+1 for t ∈ [u, u + pi − 1]. So the bound on the number of
workers available in period t gives:
∑
5
∑
t
𝓁i,t−u+1 xui ≤ Lt t ∈ [1, 9].
i =1 u=t−pi +1
The remaining constraints are xti ∈ {0, 1} and xui = 0 if u > 9 − pi + 1.
∑5 ∑t
(ii) Using (i), let 𝜂t = i=1 u=t−pi +1 𝓁i,t−u+1 xui be the number of workers
used in period t. Add the constraints 𝜂t ≤ 𝜂 and the objective function
min 𝜂.
(iii) If job 1 has not started in the first t periods, job 3 cannot start in the first
t + 2 periods.
∑
t
∑
t+2
xu1 ≥ xu3 t ∈ [1, 7].
u=1 u=1
SOLUTIONS MANUAL
, 1
Integer Programming: 2nd Edition
Solutions to Certain Exercises in IP Book
Chapter 1. Exercises 3, 6–8, 10, 16
Chapter 2. Exercises 1, 3, 7, 9, 11
Chapter 3. Exercises 2, 3, 8, 12, 14, 16
Chapter 4. Exercises 2, 6, 9, 12, 13
Chapter 5. Exercises 4, 5, 8, 11
Chapter 6. Exercises 1, 5, 9, 11, 12
Chapter 7. Exercises 3, 4, 10, 12
Chapter 8. Exercises 2, 4, 6, 8, 12, 17
Chapter 9. Exercises 3, 6, 16, 17
Chapter 10. Exercises 2, 4, 5, 6
Chapter 11. Exercises 1, 3
Chapter 12. Exercises 1, 2, 4
Chapter 13. Exercise 1
Chapter 14. Exercises 1, 3, 5
Solutions to Certain Exercises in Chapter 1
3. Modeling disjunctions.
(i) Extend the formulation of discrete alternatives of Section 1.5 to the
union of two bounded polyhedra (polytopes) Pk = {y ∈ Rn ∶ Ak y ≤ bk ,
0 ≤ y ≤ u} for k = 1, 2 where maxk maxi {aki y − bki ∶ 0 ≤ y ≤ u} ≤ M.
Integer Programming, Second Edition. Laurence A. Wolsey.
© 2021 John Wiley & Sons, Inc. Published 2021 by John Wiley & Sons, Inc.
Companion website: www.wiley.com/go/wolsey/integerprogramming2e
,2 Integer Programming: 2nd Edition
(ii) Show that an extended formulation for P1 ∪ P2 is the set Q:
y = 𝑤1 + 𝑤2
Ak 𝑤k ≤ bk xk for k = 1, 2
0≤ 𝑤k ≤ uxk for k = 1, 2
x1 + x2 =1
y ∈ ℝn , 𝑤k ∈ ℝn , xk ∈ {0, 1} for k = 1, 2.
Solution:
(i) Ak y ≤ bk +M𝟏𝛿k k ∈ [1, 2]
0≤y ≤ u
𝛿 1 + 𝛿2 = 1
𝛿k ∈ {0, 1} k ∈ [1, 2]
(ii) First we show that projy (Q) ⊆ P1 ∪ P2 .
If x1 = 1, then 𝑤2 = x2 = 0 leaving
y = 𝑤1 , A1 𝑤1 ≤ b1 , 0 ≤ 𝑤1 ≤ u
and thus y ∈ P1 . Similarly, if x2 = 1, it follows that y ∈ P2 .
Conversely, if y ∈ P1 ∪ P2 , suppose wlog that y ∈ P1 . Then (y, 𝑤1 , 𝑤2 ,
x1 , x2 ) ∈ Q with 𝑤1 = y, 𝑤2 = 0, x1 = 1, x2 = 0.
6. Prove that the set of feasible solutions to the formulation of the traveling
salesman problem in Section 1.3 is precisely the set of incidence vectors of
tours.
Solution: The solutions of the set
{ ∑ ∑ }
x ∈ ℤ+n(n−1) ∶ xij = 1 i ∈ [1, n], xij = 1 j ∈ [1, n]
j∶j≠i i∶i≠j
are assignments, namely a set of disjoint cycles, see Figure 1.2. The sub-
tour elimination constraints eliminate any solution consisting of two or more
cycles. Thus, the only solutions remaining are the tours.
7. The QED Company must draw up a production program for the next nine
weeks. Jobs last several weeks and once started must be carried out with-
out interruption. During each week, a certain number of skilled workers are
required to work full-time on the job. Thus, if job i lasts pi weeks, li,u workers
are required in week u for u = 1, … , pi . The total number of workers available
in week t is Lt . Typical job data (i, pi , li1 , · · · , lipi ) is shown below.
, Integer Programming: 2nd Edition 3
Job Length Week1 Week2 Week3 Week4
1 3 2 3 1 —
2 2 4 5 — —
3 4 2 4 1 5
4 4 3 4 2 2
5 3 9 2 3 —
(i) Formulate the problem of finding a feasible schedule as an IP.
(ii) Formulate when the objective is to minimize the maximum number of
workers used during any of the nine weeks.
(iii) Job 1 must start at least two weeks before job 3. Formulate.
(iv) Job 4 must start not later than one week after job 5. Formulate.
(v) Jobs 1 and 2 both need the same machine, and cannot be carried out
simultaneously. Formulate.
Solution:
(i) Let xti = 1 if job i starts in period t.
Each job i must start in some period and terminate before the end of the
time horizon
∑
9−pi +1
xui = 1 i ∈ [1, 5].
u=1
If job i starts in period u, the number of workers required by job i in
period t is 𝓁i,t−u+1 for t ∈ [u, u + pi − 1]. So the bound on the number of
workers available in period t gives:
∑
5
∑
t
𝓁i,t−u+1 xui ≤ Lt t ∈ [1, 9].
i =1 u=t−pi +1
The remaining constraints are xti ∈ {0, 1} and xui = 0 if u > 9 − pi + 1.
∑5 ∑t
(ii) Using (i), let 𝜂t = i=1 u=t−pi +1 𝓁i,t−u+1 xui be the number of workers
used in period t. Add the constraints 𝜂t ≤ 𝜂 and the objective function
min 𝜂.
(iii) If job 1 has not started in the first t periods, job 3 cannot start in the first
t + 2 periods.
∑
t
∑
t+2
xu1 ≥ xu3 t ∈ [1, 7].
u=1 u=1
