Chuong 3

Integer Linear
Programming
Chapter 3
Integer Linear Programming
Contents
Mathematical Modeling Motivated Examples

Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Which Node to Select?
Rule of Fathoming
Software for ILP
Le Hong Trang, Nguyen An Khuong, Huynh Tuong Nguyen Problems and

Homeworks
Faculty of Computer Science and Engineering
HCMC University of Technology
3.1
Integer Linear
Contents Programming
1 Motivated Examples
Linear Classification Problem
Facility Location Problem
2 Linear and Integer Linear Programs Contents
Motivated Examples
3 Simplex Method for Solving LP Classification
Facility Location
4 Branch & Bound Method for Solving ILP Linear and Integer
Linear Programs
Numerical Example 1 – IP
Simplex Method
Numerical Example 2 – Binary IP Branch & Bound
Strategy and Steps Method
Numerical Example 1
Exercise: 0-1 Knapsack Problem Numerical Example 2
Strategy and Steps
5 Remarks on Branch & Bound Method Exercise: 0-1 KP
Remarks
How to Branch? How to Branch?
Which Node to Select? Which Node to Select?

Rule of Fathoming
Rule of Fathoming Software for ILP
Software for Integer Programming Problems and

Homeworks
6 Problems and Homeworks

3.2
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.3
Integer Linear
Linear Classification Programming
Statement
Given two sets of points in Rn , denoted by{x1 , . . . , xN } and
{y1 , . . . , yM }, we need to classify the points.
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Applications in Computer Science Remarks
How to Branch?
• Machine learning, Which Node to Select?

Rule of Fathoming
• Pattern recognition, Software for ILP
Problems and
• Data mining, Homeworks
• ...
3.4
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
n T
• Use a line (hyperplane in R ) a x + b = 0, hence the Branch & Bound
Method
followings must be satisfied: Numerical Example 1
Numerical Example 2
Strategy and Steps
T T
a xi + b > 0, i = 1, . . . , N and a yj + b < 0, j = 1, . . . , M. Exercise: 0-1 KP
Remarks
How to Branch?
• Since the strict inequalities are homogeneous in a and b, they Which Node to Select?
are feasible iff the set of nonstrict linear inequalities: Rule of Fathoming
Software for ILP
T T Problems and
a xi + b > 1, i = 1, . . . , N and a yj + b < −1, j = 1, . . . , M. Homeworks
3.5
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
• The classification is better if having ui , vj ≥ 0 such that: Numerical Example 1
Numerical Example 2
Strategy and Steps
T T
a xi + b > 1 − ui and a yj + b < −1 + vj , Exercise: 0-1 KP
Remarks
where i = 1, . . . , N and j = 1, . . . , M . How to Branch?

Rule of Fathoming
PN PM
• The best one should be at minimizer of i=1 ui + j=1 vj . Software for ILP
Problems and
Homeworks
3.6
Integer Linear
Classification for inseparable sets (SVM form)
N
X M
X
min ui + vj Contents
Motivated Examples
i=1 j=1
Classification
T
s.t. a xi + b ≥ 1 − ui , i = 1, . . . , N, Facility Location
Linear and Integer

T
a yi + b ≤ −1 + vi , j = 1, . . . , M, Linear Programs
Simplex Method
ui , vj ≥ 0, i = 1, . . . , N and j = 1, . . . , M. Branch & Bound
Method
or, in vector form Numerical Example 1
Numerical Example 2
Strategy and Steps
T T
min 1 u + 1 v Exercise: 0-1 KP
T Remarks
s.t. x a + 1b 1 − u, How to Branch?
y T a + 1b −1 + v, Rule of Fathoming
Software for ILP
u, v 0. Problems and
Homeworks
3.7
Integer Linear
Linear Classification: numerically solving Programming
n = 2;
randn ( ’ state ’ ,2);
N = 50; M = 50;
Y = [1.5+0.9* randn (1 ,0.6* N ) , 1.5+0.7* randn (1 ,0.4* N ); Contents
2*( randn (1 ,0.6* N )+1) , 2*( randn (1 ,0.4* N ) -1)]; Motivated Examples
Classification
X = [ -1.5+0.9* randn (1 ,0.6* M ) , -1.5+0.7* randn (1 ,0.4* M );
Facility Location
2*( randn (1 ,0.6* M ) -1) , 2*( randn (1 ,0.4* M )+1)];
Linear and Integer
T = [ -1 1; 1 1]; Linear Programs
Y = T*Y; X = T*X; Simplex Method
Branch & Bound

% S o lu t i o n via CVX Method
cvx_begin Numerical Example 1
Numerical Example 2
variables a ( n ) b (1) u ( N ) v ( M )
Strategy and Steps
minimize ( ones (1 , N )* u + ones (1 , M )* v ) Exercise: 0-1 KP
X ’* a + b >= 1 - u ;
Remarks
Y ’* a + b <= -(1 - v ); How to Branch?
u >= 0; Which Node to Select?
Rule of Fathoming
v >= 0;
Software for ILP
cvx_end
Problems and
Homeworks
3.8
Integer Linear
Linear Classification: numerically solving Programming
Approximate linear classification via linear programming

8
Contents
6
Motivated Examples
Classification
4 Facility Location
Linear and Integer

Linear Programs
2
Simplex Method
Branch & Bound

Method
0
Numerical Example 1
Numerical Example 2
Strategy and Steps
−2
Exercise: 0-1 KP
Remarks
−4 How to Branch?
Rule of Fathoming
−6 Software for ILP
Problems and
−8 −6 −4 −2 0 2 4 6 8 10 Homeworks
3.9
Integer Linear
Classification for inseparable sets (SVM form)
Contents
min 1T u + 1T v Motivated Examples
s.t. xT a + 1b 1 − u, Classification
Facility Location
y T a + 1b −1 + v, Linear and Integer

Linear Programs
u, v 0. Simplex Method
Branch & Bound

Question: if u = 0 and v = 0? Method
Numerical Example 1
Numerical Example 2
min 0 Strategy and Steps
Exercise: 0-1 KP
T
s.t. x a + 1b 0, Remarks
How to Branch?
y T a + 1b ≺ 0. Which Node to Select?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.10
Integer Linear
Uncapacitated Facility Location Programming
Statement
Given a set of supermarket locations, denoted by I, let J be the
set of candidate warehouse locations. The problem is to determine Contents
which locations among J should be used to construct a Motivated Examples
warehouses such that the total cost is minimum. Classification

Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Network resource allocation Problems and

Homeworks
3.11
Integer Linear
Uncapacitated Facility Location: variables and objective Programming
• A location j ∈ J is decided by

1 if j is chosen for a facility, Contents
xj =
0 otherwise. Motivated Examples
Classification
Facility Location
• The cost associated with constructing each warehouse: fj . Linear and Integer
Linear Programs
• The fraction of supply received by supermarket i from
Simplex Method
warehouse j: yij ≥ 0. Branch & Bound
Method
• The cost of transportation between candidate warehouse site Numerical Example 1
j and supermarket location i: cij . Numerical Example 2

Strategy and Steps
• The total cost: Exercise: 0-1 KP
Remarks
X XX How to Branch?
fj xj + cij yij . Which Node to Select?
Rule of Fathoming
j∈J j∈J i∈I
Software for ILP
Problems and
Homeworks
3.12
Integer Linear
Uncapacitated Facility Location: constraints Programming
Contents
• The sum of fraction from each warehouse for each Motivated Examples
supermarket: X
Classification
Facility Location
yij = 1, ∀i ∈ I. Linear and Integer

Linear Programs
j∈J
Simplex Method
• The warehouse works if it actually constructed: Branch & Bound

Method
Numerical Example 1
yij ≤ xj , ∀i ∈ I, j ∈ J. Numerical Example 2

Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.13
Integer Linear
Uncapacitated Facility Location: model Programming
X XX Contents
min fj xj + cij yij Motivated Examples

x Classification
j∈J j∈J i∈I
Facility Location
s.t. Linear and Integer

Linear Programs
X
yij = 1, ∀i ∈ I, (1) Simplex Method
Branch & Bound

j∈J Method
yij ≤ xj , ∀i ∈ I, j ∈ J, (2) Numerical Example 1

Numerical Example 2
yij ≥ 0, ∀i ∈ I, j ∈ J, (3) Strategy and Steps

