Combinatorial Optimization
Lecture 3: Introduction to Integer Linear Programming
Le Hai Yen, Institute of Mathematics, VAST
Master IATOM, USTH, Hanoi
2024
Lecture 3: Introduction to Integer Linear Programming
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Integer linear programs Modeling examples
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Integer linear programs Modeling examples
Example 1: classical knapsack problem
Given a set of items {1, . . . , n}
Item i has weight wi and value ci
Given a knapsack that can hold a weight at most W
Which items should be put into the knapsack
so that the total weight ≤ W
and the total value is as large as possible
Integer linear programs Modeling examples
Example 1: classical knapsack problem
Variables: xi = 1 if item i is chosen, = 0 otherwise
Formulation:
∑
n
max ci xi
i=1
∑
n
subject to wi xi ≤ W
i=1
xi ∈ {0, 1} ∀i = 1, . . . , n
Integer linear programs Modeling examples
Example 2: night shift scheduling problem
Task: Make a weekly night shift schedule for a hospital’s nurses.
Constraints:
dj = demand for nurses for the night shift on day j
(j = 1, . . . , 7).
Every nurse works 5 days in a row on the night shift.
Goal: Find the minimum number of nurses.
Integer linear programs Modeling examples
Example 2: night shift scheduling problem
Variables: xj = number of nurses starting their week on day j.
IP formulation:
min x1 + x2 + x3 + x4 + x5 + x6 + x7
s.t. x1 + x4 + x5 + x6 + x7 ≥ d1
x1 + x2 + x5 + x6 + x7 ≥ d2
x1 + x2 + x3 + x6 + x7 ≥ d3
x1 + x2 + x3 + x4 + x7 ≥ d4
x1 + x2 + x3 + x4 + x5 ≥ d5
x2 + x3 + x4 + x5 + x6 ≥ d6
x3 + x4 + x5 + x6 + x7 ≥ d7
x1 , x2 , x3 , x4 , x5 , x6 , x7 ∈ Z+
Integer linear programs Formulations
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Integer linear programs Formulations
Integer linear programming (IP)
In words:
Optimize a linear function
subject to linear constraints on integer variables
Math model (standard form):
∑
n
max cj xj (1)
j=1
∑
m
s.t. aij xj ≤ bi (i = 1, . . . , m) (2)
i=1
xj ∈ Z (j = 1, . . . , n) (3)
Variants:
Mixed integer (linear) programming (MIP)
x ∈ Zp × Rq
Binary (linear) programming
xj ∈ {0, 1} (j = 1, . . . , n)
Integer linear programs Formulations
Integer linear programming
Matrix form:
Integer Program (IP) Mixed Integer Program (MIP)
min ct x min ct x
s.t. Ax ≤ b s.t. Ax ≤ b
n
x∈Z x ∈ Zp × Rq
Solving integer linear programs 2D graphical resolution
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Solving integer linear programs 2D graphical resolution
A small example: Knapsack
Input: a knapsack and
two item types
Weight Value
Type 1 3 kg 3$
Type 2 5 kg 4$
Constraints:
at most 4 items
at most 15 kg
Objective: bring
maximum value
Solving integer linear programs 2D graphical resolution
A small example: Knapsack
x1 = number of items of type 1 Input: a knapsack and
x2 = number of items of type 2 two item types
Weight Value
max 3x1 + 4x2 Type 1 3 kg 3$
subject to Type 2 5 kg 4$
x1 + x2 ≤ 4
Constraints:
3x1 + 5x2 ≤ 15
at most 4 items
x1 , x2 ∈ Z+ at most 15 kg
Objective: bring
maximum value
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
x1 = number of items of type 1 x2
x2 = number of items of type 2
4
max 3x1 + 4x2
3
subject to
2
x1 + x2 ≤ 4
3x1 + 5x2 ≤ 15 1
x1 , x2 ∈ Z+
0 1 2 3 4 5 x1
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
LP relaxation x2
4
max 3x1 + 4x2
3
subject to
x1 + x2 ≤ 4 2 (2.5, 1.5)
3x1 + 5x2 ≤ 15 1
Z
Z
x1 , x2 ∈ + R
Z
0 1 2 3 4 5 x1
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
(P1 ) max 3x1 + 4x2
subject to
x1 + x2 ≤ 4 x2
3x1 + 5x2 ≤ 15
x1 ≤ ⌊2.5⌋
4
x1 , x2 ∈ R
3
2
(P2 ) max 3x1 + 4x2
subject to 1
x1 + x2 ≤ 4
0 1 2 3 4 5 x1
3x1 + 5x2 ≤ 15
x1 ≥ ⌈2.5⌉
x1 , x2 ∈ R
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
(P1 ) max 3x1 + 4x2 x2
subject to
x1 + x2 ≤ 4
4
3x1 + 5x2 ≤ 15
x1 ≤ ⌊2.5⌋ 3
(2, 95 )
x1 , x2 ∈ R 2
(3, 1)
1 opt = 13
(P2 ) max = 13
0 1 2 3 4 5 x1
at (x1 , x2 ) = (3, 1) ∈ Z2
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
(P1.1 ) max 3x1 + 4x2
subject to
x1 + x2 ≤ 4 x2
3x1 + 5x2 ≤ 15
x1 ≤ ⌊2.5⌋
x2 ≤ ⌊1.8⌋ 4
x1 , x2 ∈ R
3
(P1.2 ) max 3x1 + 4x2
2
subject to
(3, 1)
x1 + x2 ≤ 4 1 opt = 13
3x1 + 5x2 ≤ 15
x1 ≤ ⌊2.5⌋
0 1 2 3 4 5 x1
x2 ≥ ⌈1.8⌉
x1 , x2 ∈ R
(P2 ) max = 13
at (x1 , x2 ) = (3, 1) ∈ Z2
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
x2
(P1.2.1 ) max 3x1 + 4x2
subject to 4
x1 + x2 ≤ 4
3x1 + 5x2 ≤ 15 3
x1 ≤ 1
2
x2 ≥ 2
(3, 1)
x1 , x2 ∈ R 1 opt = 13
(P2 ) max = 13
0 1 2 3 4 5 x1
at (x1 , x2 ) = (3, 1) ∈ Z2
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
x2
(P1.2.1.1 ) max = 12
4
at (x1 , x2 ) = (0, 3) ∈ Z2 (0, 3)
3 opt = 12
(P1.2.1.1 ) max = 11
2
at (x1 , x2 ) = (1, 2) ∈ Z2 (1, 2)
(3, 1)
opt = 11
1 opt = 13
(P2 ) max = 13
at (x1 , x2 ) = (3, 1) ∈ Z2 0 1 2 3 4 5 x1
Solving integer linear programs 2D graphical resolution
Branch-and-bound method in 2D
x2
4
max = 13 3
2
at (x1 , x2 ) = (3, 1) ∈ Z 2
(3, 1)
1 opt = 13
0 1 2 3 4 5 x1
Solving integer linear programs Branch-and-bound method
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Solving integer linear programs Branch-and-bound method
Branch-and-bound method for solving IPs
Initialization: z∗ := −∞, B & B(P0 )
Procedure B & B(Pk )
1: Consider the continuous relaxation Rk of Pk
2: if Rk is infeasible then return
3: Calculate an optimal solution xk of Rk and its value zk
4: if zk ≤ z∗ then return
5: if xk is integer then
6: z∗ := zk ; s∗ := xk
7: else
8: Choose a variable xki ̸∈ N
9: P′k := Pk + {xi ≥ ⌊xki ⌋ + 1}
10: P′′k := Pk + {xi ≤ ⌊xki ⌋}
11: B & B(P′k )
12: B & B(P′′k )
13: end if
Solving integer linear programs Example using IP solver
Contents
1. Integer linear programs
Modeling examples
Formulations
2. Solving integer linear programs
2D graphical resolution
Branch-and-bound method
Example using IP solver
Solving integer linear programs Example using IP solver
Classical knapsack problem
Variables: xi = 1 if item i is chosen, = 0 otherwise
Formulation:
∑
n
max ci xi
i=1
∑
n
subject to wi xi ≤ W
i=1
xi ∈ {0, 1} ∀i = 1, . . . , n
Solving integer linear programs Example using IP solver
knapsack.dat as data file
# An instance of classical knapsack problem
# W
9
# i c_i w_i
1 3 2
2 7 4
3 2 1
4 8 3
5 4 6
Thanks
Thank you for your attention!