Exercise: 0-1 KP
xj ∈ {0, 1}. (4) Remarks

How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.14
Integer Linear
Uncapacitated Facility Location: numerically solving Programming
% ILP model solved by CVX

cvx_begin Contents
% variables Motivated Examples
variable x ( n ) binary Classification
variable y (m , n ) binary Facility Location
% model Linear and Integer

Linear Programs
minimize ( buildingCost * x + sum ( sum ( servingCost .* y )))
subject to Simplex Method
for i = 1: m Branch & Bound

Method
sum ( y (i ,:)) == 1; Numerical Example 1
for j = 1: n Numerical Example 2
y (i , j ) <= x ( j ); Strategy and Steps
Exercise: 0-1 KP
end
end Remarks
How to Branch?
cvx_end Which Node to Select?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.15
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.16
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.17
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.18
Integer Linear
Linear Program (LP) Programming
• Recall the standard form of LP:
min cT x Contents
x
Motivated Examples
s.t. Classification
Facility Location
Ax = b, (5)
Linear and Integer
x ≥ 0, (6) Linear Programs
Simplex Method
n
where c ∈ R , A is an m × n matrix with full row rank, and Branch & Bound
Method
b ∈ Rm . Numerical Example 1
Numerical Example 2
• A polyhedron is a set of the form {x ∈ Rn |Bx ≥ d} for some Strategy and Steps
Exercise: 0-1 KP
matrix B. Remarks
• Let P ∈ Rn be a given polyhedron. A vector x ∈ P is an How to Branch?

extreme point of P if there does not exist y, z ∈ P , and Rule of Fathoming

Software for ILP
λ ∈ (0, 1) such that x = λy + (1 − λ)z. Problems and
Homeworks
3.19
Integer Linear
Linear Program in General form Programming
• General form of LP:

Contents
min cT x Motivated Examples
x
Classification
s.t. Facility Location
Linear and Integer

Ax = b, (7) Linear Programs
Cx ≤ d, (8) Simplex Method
Branch & Bound

x ≥ 0. (9) Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
Question How to Branch?
Is there any way to transform a general form to standard one? Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.20
Integer Linear
Integer Linear Program (ILP) Programming
• An integer linear program is a linear program where variables

are constrained to be integers.
min cT x
x Contents
s.t. Motivated Examples

Classification
Ax = b, (10) Facility Location
Linear and Integer

n
x ≥ 0 and x ∈ Z . (11) Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Question Numerical Example 2

Strategy and Steps
Why do we consider the problem with only equality constraints but Exercise: 0-1 KP
Remarks
not inequality ones? How to Branch?
Rule of Fathoming
Remark Software for ILP
Problems and
Often a mix is desired of integer and non-integer variables, called Homeworks
Mixed Integer Linear Programs (MILP).

3.21
Integer Linear
Basic Solutions and Extreme Points Programming
• Let S = {x ∈ Rn |Ax = b, x ≥ 0},the feasible set of LP. Since

A is full row rank, if the feasible set is not empty, then we
must m ≤ n. Without loss of generality, we assume that Contents
m < n. Motivated Examples

Classification
• Let A = (B, N ), where B is an m × m matrix with full rank, Facility Location
i.e., det(B) 6= 0. Then, B is called a basis. Linear and Integer

Linear Programs

xB Simplex Method
• Let x = . We have BxB + N xN = b. Setting xN = 0
xN −1
Branch & Bound
Method
−1 B b Numerical Example 1
gives xB = B b. x = is called a basic solution. xB Numerical Example 2

0 Strategy and Steps
is called basic variables, xN is called nonbasic variables. Exercise: 0-1 KP
Remarks
solution is also feasible, this is, B −1 b ≥ 0, then
• If thebasic How to Branch?
−1
B b Which Node to Select?
x= is said to be a basic feasible solution. Rule of Fathoming
0 Software for ILP
Problems and
Homeworks
3.22
Integer Linear
Basic Solutions and Extreme Points Programming
• x̂ ∈ S is an extreme point of S if and only if x̂ is a basic

feasible solution.
• Two extreme points are adjacent if they differ in only one Contents
Motivated Examples
basic variable. Classification
Facility Location
Theorem (Basic theorem of LP) Linear and Integer
Linear Programs
Consider the linear program min{cT x|Ax = b, x ≥ 0}. If S has at Simplex Method
least one extreme point and there exists an optimal solution, then Branch & Bound
there exists an optimal solution that is an extreme point. Method
Numerical Example 1
Numerical Example 2
• The feasible set of standard form linear program has at least Strategy and Steps
Exercise: 0-1 KP
one extreme point.
Remarks
• Therefore, we claim that the optimal value of a linear How to Branch?
program is either −∞, or is attained an extreme point (basic Rule of Fathoming
feasible solution) of the feasible set. Software for ILP
Problems and
Homeworks
3.23
Integer Linear
A Naive Algorithm for Solving Linear Program Programming
• Let min{cT x|Ax = b, x ≥ 0} be a bounded linear program.

m Contents
• Enumerate all bases B ∈ {1, 2, . . . , n}, = O(nm ), too
n Motivated Examples
many. Classification
Facility Location
−1
B b Linear and Integer
• Compute associated basic solution x = . Linear Programs
0
Simplex Method
• Return the one which has largest objective function value Branch & Bound
Method
among the feasible basic solutions. Numerical Example 1
• Running time is O(nm · m3 ). Numerical Example 2

Strategy and Steps
Exercise: 0-1 KP
Remarks
Question How to Branch?
Are there more efficient algorithms? Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.24
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.25
Integer Linear
Simplex Method Programming
• Simplex method was invented by George Dantzig

(1914–2005) (father of linear programming).
−1
B b
• Suppose we have a basic feasible solution x̂ = ,
0 Contents
A = (B, N ). Motivated Examples

Classification
xB Facility Location
• Let x ∈ S be any feasible solution of the LP. Let x =
xN Linear and Integer
Linear Programs

c
and c = B . Then, BxB + N xN = b and Simplex Method
cN Branch & Bound

Method
xB = B −1 b − B −1 N xN . We have Numerical Example 1
Numerical Example 2
Strategy and Steps
T
c x= cTB xB + cTN xN Exercise: 0-1 KP
= cTB B −1 b − cTB B −1 N xN + cTN xN Remarks

How to Branch?
cT x̂ + (cTN − cTB B −1 N )xN .

= Rule of Fathoming
Software for ILP
• Let rN = (cTN − cTB B −1 N ),

called reduced cost. If rN ≥ 0, Problems and
Homeworks
then cT x ≥ c x̂ and the current extreme point x̂ is optimal.

T
3.26
Integer Linear
• Otherwise, there must exist an ri < 0, we can let current

nonbasic variable xi become a basic one xi > 0 (entering Contents
variable). Motivated Examples

Classification
• Suitably choosing basic variable to become a nonbasic one Facility Location
(leaving variable), we can get a new basic feasible solution Linear and Integer
Linear Programs
whose objective value is less than that of the current basic Simplex Method
feasible solution x̂. Branch & Bound
Method
• Geometrically, the simplex method moves from one extreme Numerical Example 1
point to one of its adjacent extreme point. Numerical Example 2

Strategy and Steps
• Since there are only a finite number of extreme points, the Exercise: 0-1 KP
Remarks
method terminates finitely at an optimal solution or detects How to Branch?
that the problem is infeasible or it is unbounded. Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.27
Integer Linear
Geometry of Simplex Method Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.28
Integer Linear
• Step 0: Compute aninitial

basis B and the basic feasible
B −1 b
B −1 b solution x = .
0 Contents
• Step 1: if rN = (cT T −1
N − cB B N ) ≥ 0, stop, x is an optimal Motivated Examples
Classification
solution. Otherwise goto Step 2. Facility Location
• Step 2: Choose j satisfying cT T −1

i − cB B aj < 0, if Linear and Integer
Linear Programs
āj = B −1 aj ≤ 0, stop, the LP is infeasible. Otherwise, goto Simplex Method
Step 3. Branch & Bound

Method
• Step 3: compute the step size Numerical Example 1
Numerical Example 2
Strategy and Steps
b̄i b̄r Exercise: 0-1 KP
λ = min{ |āij > 0} =
āij ārj Remarks
How to Branch?
−1
B aj Rule of Fathoming
Let x := x + λdj , where dj = . goto Step 1. Software for ILP

ej Problems and
Homeworks
3.29
Integer Linear
Simplex Tableau Programming
Contents
xB xN rhs Motivated Examples
B N b Classification
cTB cTN
Facility Location
0
Linear and Integer
Linear Programs
It implies that Simplex Method
Branch & Bound

xB xN rhs Method
Numerical Example 1
I B −1 N B −1 b Numerical Example 2
cTN − cTB B −1 N −cTB B −1 b

Strategy and Steps
0 Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.30
Integer Linear
Simplex Method: An example Programming
• Consider the following LP
min − 7x1 − 2x2

x Contents
s.t. Motivated Examples

Classification
− x1 + 2x2 + x3 = 4, Facility Location
Linear and Integer

5x1 + x2 + x4 = 20, Linear Programs
2x1 + 2x2 − x5 = 7, Simplex Method
Branch & Bound

x ≥ 0. Method
Numerical Example 1
Numerical Example 2
• The initial tableau should be Strategy and Steps
Exercise: 0-1 KP
x1 x2 x3 x4 x5 rhs
Remarks
−1 2 1 0 0 4 How to Branch?
5 1 0 1 0 20 Which Node to Select?

Rule of Fathoming
2 2 0 0 −1 7 Software for ILP
−7 −2 0 0 0 0 Problems and
Homeworks
3.31
Integer Linear
Simplex Method: example (cont.) Programming
• Choose the initial basis to be B = (a1 , a3 , a4 ), we have basic

xB = (x1 , x3 , x4 )T . The simplex tableau is then
x1 x2 x3 x4 x5 rhs
0 3 1 0 − 12 7 12
1
0 −4 0 1 22 2 12 Contents
1 1 0 0 −2 3 12 Classification
0 5 0 0 − 2 24 12
7 Facility Location
Linear and Integer

• The basic feasible solution is Linear Programs
xB = (x1 , x3 , x4 )T = (3 12 , 7 12 , 2 12 )T . Simplex Method
Branch & Bound

• Since r5 = − 72 < 0, x5 is chosen entering variable. Method
Numerical Example 1
2 21
λ= 2 12
= 1, then x4 is leaving variable. The new basic Numerical Example 2
Strategy and Steps
variable should be xB = (x1 , x3 , x5 )T . The new tableau is Exercise: 0-1 KP
Remarks
obtained as below. How to Branch?
x1 x2 x3 x4 x5 rhs Which Node to Select?

Rule of Fathoming
11 1
0 5 1 5 0 8 Software for ILP
8 2
0 −5 0 5 1 1 Problems and
Homeworks
1 1
1 5 0 5 0 4
0 − 53 0 7
5 0 28
3.32
Integer Linear
Simplex Method: example (cont.) Programming
• Similarly, choose x2 as the entering variable, then

8 4
λ = min{ 11/5 , 1/5 } = 40
11 . Hence x3 is leaving variable.
Contents
Motivated Examples
Therefore, the tableau is Classification
x1 x2 x3 x4 x5 rhs Facility Location
5 1 40 Linear and Integer

0 1 11 11 0 11 Linear Programs
8 6 75
0 0 11 11 1 11
Simplex Method
1 2 36
1 0 − 11 11 0 11
Branch & Bound
Method
3 16 2
0 0 11 11 0 30 11 Numerical Example 1
Numerical Example 2
3 16

• Since rN = 11 , 11 ≥ 0, the current basic feasible solution Strategy and Steps
Exercise: 0-1 KP
75 T
x = 36 40

,
11 11 , 0, 0, 11 is optimal with the optimal value is Remarks
2
−30 11 . How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.33
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.34
Integer Linear
Branch & Bound Method – Introduction Programming
• This is the divide and conquer method. We divide a large

problem into a few smaller ones. This is the “branch” part. Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.35
Integer Linear

Motivated Examples
• The conquering part is done by estimate how good a solution Classification
we can get for each smaller problems. Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.35
Integer Linear

Motivated Examples
• To do so, we may have to divide the problem further, until we Linear and Integer
Linear Programs
get a problem that we can handle, that is the “bound” part. Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.35
Integer Linear

Motivated Examples
Linear Programs
• We will use the linear programming relaxation to estimate the Branch & Bound
Method
optimal solution of an integer programming. Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.35
Integer Linear

Motivated Examples
Linear Programs
• We will use the linear programming relaxation to estimate the Branch & Bound
Method
optimal solution of an integer programming. Numerical Example 1
Numerical Example 2
• For an integer programming model P, the linear programming Strategy and Steps
model we get by dropping the requirement that all variables Exercise: 0-1 KP
Remarks
must be integers is called the linear programming relaxation How to Branch?
of P. Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.35
Integer Linear
Numerical Example 1: Integer Programming Programming
Contents
max(Z = −x1 + 4x2 ) (12) Motivated Examples

Classification
Facility Location
Subject to Linear and Integer
−10x1 + 20x2 ≤ 22 (13) Linear Programs
Simplex Method
5x1 + 10x2 ≤ 49 (14) Branch & Bound
Method
x1 ≤ 5 (15) Numerical Example 1
Numerical Example 2
Strategy and Steps
xi ≥ 0, xi ∈ Z ∀i ∈ {1, 2} (16) Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.36
Integer Linear
Numerical Example 1 (cont’) : Linear programming relaxation Programming
With linear programming relaxation, we drop xi ∈ Z Contents
Motivated Examples
max(Z = −x1 + 4x2 ) (17) Classification
Facility Location

Linear Programs
−10x1 + 20x2 ≤ 22 (18) Simplex Method
Branch & Bound

5x1 + 10x2 ≤ 49 (19) Method
Numerical Example 1
x1 ≤ 5 (20) Numerical Example 2

Strategy and Steps
Exercise: 0-1 KP
xi ≥ 0 ∀i ∈ {1, 2} (21) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.37
Integer Linear
Numerical Example 1 (cont’) Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Optimal solution of relaxation is (3.8, 3) with Z = 8.2. Homeworks
3.38
Integer Linear
Numerical Example 1 (cont’): Linear programming relaxation Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Since optimal solution of relaxation is (3.8, 3), we consider two Rule of Fathoming
Software for ILP
cases: x1 ≥ 4 and x1 ≤ 3. Problems and
Homeworks
3.39
Integer Linear
Example 1 (cont’) – LP relaxation: x1 ≥ 4 Programming
Case x1 ≥ 4:
Contents
Classification
Subject to Facility Location
−10x1 + 20x2 ≤ 22 (23) Linear and Integer

Linear Programs
5x1 + 10x2 ≤ 49 (24) Simplex Method
Branch & Bound

x1 ≤ 5 (25) Method
Numerical Example 1
Numerical Example 2
x1 ≥ 4 (26) Strategy and Steps
Exercise: 0-1 KP
x2 ≥ 0 (27) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.40
Integer Linear
Numerical Example 1 (cont’) – LP relaxation:x1 ≥ 4 Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has optimal solution at (4, 2.9) with Z = 7.6. Rule of Fathoming

Software for ILP
Then we consider two cases: x2 ≥ 3 and x2 ≤ 2. Problems and
Homeworks
3.41
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: x1 ≥ 4, x2 ≥ 3 Programming
Case x1 ≥ 4, x2 ≥ 3:
Contents
Classification
Facility Location
Subject to
Linear and Integer
Simplex Method
5x1 + 10x2 ≤ 49 (30) Branch & Bound
Method
4 ≤ x1 ≤ 5 (31) Numerical Example 1
Numerical Example 2
Strategy and Steps
x2 ≥ 3 (32) Exercise: 0-1 KP
Remarks
has no feasible solution (5x1 +10x2 ≥ 50) so the IP has no How to Branch?
feasible solution either. Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.42
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: x1 ≥ 4, x2 ≤ 2 Programming
Case x1 ≥ 4, x2 ≤ 2: Contents
Motivated Examples
Facility Location

Linear Programs
Branch & Bound

5x1 + 10x2 ≤ 49 (35) Method
Numerical Example 1

Strategy and Steps
Exercise: 0-1 KP
0 ≤ x2 ≤ 2 (37) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.43
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: - x1 ≥ 4, x2 ≤ 2 Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has an optimal solution at (4, 2) with Z = 4. Rule of Fathoming
This is the optimal solution of the IP as well. Currently, the best Software for ILP
Problems and
value of Z for the original IP is Z = 4. Homeworks
3.44
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: x1 ≤ 3 Programming
Come back case x1 ≤ 3: Contents
Motivated Examples
Facility Location

Linear Programs
Branch & Bound

5x1 + 10x2 ≤ 49 (40) Method
Numerical Example 1

Strategy and Steps
Exercise: 0-1 KP
x2 ≥ 0 (42) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.45
Integer Linear
Numerical Example 1 (cont’): LP relaxation Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has an optimal solution at (3, 2.6) with Z = 7.4. Rule of Fathoming

Software for ILP
We branch out further to two cases: x2 ≥ 3 and x2 ≤ 2. Problems and
Homeworks
3.46
Integer Linear
Example 1 (cont’) – LP relaxation: x1 ≤ 3, x2 ≥ 3 Programming
Case x1 ≤ 3, x2 ≥ 3:
Contents
Classification
Facility Location
Subject to
Linear and Integer
Simplex Method
5x1 + 10x2 ≤ 49 (45) Branch & Bound
Method
Numerical Example 2
Strategy and Steps
x2 ≥ 3 (47) Exercise: 0-1 KP
Remarks
has no feasible solution (−10x1 +20x2 ≥ 30). How to Branch?
The IP has no solution either. Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.47
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: - x1 ≤ 3, x2 ≤ 2 Programming
Case x1 ≤ 3, x2 ≤ 2: Contents
Motivated Examples
Facility Location

Linear Programs
Branch & Bound

5x1 + 10x2 ≤ 49 (50) Method
Numerical Example 1

Strategy and Steps
Exercise: 0-1 KP
0 ≤ x2 ≤ 2 (52) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.48
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: x1 ≤ 3, x2 ≤ 2 Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has an optimal at (1.8, 2) with Z = 6.2. Rule of Fathoming

Software for ILP
We branch further with two cases: x1 ≥ 2 or x1 ≤ 1 Problems and
Homeworks
3.49
Integer Linear
Case x1 ≥ 2, x2 ≤ 2: Contents
Motivated Examples
Facility Location

Linear Programs
Branch & Bound

5x1 + 10x2 ≤ 49 (55) Method
Numerical Example 1

Strategy and Steps
Exercise: 0-1 KP
0 ≤ x2 ≤ 2 (57) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.50
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has an optimal at (2, 2), with Z = 6. Rule of Fathoming
Since this is better than the incumbent Z = 4 at (4, 2), this new Software for ILP
Problems and
integer solution is our current best solution. Homeworks
3.51
Integer Linear
Case x1 ≤ 1, x2 ≤ 2: Contents
Motivated Examples
Facility Location

Linear Programs
Branch & Bound

5x1 + 10x2 ≤ 49 (60) Method
Numerical Example 1

Strategy and Steps
Exercise: 0-1 KP
0 ≤ x2 ≤ 2 (62) Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.52
Integer Linear
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
has an optimal at (1, 1.6) with Z = 5.4. Rule of Fathoming
Then any integer solution in this region can not give us a solution Software for ILP
Problems and
with the value of Z greater than 5.4. This branch is fathomed. Homeworks
3.53
Integer Linear
Numerical Example 1 (cont’) – LP relaxation: conclusion Programming
Z=8.2 (3.8, 3) Contents
Motivated Examples
Classification
Facility Location
Z=7.6 (4, 2.9) (3, 2.6) Z=7.4 Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
NF (4, 3) Z=4 (4, 2) (3, 3) NF (1.8, 2) Z=6.2 Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
Z=6 (2, 2) Z=5.4 (1, 1.6) How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.54
Integer Linear
Numerical Example 2 – Binary IP Problem Programming
Contents
max(Z = 9x1 + 5x2 + 6x3 + 4x4 ) (63) Motivated Examples
Classification
6x1 + 3x2 + 5x3 + 2x4 ≤ 10 (64) Linear and Integer

Linear Programs
x3 + x4 ≤ 1 (65) Simplex Method
Branch & Bound

−x1 + x3 ≤ 0 (66) Method
Numerical Example 1
Numerical Example 2
−x2 + x4 ≤ 0 (67) Strategy and Steps
Exercise: 0-1 KP
xi ∈ {0, 1}. (68) Remarks

How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.55
Integer Linear
Numerical Example 2: LP Relaxation Programming
max(Z = 9x1 + 5x2 + 6x3 + 4x4 ) (69)

Subject to Contents
Motivated Examples
6x1 + 3x2 + 5x3 + 2x4 ≤ 10 (70) Classification
Facility Location
x3 + x4 ≤ 1 (71) Linear and Integer
Linear Programs
−x1 + x3 ≤ 0 (72) Simplex Method
Branch & Bound

−x2 + x4 ≤ 0 (73) Method
Numerical Example 1
xi ≤ 1, f or 1 ≤ i ≤ 4 (74) Numerical Example 2

Strategy and Steps
Exercise: 0-1 KP
0 ≤ xi (75)
Remarks
has optimal solution at ( 56 , 1, 0, 1) (why?-HW on Simplex How to Branch?

Method!) with Z = 16.5 Rule of Fathoming

Software for ILP
Has two branch, x1 = 0 or x1 = 1 Problems and
Homeworks
3.56
Integer Linear
Numerical Example 2 – LP Relaxation: x1 = 0 Programming
With x1 = 0, problem becomes

Contents
max(Z = 5x2 + 4x4 ) (76) Motivated Examples
Classification
Linear and Integer

Linear Programs
3x2 + 2x4 ≤ 10 Simplex Method
x3 + x4 ≤ 1 Branch & Bound

Method
−x2 + x4 ≤ 0 Numerical Example 1

Numerical Example 2
xi ∈ {0, 1} Strategy and Steps

Exercise: 0-1 KP
Remarks
has the optimal solution at (0, 1, 0, 1) with Z = 9. (Current best How to Branch?
solution) Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.57
Integer Linear
Numerical Example 2 – LP Relaxation: x1 = 1 Programming
With x1 = 1, the LP relaxation
max(Z = 9 + 5x2 + 6x3 + 4x4 ) (77)

Contents
Motivated Examples
Subject to Classification
Facility Location
3x2 + 5x3 + 2x4 ≤ 4 Linear and Integer

Linear Programs
x3 + x4 ≤ 1 Simplex Method
Branch & Bound

x3 ≤ 1 Method
Numerical Example 1
−x2 + x4 ≤ 0 Numerical Example 2
Strategy and Steps
xi ≤ 1 f or 2 ≤ i ≤ 4 Exercise: 0-1 KP
0 ≤xi Remarks
How to Branch?
has the optimal solution at (1, 0.8, 0, 0.8) with Z = 16.2 Rule of Fathoming
Software for ILP
Branch: x2 = 0 or x2 = 1 Problems and
Homeworks
3.58
Integer Linear
Numerical Example 2 – LP Relaxation: x1 = 1, x2 = 0 Programming
In this case, we have x4 = 0 as well
max(Z = 9 + 6x3 ) (78)

Contents
Motivated Examples
Facility Location
5x3 ≤ 4 Linear and Integer

Linear Programs
x3 ≤ 1 Simplex Method
Branch & Bound

0 ≤x3 Method
Numerical Example 1
Numerical Example 2
has the optimal solution at (1, 0, 0.8, 0) with Z = 13.8 Strategy and Steps
Branch: x3 = 0 or x3 = 1 Exercise: 0-1 KP
Remarks
• With x3 = 0 The optimal solution is (1, 0, 0, 0) with Z = 9 How to Branch?
(not better than current solution) Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.59
Integer Linear
In this case, we have x4 = 0 as well
max(Z = 9 + 6x3 ) (78)

Contents
Motivated Examples
Facility Location
5x3 ≤ 4 Linear and Integer

Linear Programs
x3 ≤ 1 Simplex Method
Branch & Bound

0 ≤x3 Method
Numerical Example 1
Numerical Example 2
has the optimal solution at (1, 0, 0.8, 0) with Z = 13.8 Strategy and Steps
Branch: x3 = 0 or x3 = 1 Exercise: 0-1 KP
Remarks
• With x3 = 0 The optimal solution is (1, 0, 0, 0) with Z = 9 How to Branch?
(not better than current solution) Which Node to Select?

Rule of Fathoming
Software for ILP
• With x3 = 1. Have no feasible solution
Problems and
Homeworks
3.59
Integer Linear
With x1 = 0, the LP relaxation

Contents
max(Z = 14 + 6x3 + 4x4 ) (79) Motivated Examples

Classification
Facility Location
Linear Programs
5x3 + 2x4 ≤ 1 Simplex Method
Branch & Bound

x3 + x4 ≤ 1 Method
Numerical Example 1
0 ≤ x3 ≤ 1 Numerical Example 2
Strategy and Steps
0 ≤ x4 ≤ 1 Exercise: 0-1 KP
Remarks
has the optimal solution at (1, 1, 0, 0.5) with Z = 16 How to Branch?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.60
Integer Linear
max(Z = 14 + 6x3 + 4x4 ) (80)
Contents
S.t. 5x3 + 2x4 ≤ 1 Motivated Examples
x3 + x4 ≤ 1 Classification
Facility Location
0 ≤ x3 ≤ 1 Linear and Integer

Linear Programs
0 ≤ x4 ≤ 1 Simplex Method
Branch & Bound

Method
Numerical Example 1
• With x3 = 0, Z = 16 is still feasible solution at (1, 1, 0, 0.5) Numerical Example 2

Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
⇒ The current best solution (1, 1, 0, 0) with Z = 14 is the Software for ILP
Problems and
optimal solution. Homeworks
3.61
Integer Linear
max(Z = 14 + 6x3 + 4x4 ) (80)
Contents
Facility Location

Linear Programs
Branch & Bound

Method
Numerical Example 1

Strategy and Steps
• With x4 = 0, (1, 1, 0, 0), Z = 14 (new optimal solution) Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Problems and
3.61
Integer Linear
max(Z = 14 + 6x3 + 4x4 ) (80)
Contents
Facility Location

Linear Programs
Branch & Bound

Method
Numerical Example 1

Strategy and Steps
• With x4 = 1, (1, 1, 0, 1) is not feasible Remarks

How to Branch?
Rule of Fathoming
Problems and
3.61
Integer Linear
max(Z = 14 + 6x3 + 4x4 ) (80)
Contents
Facility Location

Linear Programs
Branch & Bound

Method
Numerical Example 1

Strategy and Steps
• With x4 = 1, (1, 1, 0, 1) is not feasible Remarks

How to Branch?
• With x3 = 1, No feasible solution Which Node to Select?

Rule of Fathoming
Problems and
3.61
Integer Linear
Numerical Example 2 (cont’) – LP relaxation: conclusion Programming
(0, 1, 0, 1) Z=9
(1, 0, 0, 0) Z = 9 Contents
( 56 ,1,0,1) Z=16.5 (1, 0, 0.8, 0) Z=13.8

Motivated Examples
Classification
Facility Location
(1, 1, 1, 0) NF Linear and Integer

Linear Programs
(1, 0.8, 0, 0.8) Z = 16.2 Simplex Method
(1, 1, 0, 0) Z=14 Branch & Bound

Method
Numerical Example 1
(1, 1, 0, 0.5) Z=16 Numerical Example 2
Strategy and Steps
(1, 1, 0, 0.5) Z=16 (1, 1, 0, 1) NF Exercise: 0-1 KP
Remarks
(1, 1, 1, 0.5) NF How to Branch?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.62
Integer Linear
Branch & Bound: General Strategy Programming
• Solve the linear relaxation of the problem. If the solution is

Contents
integer, then we are done. Otherwise create two new Motivated Examples
subproblems by branching on a fractional variable. Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
• A node (subproblem) is not active when any of the following Linear and Integer
occurs: Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
Simplex Method
1 The node is being branched on;
Branch & Bound
Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
2 The solution is integral; Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
3 The subproblem is infeasible; Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
Numerical Example 2
4 You can fathom the subproblem by a bounding argument. Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
Numerical Example 2
4 You can fathom the subproblem by a bounding argument. Strategy and Steps
Exercise: 0-1 KP
• Choose an active node and branch on a fractional variable.
Remarks
Repeat until there are no active subproblems. How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.63
Integer Linear
Branch & Bound: Steps Programming
• Omitted the integrality constraints from the original problem

in order to obtain a relaxation. Thus a LP problem is
obtained and solve this LP problem. Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear

• Divide a problem into subproblems Motivated Examples

Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification
• Calculate the LP relaxation of a subproblem Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification
- The LP problem has no feasible solution, done; Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification

Linear Programs
- The LP problem has an integer optimal solution; done. Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification

Linear Programs
- Compare the optimal solution with the best solution we know Branch & Bound
(the incumbent). Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification

Linear Programs
Numerical Example 1
- The LP problem has an optimal solution that is worse than Numerical Example 2
the incumbent, done. Strategy and Steps

Exercise: 0-1 KP
In all the cases above, we know all we need to know about
Remarks
that subproblem. We say that subproblem is fathomed. How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.64
Integer Linear


Classification

Linear Programs
Numerical Example 1
- The LP problem has an optimal solution that is worse than Numerical Example 2
the incumbent, done. Strategy and Steps

Exercise: 0-1 KP
In all the cases above, we know all we need to know about
Remarks
that subproblem. We say that subproblem is fathomed. How to Branch?
- The LP problem has an optimal solution that are not all Which Node to Select?
Rule of Fathoming
integer, better than the incumbent. In this case we would Software for ILP
have to divide this subproblem further and repeat. Problems and

Homeworks
3.64
Integer Linear
Exercise: An 0-1 Knapsack Problem Instance Programming
• Consider the problem

Contents
max 8x1 + 11x2 + 6x3 + 4x4 Motivated Examples
x
Classification
s.t. Facility Location
Linear and Integer

5x1 + 7x2 + 4x3 + 3x4 ≤ 14, Linear Programs
x ∈ {0, 1}4 . Simplex Method
Branch & Bound

Method
• The linear relaxation solution is x = (1, 1, 0.5, 0) with a value Numerical Example 1
Numerical Example 2
of 22. The solution is not integral. Strategy and Steps
Exercise: 0-1 KP
• Choose x3 to branch. The next two subproblems will have Remarks
x3 = 0 and x3 = 1, respectively. How to Branch?
• ... Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.65
Integer Linear
Exercise: An 0-1 Knapsack Problem Instance Programming
• The tree search:

Contents
Z = 22 (1, 1, 0.5, 0)
Motivated Examples
Classification
Facility Location
Z = 21.65 (1, 1, 0, 0.67) (1, 0.71, 1, 0) Z = 21.85 Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Z = 18 (1, 1, 1, 1) (0.6, 1, 1, 0) Z = 21.8 Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Z = 21 (0, 1, 1, 1) (1, 1, 1, 0) NF Remarks

How to Branch?
• Theo ptimal solution is x = (0, 1, 1, 1). Which Node to Select?

Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.66
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.67
Integer Linear
How to Branch? Programming
• We want to divide the current problem into two or more

subproblems that are easier than the original. A commonly
used branching method:
Contents
xi ≤ bx∗i c, xi ≥ dx∗i e, Motivated Examples

Classification
Facility Location
where x∗i is a fractional variable. Linear and Integer
Linear Programs
• Which variable to branch? A commonly used branching rule:
Simplex Method
Branch the most fractional variable. Branch & Bound
Method
• We would like to choose the branching that minimizes the Numerical Example 1
sum of the solution times of all the created subproblems. Numerical Example 2
Strategy and Steps
• How do we know how long it will take to solve each Exercise: 0-1 KP
subproblem? Remarks
How to Branch?
• Answer: We don’t. Which Node to Select?
• Idea: Try to predict the difficulty of a subproblem. Rule of Fathoming

Software for ILP
• A good branching rule: The value of the linear programming Problems and
Homeworks
relaxation changes a lot.
3.68
Integer Linear
Which Node to Select? Programming
Contents
• An important choice in branch and bound is the strategy for Motivated Examples
Classification
selecting the next subproblem to be processed. Facility Location
• Goals: (i) Minimizing overall solution time; (ii) Finding a Linear and Integer
Linear Programs
good feasible solution quickly. Simplex Method
• Some commonly used search strategies: Branch & Bound

Method
• Best First, Numerical Example 1
Numerical Example 2
• Depth-First. Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.69
Integer Linear
The Best First Approach Programming
• One way to minimize overall solution time is to try to

Contents
minimize the size of the search tree. We can achieve this by
Motivated Examples
choosing the subproblem with the best bound (lowest lower Classification
bound if we are minimizing). Facility Location
Linear and Integer

• Drawbacks of Best First Linear Programs
• Doesn’t necessarily find feasible solutions quickly since Simplex Method
feasible solutions are “more likely” to be found deep in the Branch & Bound
Method
tree. Numerical Example 1
• Node setup costs are high. The linear program being solved Numerical Example 2
Strategy and Steps
may change quite a bit from one node evaluation to the next. Exercise: 0-1 KP
• Memory usage is high. It can require a lot of memory to store Remarks
the candidate list, since the tree can grow “broad”. How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.70
Integer Linear
The Depth-First Approach Programming
• The depth first approach is to always choose the deepest

node to process next. Just dive until you prune, then back up Contents
and go the other way. Motivated Examples

Classification
• This avoids most of the problems with best first: The number Facility Location
of candidate nodes is minimized (saving memory). The node Linear and Integer
Linear Programs
set-up costs are minimized. Simplex Method
• LPs change very little from one iteration to the next. Feasible Branch & Bound
Method
solutions are usually found quickly. Numerical Example 1
Numerical Example 2
• Drawback: If the initial lower bound is not very good, then we Strategy and Steps
may end up processing lots of non-critical nodes. Exercise: 0-1 KP
Remarks
• Hybrid Strategies: Go depth-first until you find a feasible How to Branch?
solution, then do best-first search. Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.71
Integer Linear
Rule of Fathoming Programming
Contents
A subproblem is fathomed when Motivated Examples

Classification
1 The relaxation of the subproblem has an optimal solution Facility Location
with z < z ∗ where z ∗ is the current best solution; Linear and Integer
Linear Programs
2 The relaxation of the subproblem has no feasible solution; Simplex Method
Branch & Bound

3 The relaxation of the subproblem has an optimal solution that Method
Numerical Example 1
has all integer values (or all binary if it is an BIP). Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.72
Integer Linear
Software for ILP Programming
• Matlab optimization toolbox: bintprog – a built-in function

Contents
for mixed integer linear programming. Motivated Examples
• Some of softwares which are proprietary but free for academic Classification
Facility Location
use:
Linear and Integer
• CPLEX: www-03.ibm.com/.../ibmilogcpleoptistud Linear Programs
• Gurobi: gurobi.com Simplex Method
• MOSEK: www.mosek.com Branch & Bound

Method
• SCIP: scip.zib.de Numerical Example 1
Numerical Example 2
These softwares can also be used as solvers in some modeling Strategy and Steps
tools. Exercise: 0-1 KP
Remarks
• Many open-source solvers were developed in the literature. How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.73
Integer Linear
Software for ILP: Modeling Tools Programming
• CVX: cvxr.com/cvx
Contents
• YALMIP: yalmip.github.io Motivated Examples
Classification
• TOMLAB: tomopt.com/tomlab Facility Location
Linear and Integer

Linear Programs
Questions
Simplex Method
Branch & Bound

• What is a modeling tool? Method
Numerical Example 1
• How does it work? Numerical Example 2
Strategy and Steps
• How do we use it? Exercise: 0-1 KP
Remarks
→ See the next slide for an example of the use of CVX. How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.74
Integer Linear
Example: Solving the Linear Classification Problem using CVX Programming
Statement
Contents
Given two sets of points in Rn , denoted by{x1 , . . . , xN } and
Motivated Examples
{y1 , . . . , yM }, we need to classify the points. Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.75
Integer Linear
Solving the Linear Classification Problem using CVX Programming
Contents
Classification for inseparable sets Motivated Examples

Classification
Facility Location
T T
min 1 u+1 u Linear and Integer
Linear Programs
s.t. aT xi + b ≥ 1 − ui , i = 1, . . . , N, Simplex Method
T Branch & Bound

a yi + b ≤ −1 + vi , i = 1, . . . , M, Method
Numerical Example 1
u, v 0. Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.76
Integer Linear
n = 2;
randn ( ’ state ’ ,2);
N = 50; M = 50;
Y = [1.5+0.9* randn (1 ,0.6* N ) , 1.5+0.7* randn (1 ,0.4* N ); Contents
2*( randn (1 ,0.6* N )+1) , 2*( randn (1 ,0.4* N ) -1)]; Motivated Examples
Classification
X = [ -1.5+0.9* randn (1 ,0.6* M ) , -1.5+0.7* randn (1 ,0.4* M );
Facility Location
2*( randn (1 ,0.6* M ) -1) , 2*( randn (1 ,0.4* M )+1)];
Linear and Integer
T = [ -1 1; 1 1]; Linear Programs
Y = T*Y; X = T*X; Simplex Method
Branch & Bound

% S o l u t i o n via CVX Method
cvx_begin Numerical Example 1
Numerical Example 2
variables a ( n ) b (1) u ( N ) v ( M )
Strategy and Steps
minimize ( ones (1 , N )* u + ones (1 , M )* v ) Exercise: 0-1 KP
X ’* a + b >= 1 - u ;
Remarks
Y ’* a + b <= -(1 - v ); How to Branch?
u >= 0; Which Node to Select?
Rule of Fathoming
v >= 0;
Software for ILP
cvx_end
Problems and
Homeworks
3.77
Integer Linear
Approximate linear classification via linear programming

8
Contents
6
Motivated Examples
Classification
4 Facility Location
Linear and Integer

Linear Programs
2
Simplex Method
Branch & Bound

Method
0
Numerical Example 1
Numerical Example 2
Strategy and Steps
−2
Exercise: 0-1 KP
Remarks
−4 How to Branch?
Rule of Fathoming
−6 Software for ILP
Problems and
−8 −6 −4 −2 0 2 4 6 8 10 Homeworks
3.78
Integer Linear
Outline Programming
Motivated Examples
Facility Location
Linear Programs
Simplex Method
Numerical Example 1
Strategy and Steps
Remarks

Rule of Fathoming

Homeworks

3.79
Integer Linear
Transportation Problem — Linear Programming Model Programming
Statement of an instance
Suppose a company has 2 factories F1 , F2 and 9 retail outlets
R1 , . . . , R9 :
• the total supply of the product from each factory F1 is ai ; Contents
• the total demand for the product at each outlet Rj is bj ; Motivated Examples
Classification
• The cost of sending one unit of the product from factory Fi Facility Location
Linear and Integer

to outlet Rj is equal to cij , Linear Programs
where i = 1, 2 and j = 1, 2, . . . , 9. Simplex Method
Branch & Bound

The problem is to determine a transportation scheme between the Method
factories and the outlets so as to minimize the total transportation Numerical Example 1
Numerical Example 2
cost, subject to the specified supply and demand constraints.. Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.80
Integer Linear
Transportation Problem — Linear Programming Model Programming
Statement of an instance
Suppose a company has 2 factories F1 , F2 and 9 retail outlets
R1 , . . . , R9 :
• the total supply of the product from each factory F1 is ai ; Contents
• the total demand for the product at each outlet Rj is bj ; Motivated Examples
Classification
• The cost of sending one unit of the product from factory Fi Facility Location
Linear and Integer

to outlet Rj is equal to cij , Linear Programs
where i = 1, 2 and j = 1, 2, . . . , 9. Simplex Method
Branch & Bound

The problem is to determine a transportation scheme between the Method
factories and the outlets so as to minimize the total transportation Numerical Example 1
Numerical Example 2
cost, subject to the specified supply and demand constraints.. Strategy and Steps
Exercise: 0-1 KP
Remarks
• Objective: minimum cost of transporting. How to Branch?
• Constraint: total supply of the factories and, total demand for Rule of Fathoming
Software for ILP
the product of the outlets.
Problems and
• Variable: the size of the shipment from Fi to Rj , where Homeworks
i = 1, 2 and j = 1, 2, . . . , 9.
3.80
Integer Linear
Transportation Problem: Mathematical Formulation Programming
• Variable: xij ≥ 0. Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.81
Integer Linear
Motivated Examples
• Objective Classification
• transportation cost from Fi to Facility Location
Rj : cij xij , P
Linear and Integer
Linear Programs
• objective function: ij cij xij . Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.81
Integer Linear
Motivated Examples
• Objective Classification
• transportation cost from Fi to Facility Location
Rj : cij xij , P
Linear and Integer
Linear Programs
• objective function: ij cij xij . Simplex Method
• Constraints Branch & Bound

Method
• total supply of Fi : Numerical Example 1
P9
j=1 xij ≤ ai ,
Numerical Example 2
Strategy and Steps
• total demand of Rj : Exercise: 0-1 KP
P2
i=1 xij ≥ bj . Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.81
Integer Linear
Transportation Problem: Mathematical Formulation (cont.) Programming
X
min cij xij Contents
x
ij Motivated Examples
Classification
subject to Facility Location
9 Linear and Integer

X Linear Programs
xij ≤ ai , i = 1, 2, (81) Simplex Method
j=1 Branch & Bound
Method
2
X Numerical Example 1
xij ≥ bj , j = 1, . . . , 9, (82) Numerical Example 2

Strategy and Steps
i=1 Exercise: 0-1 KP
xij ≥ 0, i = 1, 2, j = 1, . . . , 9. Remarks
How to Branch?
(83) Which Node to Select?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.82
Integer Linear
Mathematical Formulation Programming
Contents
Motivated Examples
Steps Classification
Facility Location
Linear and Integer

1 Define decision variables. Linear Programs
Simplex Method
2 Determine the objective function.
Branch & Bound
3 Establish constraints. Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.83
Integer Linear
Knapsack Problems — Integer Linear Programming Model Programming
There are many different knapsack problems. The first and

classical one is the binary knapsack problem.
Binary (0-1) knapsack problem
A tourist is planning a tour in the mountains. He has a lot of
Contents
objects which may be useful during the tour. For example ice pick Motivated Examples
and can opener can be among the objects. We suppose that Classification
Facility Location
• Each object has a positive value and a positive weight, the Linear and Integer
value is the degree of contribution of the object to the Linear Programs
Simplex Method
success of the tour;
Branch & Bound
Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.84
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
• The objects are independent from each other (e.g. can and Method
Numerical Example 1
can opener are not independent as any of them without the Numerical Example 2
other one has limited value); Strategy and Steps

Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.84
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
Numerical Example 1

Exercise: 0-1 KP
• The knapsack of the tourist is strong and large enough to Remarks

How to Branch?
contain all possible objects; Which Node to Select?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.84
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
Numerical Example 1

Exercise: 0-1 KP

How to Branch?
Rule of Fathoming
• The strength of the tourist makes possible to bring only a Software for ILP
limited total weight; Problems and

Homeworks
3.84
Integer Linear

Contents
Facility Location
Simplex Method
Branch & Bound
Numerical Example 1

Exercise: 0-1 KP

How to Branch?
Rule of Fathoming
• The strength of the tourist makes possible to bring only a Software for ILP
limited total weight; Problems and

Homeworks
• But within this weight limit the tourist want to achieve the
maximal total value.
3.84
Integer Linear
• The following notations are used to the mathematical

formulation of the problem:
n the number of objects;

j the index of the objects; Contents
wj the weight of object j; Motivated Examples

Classification
vj the value of object j; Facility Location
b the maximal weight what the tourist can bring. Linear and Integer
Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.85
Integer Linear



Classification
Linear Programs
• For each object j a so-called binary or zero-one decision Simplex Method
Branch & Bound

variable, say xj , is introduced: Method
Numerical Example 1
Numerical Example 2

1 if object j is present on the tour Strategy and Steps
xj =
0 if object j isn’t present on the tour. Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.85
Integer Linear



Classification
Linear Programs
• For each object j a so-called binary or zero-one decision Simplex Method
Branch & Bound

variable, say xj , is introduced: Method
Numerical Example 1
Numerical Example 2

1 if object j is present on the tour Strategy and Steps
xj =
0 if object j isn’t present on the tour. Exercise: 0-1 KP
Remarks
How to Branch?
• Notice that Which Node to Select?
Rule of Fathoming

wj if object j is present on the tour, Software for ILP
w j xj = Problems and
0 if object j isn’t present on the tour Homeworks
is the weight of the object in the knapsack.

3.85
Integer Linear
Mathematical Formulation (cont.) Programming
• Similarly vj xj is the value of the object on the tour. The

total weight in the knapsack is
n
X
vj x j Contents
j=1 Motivated Examples

Classification
Facility Location
which may not exceed the weight limit.
Linear and Integer
Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.86
Integer Linear
Mathematical Formulation (cont.) Programming
• Similarly vj xj is the value of the object on the tour. The

total weight in the knapsack is
n
X
vj x j Contents
j=1 Motivated Examples

Classification
Facility Location
which may not exceed the weight limit.
Linear and Integer
• Hence the mathematical form of the problem is as follows. Linear Programs
Simplex Method
n
X Branch & Bound
Method
max vj x j (84) Numerical Example 1
x
Numerical Example 2
j=1
Strategy and Steps
subject to Exercise: 0-1 KP
Remarks
n
X How to Branch?
wj xj ≤ b, (85) Which Node to Select?

Rule of Fathoming
j=1 Software for ILP
xj = 0 or 1, j = 1, . . . , n. (86) Problems and

Homeworks
3.86
Integer Linear
Solving the problem in this case Programming
• The difficulty of the problem is caused by the integrality

requirement. If constraint (86) is substituted by the relaxed
constraint, i.e. by
0 ≤ xj ≤ 1, j = 1, . . . , n , (87)
Contents
then the Problem (84), (85), and (87) is a linear Motivated Examples
programming problem. (87) means that not only a complete Classification
Facility Location
object can be in the knapsack but any part of it.
Linear and Integer
Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Theorem Numerical Example 2
Strategy and Steps
Suppose: vj , wj (j = 1, . . . , n)-all positive, and satisfies Exercise: 0-1 KP
Remarks
v1 v2 vn How to Branch?
≥ ··· ≥ . (88) Which Node to Select?
w1 w2 wn Rule of Fathoming
Software for ILP
Then there is an index p (1 ≤ p ≤ n) and an optimal sol. x∗ s.t. Problems and

Homeworks
x∗1 = x∗2 = · · · = x∗p−1 = 1, x∗p+1 = x∗p+2 = · · · = x∗p+1 = 0.

3.87
Integer Linear
Solving the problem in this case Programming
• The difficulty of the problem is caused by the integrality

requirement. If constraint (86) is substituted by the relaxed
constraint, i.e. by
0 ≤ xj ≤ 1, j = 1, . . . , n , (87)
Contents
then the Problem (84), (85), and (87) is a linear Motivated Examples
programming problem. (87) means that not only a complete Classification
Facility Location
object can be in the knapsack but any part of it.
Linear and Integer
• Moreover in this special case, it is not necessary to apply the Linear Programs
simplex method or any other LP algorithm to solve it, as its Simplex Method
optimal solution is described by Branch & Bound

Method
Numerical Example 1
Theorem Numerical Example 2
Strategy and Steps
Suppose: vj , wj (j = 1, . . . , n)-all positive, and satisfies Exercise: 0-1 KP
Remarks
v1 v2 vn How to Branch?
≥ ··· ≥ . (88) Which Node to Select?
w1 w2 wn Rule of Fathoming
Software for ILP
Then there is an index p (1 ≤ p ≤ n) and an optimal sol. x∗ s.t. Problems and

Homeworks
x∗1 = x∗2 = · · · = x∗p−1 = 1, x∗p+1 = x∗p+2 = · · · = x∗p+1 = 0.

3.87
Integer Linear
Remarks Programming
• Notice that there is only at most one non-integer component

in x∗ . This property will be used at the numerical calculations.
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.88
Integer Linear
Remarks Programming

• From the point of view of B&B the relation of the Problems
Contents
(84), (85), and (86) and (84), (85), and (87) is very
Motivated Examples
important. Any feasible solution of the first one is also feasible Classification
in the second one. But the opposite statement is not true. Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.88
Integer Linear
Remarks Programming

Contents
Motivated Examples
Linear and Integer

• In other words the set of feasible solutions of the first problem Linear Programs
is a proper subset of the feasible solutions of the second one. Simplex Method
This fact has two important consequences: Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.88
Integer Linear
Remarks Programming

Contents
Motivated Examples
Linear and Integer


Method
• The optimal value of the Problem (84), (85), and (87) is an Numerical Example 1
upper bound of the optimal value of the Problem (84), (85), Numerical Example 2
Strategy and Steps
and (86). Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.88
Integer Linear
Remarks Programming

Contents
Motivated Examples
Linear and Integer


Method
Strategy and Steps
• If the optimal solution of the Problem (84), (85), and (87) is Remarks
How to Branch?
feasible in the Problem (84), (85), and (86) then it is the Which Node to Select?
optimal solution of the latter problem as well. Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.88
Integer Linear
Remarks Programming

Contents
Motivated Examples
Linear and Integer


Method
Strategy and Steps
• If the optimal solution of the Problem (84), (85), and (87) is Remarks
How to Branch?
feasible in the Problem (84), (85), and (86) then it is the Which Node to Select?
optimal solution of the latter problem as well. Rule of Fathoming
Software for ILP
• These properties are used in the course of the branch and Problems and
bound method intensively. Homeworks
3.88
Integer Linear
Sudoku Game Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Problem statement Exercise: 0-1 KP
Given a grid of 9 × 9, the grid is divided into 9 subgrids of 3 × 3. Remarks

How to Branch?
Some cells of subgrids are filled by digits in {1, 2, . . . , 9}. The Which Node to Select?
objective is to fill remaining cells such that Rule of Fathoming

Software for ILP
• each column, each row, and each subgrid that compose the Problems and
Homeworks
grid, contain all of the digits from 1 to 9.
3.89
Integer Linear
Sudoku Game: Model Programming

1 if cell (i, j) contains k;
Variable xijk =
0 otherwise.
min 0T x Contents
x
Motivated Examples
subject to Classification
Facility Location
9
X Linear and Integer
xijk = 1, j, k = 1, . . . , 9, Linear Programs
i=1 Simplex Method
9
X Branch & Bound
Method
xijk = 1, i, k = 1, . . . , 9, Numerical Example 1
Numerical Example 2
j=1
Strategy and Steps
9
X Exercise: 0-1 KP
xijk = 1, i, j = 1, . . . , 9, Remarks
How to Branch?
k=1 Which Node to Select?
Rule of Fathoming
3q 3p
X X Software for ILP
xijk = 1, k = 1, . . . , 9; p, q = 1, 2, 3, Problems and
Homeworks
j=3q+2 i=3p+2
xijk ∈ {0, 1}, xijk = 1, ∀(i, j, k) ∈ G.

3.90
Integer Linear
Vehicle Routing Programming
Contents
Motivated Examples
Classification
Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.91
Integer Linear
Vehicle Routing Programming
Problem statement
Let G = (V, E) be a complete graph, where V = 0, . . . , n is the
set of vertices and E is the set of edges.
• We assume that vertex 0 denotes the depot, whereas vertex Contents
i = 1, . . . , n is customer. Motivated Examples
Classification
• A nonnegative value, denoted by cij , is the cost associated Facility Location
with each edge of G that connects vertex i and j. Linear and Integer
Linear Programs
• Let S ⊆ V , we denote by r(S) the minimum number of Simplex Method
vehicles required for all customers in S. Branch & Bound
Method
Given a positive integer number k, the capacitated vehicle routing Numerical Example 1
Numerical Example 2
problem is asked for seeking k simple routes that minimizing a Strategy and Steps
cost function of the sum of cost of edges of the routes, and Exercise: 0-1 KP
satisfying simultaneously: Remarks

How to Branch?
(i) each route starts at the depot vertex, Which Node to Select?
Rule of Fathoming
(ii) each customer belongs exactly one route, Software for ILP
Problems and
(iii) the sum of demands of the vertices visited by a route is Homeworks
always lower than the capacity C of the vehicle.

3.92
Integer Linear
Vehicle Routing: Model Programming
• We use xij ∈ {0, 1} to indicates if the edge connecting vertex

i and j, is an edge of the solution.
XX
min cij xij
x
i∈V j∈V Contents
Motivated Examples
subject to Classification
X Facility Location
xij = 1 for all j ∈ V \ {0}, Linear and Integer

Linear Programs
i∈V
X Simplex Method
xij = 1 for all i ∈ V \ {0}, Branch & Bound
Method
j∈V
Numerical Example 1
X Numerical Example 2
xi0 = k, Strategy and Steps
Exercise: 0-1 KP
i∈V
X Remarks
x0j = k, How to Branch?
j∈V Rule of Fathoming
XX Software for ILP
xij ≥ r(S) for all S ⊆ V \ {0}, S 6= ∅, Problems and
Homeworks
/ j∈S
i∈S
xij ∈ {0, 1} for all i, j ∈ V.

3.93
Integer Linear
Homeworks Programming
Contents
Motivated Examples
• Simplex Method: details. Classification

Facility Location
Linear and Integer

Linear Programs
Simplex Method
Branch & Bound

Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.94
Integer Linear
Contents
Motivated Examples

Facility Location
• Read carefully and do all Examples, Exercises in Chapter 7 of Linear and Integer
Linear Programs
[4]: F.R. Giordano, W.P. Fox and S.B. Horton, A First Course Simplex Method
in Mathematical Modeling, 5th ed., Cengage, 2014. Branch & Bound
Method
Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.94
Integer Linear
Contents
Motivated Examples

Facility Location
• Read carefully and do all Examples, Exercises in Chapter 7 of Linear and Integer
Linear Programs
[4]: F.R. Giordano, W.P. Fox and S.B. Horton, A First Course Simplex Method
in Mathematical Modeling, 5th ed., Cengage, 2014. Branch & Bound
Method
• Do all Exercises in the file named "BT Chương 3.pdf". Numerical Example 1
Numerical Example 2
Strategy and Steps
Exercise: 0-1 KP
Remarks
How to Branch?
Rule of Fathoming
Software for ILP
Problems and
Homeworks
3.94

Chuong 3

Uploaded by

Copyright:

Available Formats

Chuong 3

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chuong 3

Uploaded by

Copyright:

Available Formats

Integer Linear

Mathematical Modeling Motivated Examples

Linear and Integer

Branch & Bound

Le Hong Trang, Nguyen An Khuong, Huynh Tuong Nguyen Problems and

5 Remarks on Branch & Bound Method Exercise: 0-1 KP

Which Node to Select? Which Node to Select?

Software for Integer Programming Problems and

6 Problems and Homeworks

5 Remarks on Branch & Bound Method Exercise: 0-1 KP

Which Node to Select? Which Node to Select?

Software for Integer Programming Problems and

6 Problems and Homeworks

Linear and Integer

Branch & Bound

• Machine learning, Which Node to Select?

• Pattern recognition, Software for ILP

Linear and Integer

Linear and Integer

Branch & Bound

where i = 1, . . . , N and j = 1, . . . , M . How to Branch?

Classification for inseparable sets (SVM form)

Linear and Integer

Branch & Bound

Approximate linear classification via linear programming

Linear and Integer

Branch & Bound

−6 Software for ILP

Classification for inseparable sets (SVM form)

y T a + 1b  −1 + v, Linear and Integer

Branch & Bound

warehouses such that the total cost is minimum. Classification

Linear and Integer

Branch & Bound

Network resource allocation Problems and

j and supermarket location i: cij . Numerical Example 2

• The total cost: Exercise: 0-1 KP

yij = 1, ∀i ∈ I. Linear and Integer

• The warehouse works if it actually constructed: Branch & Bound

yij ≤ xj , ∀i ∈ I, j ∈ J. Numerical Example 2

min fj xj + cij yij Motivated Examples

s.t. Linear and Integer

Branch & Bound

yij ≤ xj , ∀i ∈ I, j ∈ J, (2) Numerical Example 1

yij ≥ 0, ∀i ∈ I, j ∈ J, (3) Strategy and Steps

xj ∈ {0, 1}. (4) Remarks

% ILP model solved by CVX

variable y (m , n ) binary Facility Location

% model Linear and Integer

for i = 1: m Branch & Bound

Linear and Integer

Branch & Bound

Linear and Integer

Branch & Bound

5 Remarks on Branch & Bound Method Exercise: 0-1 KP

Which Node to Select? Which Node to Select?

Software for Integer Programming Problems and

6 Problems and Homeworks

y T a + 1b −1 + v, Linear and Integer

• Step 0: Compute aninitial