Chapter 6

Integer Programming

Lecturer: Assoc. Prof. HO THANH PHONG

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Integer Programming

• A problem that is a LP except that the variables are required to

be integers, is called an Integer Program (IP)

• If only some of the variables must be integers, it is called a

Mixed Integer Program (MIP)

• If it contains only binary (0-1) variables it is called a Binary

Integer Program (BIP): pure BIP or mixed BIP problems.

Operations Research – Deterministic Model 2 Assoc. Prof. Hồ Thanh Phong

Properties of Integer Programming
• Type of Problems: Making “yes-or-no” type decisions

• Build a factory?
• Make Or Buy ?
• Doing a project or Not doing ?
• Fixed-Charge Problems
• Set Covering Problem

• Logical constraints

• Either-Or Constraints.
• If-Then Constraints

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Prototype Example:
California Manufacturing Company
• The California Manufacturing Company is a diversified company
with several factories and warehouses throughout California, but none
yet in Los Angeles or San Francisco.
• A basic issue is whether to build a new factory in Los Angeles or San
Francisco, or perhaps even both. Management is also considering
building at most one new warehouse, but will restrict the choice to a
city where a new factory is being built. Means that: building
warehouse in the city new factory built.
• There are two special points:
- Mutually exclusive alternatives: at most one warehouse
- Contingent decision: building warehouse in the city new factory built.

Objective: find the feasible combination of alternatives

that maximizes the net present value.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

• Formulating the model

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Prototype Example
Objective function: Max. Net Present Value Z

𝑀𝑎𝑥 𝑍 = 9𝑥1 + 5𝑥2 + 6𝑥3 + 4𝑥4

Subject to:

6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10 1 : Resource availability

𝑥3 + 𝑥4 ≤ 1 (2) : Mutual Exclusive decision
𝑥3 ≤ 𝑥1 (3): Contingent decision, decision 3 depend decision 1
𝑥4 ≤ 𝑥2 (4): Contingent decision, decision 4 depend decision 2

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

6
Prototype Example

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

7
Mô hình LINGO
MAX = 9*x1 + 5*x2 + 6*x3 + 4*x4;
6*x1 + 3*x2 + 5*x3 + 2*x4 <= 10;
X3 + x4 <=1;
x3 - x1 <= 0;
x4 - x2 <= 0;
@BIN(x1);
@BIN(x2);
@BIN(x3);
@BIN(x4);
Solution:
Global optimal solution found.
Objective value: 14.00000
Variable Value Reduced Cost
X1 1.000000 -9.000000
X2 1.000000 -5.000000
X3 0.000000 -6.000000
X4 0.000000 -4.000000

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Some Other Applications
• Investment Analysis
• Should we make a certain fixed investment?
• Site Selection
• Should a certain site be selected for the location of a new
facility?
• Designing a Production and Distribution Network
• Should a certain plant remain open? Should a certain site be
selected for a new plant? Should a distribution center remain
open? Should a certain site be selected for a new distribution
center? Should a certain distribution center be assigned to
serve a certain market area?

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Some Other Applications

• Dispatching Shipments
• Should a certain route be selected for a truck? Should a
certain size truck be used? Should a certain time period for
departure be used?
• Scheduling Interrelated Activities
• Should a certain activity begin in a certain time period?
• Scheduling Asset Divestitures
• Should a certain asset be sold in a certain time period?
• Airline Applications:
• Should a certain type of airplane be assigned to a certain
flight leg? Should a certain sequence of flight legs be
assigned to a crew?

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Modelling Either-Or constraint

• Assume there are two constraints

2𝑥1 + 3𝑥2 ≤ 10 (1) and 𝑥1 −4𝑥2 ≤ 5 (2) and only one must hold.
Let M > 0 is a very large positive number, we want:
2𝑥1 + 3𝑥2 ≤ 10 2𝑥1 + 3𝑥2 ≤ 10 + 𝑀
Either ൜ Or ൜
𝑥1 −4𝑥2 ≤ 5 + 𝑀 𝑥1 −4𝑥2 ≤ 5

We introduce a new auxiliary variable y (either 0 or 1), we have:

2𝑥1 + 3𝑥2 ≤ 10 + 𝑀𝑦 (1)

൜
𝑥1 −4𝑥2 ≤ 5 + 𝑀 1 − 𝑦 (2)

If y = 0, (1) hold, y = 1, (2) hold.

Modelling K out of N constraints

• Assume there are N constraints

𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏1 (1)
𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏2 (2)
...
𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏𝑁 (N)
Requirement: There are only K constraint hold.
Use big M and binary 𝑦𝑖 :
𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏1 + 𝑀𝑦1 (1)
𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏2 + 𝑀𝑦2 (2)
...
𝑓 𝑥1 , 𝑥2 … 𝑥𝑛 ≤ 𝑏𝑁 + 𝑀𝑦𝑁 (N) and add one more const. (N+1)
𝑁

෍ 𝑦𝑖 = 𝑁 − 𝐾 (N + 1)
𝑖=1
One value is chosen (function with N possible values)
Modeling Fixed-Charge Problems

If a product is produced, must incur a fixed setup cost C2 and a

variable cost.
Cost = C1x + C2
→The problem is non-linear.
x – quantity of product to be manufactured
x = 0 → cost = 0;
x > 0 → cost = C1x + C2
→How to model it? Using an indicator variable y
y = 1 → x is produced; y = 0 → x is not produced (x ≤ My)
Objective function becomes → Min (C1x + C2y)
Additional Constraint → x ≤ My; M is very large number.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Wyndor Glass Co. (original version)
• Two new products have been developed: Door and
WindowsWyndor has three production plants
– Production of the Door utilizes Plants 1 and 3
– Production of the Window utilizes Plants 2 and 3

• Objective is to find the optimal mix of these two new products.

Production Time Used for Each Unit Produced

Plant Doors Windows Available Per Week

1 1 hour 0 hour 4 hour

2 0 hour 2 hour 12 hour

3 3 hour 2 hour 18 hour

Unit Profit $300 $500

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh

15Phong
Wyndor Glass Co. with Setup Costs
(Variation 1)
Suppose that two changes are made to the original Wyndor
problem:
1.For each product, producing any units requires a substantial
one-time setup cost for setting up the production facilities.
2.The production runs for these products will be ended after
one week, so X1 and X2 in the original model now represent
the total number of doors and windows produced,
respectively, rather than production rates. Therefore, these
two variables need to be restricted to integer values.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Model Formulation
Let X1 = Number of doors to produce,
X2 = Number of windows to produce,
y1 = 1 if perform setup to produce doors; 0 otherwise,
y2 = 1 if perform setup to produce windows; 0 otherwise .

Maximize P = 300X1 + 500X2 – 700y1 – 1,300y2

subject to:
Original Constraints:
Plant 1: X1 ≤ 4
Plant 2: 2X2 ≤ 12
Plant 3: 3X1 + 2X2 ≤ 18
Produce only if Setup:
Doors: X1 ≤ My1
Windows: X2 ≤ My2
and
X1 ≥ 0, X2 ≥ 0, y1 and y2 are binary.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Lingo model and POM model
LINGO Model
MAX = 300*X1 + 500*X2 - 700*Y1 - 1300*Y2; Variable Value ReduceX1 Cost
X1 <= 4 ; X1 0.000000 -300.0000
X2 6.000000 -500.0000
2*X2 <= 12;
Y1 0.000000 700.0000
3*X1 + 2*X2 <= 18; Y2 1.000000 1300.000
X1 <= 10000*Y1;
X2 <= 10000 * Y2;
@BIN(Y1);
@BIN(Y2);
@GIN(X1);
@GIN(X2);

POM Model
Wyndor Glass Co. with Mutually Exclusive Products
(Variation 2)

Suppose that now the only change from the original Wyndor
problem is:
• The two potential new products (doors and windows) would
compete for the same customers. Therefore, management
has decided not to produce both of them together.
• At most one can be chosen for production,
so either X1 = 0 or W = 0, or both.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Model Formulation
Let X1 = Number of doors to produce,
X2 = Number of windows to produce,
y1 = 1 if produce doors; 0 otherwise,
y2 = 1 if produce windows; 0 otherwise.
Maximize P = 300X1 + 500W
subject to
Original Constraints:
Plant 1: X1 ≤ 4
Plant 2: 2X2 ≤ 12
Plant 3: 3X1 + 2X2 ≤ 18
Auxiliary variables must =1 if produce any:
Doors: X1 ≤ My1
Windows: X2 ≤ My2
Mutually Exclusive: y1 + y2 ≤ 1
and
X1 ≥ 0, X2 ≥ 0, y1 and y2 are binary.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Wyndor Glass Co. with Either-Or Constraints
(Variation 3)

Suppose that now the only change from the original Wyndor
problem is:
• The company has just opened a new plant (plant 4) that is
similar to plant 3, so the new plant can perform the same
operations as plant 3 to help produce the two new products
(doors and windows).
• However, management wants just one of the plants to be
chosen to work on these new products. The plant chosen
should be the one that provides the most profitable product
mix.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Data for Wyndor with Either-Or Constraints
(Variation 3)

Production Time Used for Production Time

Each Unit Produced (Hours) Available
Plant Doors Windows per Week (Hours)
1 1 0 4
2 0 2 12
3 3 2 18
4 2 4 28
Unit Profit $300 $500
Model Formulation
Let X1 = Number of doors to produce,
X2 = Number of windows to produce,
y = 1 if plant 4 is used; 0 if plant 3 is used
Maximize P = 300X1 + 500W
subject to:
Plant 1: X1 ≤ 4
Plant 2: 2X2 ≤ 12
Plant 3: 3X1 + 2X2 ≤ 18 + My
Plant 4: 2X1 + 4X2 ≤ 28 + M(1 – y)
and
X1 ≥ 0, X2 ≥ 0, y is binary.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Applications of Binary Variables
• Making “yes-or-no” type decisions
• Build a factory?
• Manufacture a product?
• Do a project?
• Assign a person to a task?
• Fixed costs
• If a product is produced, must incur a fixed setup cost.
• If a warehouse is operated, must incur a fixed cost.
• Either-or constraints
• Production must either be 0 or ≥ 100.
• Subset of constraints
• meet 3 out of 4 constraints.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Some special Integer Programming problems
• The Knapsack Problem (Bài toán xếp túi hành lý-ba-lô)
There are n things, thing j has profit pj. and weight wj, the bag weight is W. Select
thing through binary variable xj = 0 (not selecting) and và xj =1 (selecting).
Maximize σ𝑛𝑗=1 𝑝𝑗 𝑥𝑗
Subject to: σ𝑛𝑗=1 𝑤𝑗 𝑥𝑗 ≤ 𝑊

• Set Covering Problem (Bài toán tập bao phủ)

• Some devices will be installed. Each device covers an area. We need to
identify minimum number of devices to satisfy requirement. Example:
installing network of phone, network of pipeline water…

• Set Partitioning Problem

• The Traveling Salesman Problem

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Southwestern Airways Crew Scheduling

• Southwestern Airways needs to assign crews to cover all its

upcoming flights.
• We will focus on assigning 3 crews based in San Francisco
(SFO) to 11 flights.

Question: How should the 3 crews be assigned 3 sequences

of flights so that every one of the 11 flights is covered?

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Data for the Southwestern Airways Problem
Feasible Sequence of Flights (pairings)
Flights Leg 1 2 3 4 5 6 7 8 9 10 11 12
1. SFO–LAX 1 1 1 1
2. SFO–DEN 1 1 1 1
3. SFO–SEA 1 1 1 1
4. LAX–ORD 2 2 3 2 3
5. LAX–SFO 2 3 5 5
6. ORD–DEN 3 3 4
7. ORD–SEA 3 3 3 3 4
8. DEN–SFO 2 4 4 5
9. DEN–ORD 2 2 2
10. SEA–SFO 2 4 4 5
11. SEA–LAX 2 2 4 4 2
Cost, $1,000s 2 3 4 6 7 5 7 8 9 9 8 9

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Model Formulation
Let xj = 1 if flight sequence (pairing) j is assigned to a crew; 0 otherwise. (j = 1, 2, … , 12).
Minimize Cost = 2x1 + 3x2 + 4x3 + 6x4 + 7x5 + 5x6 + 7x7 + 8x8 + 9x9 + 9x10 + 8x11 + 9x12

subject to
pairings
Flight 1 covered: x1 + x4 + x7 + x10 ≥ 1
Flight 2 covered: x2 + x5 + x8 + x11 ≥ 1
: :
Flight 11 covered: x6 + x9 + x10 + x11 + x12 ≥ 1
Three Crews: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 ≤ 3
and
xj are binary (j = 1, 2, … , 12).

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

•Minimize Cost = 2x1 + 3x2 + 4x3 +6x4 +7x5 +5x6 +7x7 +8x8 + 9x9 + 9x10 + 8x11 + 9x12
subject to:
x1 + x4 + x7 + x10 ≥ 1 ; Flight 1: SFO–LAX
x2 + x5 + x8 + x11 ≥ 1 ; Flight 2: SFO–DEN
x3 + x6 + x9 + x12 ≥ 1 ; Flight 3: SFO–SEA
x4 + x7 + x9 + x10 + x12 ≥ 1 ; Flight 4: LAX-ORD
x1 + x6 + x10 + x11 ≥ 1 ; Flight 5: LAX-SFO
x4 + x5 + x9 ≥ 1 ; Flight 6: ORD-DEN
x7 + x8 + x10 + x11 + x12 ≥ 1; Flight 7: ORD-SEA
x2 + x4 + x5 + x9 ≥ 1 ; Flight 8: DEN-SFO
x5 + x8 + x11 ≥ 1 ; Flight 9: DEN-ORD
x3 + x7 + x8 + x12 ≥ 1 ; Flight 10: SEA-SFO
x6 + x9 + x10 + x11 + x12 ≥ 1; Flight 11: SEA-LAX
σ12
𝑗=1 𝑥𝑗 = 3 (three crew)

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

LINGO Model
Min = 2*x1 + 3*x2 + 4*x3 +6*x4 +7*x5 +5*x6 +7*x7 +8*x8 + 9*x9
+ 9*x10 + 8*x11 + 9*x12 ;
!subject to: ;
x1 + x4 + x7 + x10 >=1 ; ! Flight 1: SFO-LAX ;
x2 + x5 + x8 + x11 >=1 ; ! Flight 2: SFO-DEN;
x3 + x6 + x9 + x12 >=1 ; ! Flight 3: SFO-SEA;
x4 + x7 + x9 + x10 + x12 >=1 ; !Flight 4: LAX-ORD ;
x1 + x6 + x10 + x11 >=1 ; ! Flight 5: LAX-SFO;
x4 + x5 + x9 >=1 ; !Flight 6: ORD-DEN;
x7 + x8 + x10 + x11 + x12 >=1; !Flight 7: ORD-SEA;
x2 + x4 + x5 + x9 >=1 ; !Flight 8: DEN-SFO;
x5 + x8 + x11 >=1 ; !Flight 9: DEN-ORD;
x3 + x7 + x8 + x12 >=1 ; !Flight 10: SEA-SFO;
x6 + x9 + x10 + x11 + x12 >=1; !Flight 11: SEA-LAX ;
x1 + x2 + x3 +x4 +x5 +x6 +x7 +x8 + x9 + x10 + x11 + x12 = 3 ;

Solutions:
x3=1, x4 =1, x11=1; otherwise xij=0
Integer Programming Part 2

B&B Algorithm

Lecturer: Assoc. Prof. HO THANH PHONG

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Solving Integer Programming problem
A. Principle of Branch-And-Bound Algorithm
• We have Solution Space; we don’t know where is optimal value O.
We have to find out point O by apply principle divide-and-conquer.
• Algorithm consists of two steps and repeated: Branching and
Bounding
• Branching: use relevant methods and techniques, number of
branches may be > 2
• Bounding: Finding an upper limit for Maximization problem and
a lower limit for Minimize problem
• Maximization: Upper 𝐵𝑜𝑢𝑛𝑑 𝑘 ≥ 𝑂𝑝𝑡𝑖. 𝑣𝑎𝑙𝑢𝑒 𝑂
• Minimization: Lower 𝐵𝑜𝑢𝑛𝑑 𝑘 ≤ 𝑂𝑝𝑡𝑖. 𝑣𝑎𝑙𝑢𝑒 𝑂
SS
1 Solution
x x
x
x
O?

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Solving Integer Programming problem (Contd.)
A. Principle of Branch-Anh-Bound Algorithm) (TT)
• Selecting Branch
• Maximization: Select branch has largest Bound
• Minimization: Select branch has smallest Bound
• Not selecting branch that is infeasible
• Not selecting branch that bound is worst than the current best (incumbent).
Example: Bài toán Maximization, there are 2 branches, each with Bound as B1=10 and
B2=15. Now we're going to choose branch 2 and we don't need to look at branch 1
anymore. If you don't choose branch 2, what happens?
SS, Maximization
Selected branch
Bound
B1 = 10
B2 = 15
O?

• Choose a branch and continue the branching process, find bound, select the branch
until the optimal solution is identified.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Solving Mixed Integer Programming problem (Contd.)
A. Algorithm Branch-And-Bound (contd.)
1. Iteration 0:
- Distinguish remaining problem is the current solving problem, fathomed problem is the
confirmed and clear problem, is not need to be further considered.
- First, solve the relaxation problem: Solve the original problem with relaxation constraints:
eg. delete integer constraints.
• If no Solution then Stop, the relaxation have no solution means the original problem have
no solution.
• If there is a solution that satisfies the integer condition, stopped, the problem has been
confirmed (fathomed). If the integer condition is not met, then continue.

2. Branching
In the remaining problems, selecting the branching variable is the first variable in the list
that does not meet the integer conditions, 𝑥𝑗 , value is 𝑥𝑗∗ , integer part is 𝑥𝑗∗ . Divide into
2 branches by creating 2 sub-problems BT1 and BT2

- BT1: original constraints and adding constraint 𝒙𝒋 ≤ 𝒙∗𝒋

- BT2: original constraints and adding constraint 𝒙𝒋 ≥ 𝒙∗𝒋 + 𝟏

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Solving Mixed Integer Programming problem (Contd.)
A. Algorithm Branch-And-Bound (contd.)
3. Bounding: For each new subproblem, obtain its bound by applying the
simplex method to its LP relaxation and using the value of Z for the resulting
optimal solution.
4. Fathoming: For each new subproblem, apply the three fathoming tests
given below, and discard those subproblems that are fathomed by any of the
tests.
Test 1: Its bound ≤ Z*, where Z* is the value of Z for the current optimal
incumbent.
Test 2: Its LP relaxation has no feasible solutions.
Test 3: The optimal solution for its LP relaxation has integer values for the
integer-restricted variables. If this solution is better than the incumbent, it
becomes the new incumbent and test 1 is reapplied to all unfathomed
subproblems with the new larger Z*.

Optimal conditions: The program stops when there are no more unconfirmed
sub-problems. Value of incumbents are the optimal value.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Solving Mixed Integer Programming problem (Contd.)
A. Algorithm Branch-And-Bound (contd.)
Example Branch And Bound Algorithm
Original
problem
Incumbent
Z*

Sub Sub
problem 1 problem 2

Bound B1 Bound B2
B2 < Z*: fathomed

B11 > B12 Sub Sub

problem 11 problem 12 B12 > Z*: new incumbent
Bound B11 Bound B12 Z* = B12
Z*=B12

B111 > Z* Sub Sub

New incumbent problem 111 problem 112 B112 < Z*
Bound Bound
B111 B112
Fathomed
Solving Mixed Integer Programming problem (Contd.)
B. Example MIP problem
A MIP is given
Max. Z = 4𝑥1 − 2𝑥2 + 7𝑥3 − 𝑥4
Sub. to:
𝑥1 +5𝑥3 ≤ 10;
𝑥1 + 𝑥2 − 𝑥3 ≤1;
6𝑥1 −5𝑥2 ≤0;
−𝑥1 + 2𝑥3 − 2𝑥4 ≤ 3;
𝑥1 , 𝑥2 , 𝑥3 : 𝑖𝑛𝑡𝑒𝑔𝑒𝑟
𝑥4 : 𝑟𝑒𝑎𝑙

Iteration 0: Solve the original problem with relaxation constraints: delete integer
constraints
Solutions: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1.25, 1.5, 1.75, 0), Z= 14.25; Let Z* = -∞.
Because solution 𝑥1 , 𝑥2 , 𝑥3 are not satisfied integer condition➔ Not fathomed, continue.
Iteration 1:
Select branching variable is 𝑥1 . Current value 𝑥1 =1.25, 𝑥1 = 1 create two sub-problems
BT1 and BT2
- BT1: Original problem + constraint 𝑥1 ≤ 1
- BT2: Original problem + constraint 𝑥1 ≥ 2

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Giải bài toán Qui hoạch Nguyên (TT)
- BT1: Original problem + constraint 𝑥1 ≤ 1. Solutions (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 1.2, 1.8, 0), Z
= 14.2 = Bound B1.
- BT2: Original problem + constraint 𝑥1 ≥ 2, infeasible. Delete this branch (fathomed)
Iteration 2:
Select 𝑥2 is branching variable, value 𝑥2 = 1.2, branching two sub-problem BT11 and BT12
- BT11: Original problem + (𝑥1 ≤ 1) + (𝑥2 ≤ 1). Solutions (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 1, 1.83,
0), Z = 14.17 = Bound B11. Not satisfy integer condition, B11 > Z* ➔ not fathomed.
- BT12: Original problem + (𝑥1 ≤ 1) + (𝑥2 ≥ 2). Solutions (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 2, 1.83,
0), Z = 12.17 = Bound B12. Not satisfy integer condition, B11 > Z* ➔ not fathomed.
We select branch BT11 to continue because Bound B11 > Bound B12.

Iteration 3:
Select 𝑥3 is branching variable, value 𝑥3 = 1.83, branching two sub-problem BT111 and
BT112
- BT111: Original problem + (𝑥1 ≤ 1) + (𝑥2 ≤ 1) + (𝑥3 ≤ 1). Give a solution
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 1, 1, 0), Z = 8.33 = Bound B111. Not satisfy integer condition,
B111 > Z* ➔ not fathomed.
- BT112: Original problem + (𝑥1 ≤ 1) + (𝑥2 ≤ 1) + (𝑥3 ≥ 2). Give a solution
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0, 0, 2, 0.5), Z = 13.5. Satisfy integer condition, Z*=13.5 incumbent.
Stop because it reaches optimal condition, this is final solution of the problem.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Giải bài toán Qui hoạch Nguyên (TT)
Example Branch And Bound Algorithm
Original
problem
Incumbent
Z*=− ∞

Sub
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 1.2, 1.8, 0) problem Sub
Z = 14.2 = Bound B1. BT1 problem 2 Infeasible
𝑥1 ≤ 1 𝑥1 ≥ 2

Sub Sub
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 1, 1.83, 0) problem 11
Z = 14.17 = Bound B11. problem 12 (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 2, 1.83, 0)
𝑥1 ≤ 1 𝑥1 ≤ 1 Z = 12.17 = Bound B12.
B11 > B12 ➔ Select branch 11 𝑥2 ≤ 1 𝑥2 ≥ 2

(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0.83, 1, 1, 0) Sub problem Sub problem 112

Z = 8.33 = Bound B111 111 (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0, 0, 2, 0.5)
𝑥1 ≤ 1
𝑥1 ≤ 1 𝑥2 ≤ 1 Z = 13.5 = Z*. Optimal !
𝑥2 ≤ 1 𝑥3 ≥ 2
𝑥3 ≤ 1
Solving Mixed Binary Integer Programming (BIP) problem

B. Example Branch-And-Bound to solve Mixed BIP (includes binary & real variables).
A Mixed BIP is given
Max. Z = 4𝑥1 + 2𝑥2 + 7𝑥3 − 2𝑥4
Ràng buộc:
𝑥1 +5𝑥3 ≤ 5;
𝑥2 + 𝑥3 ≤2;
3𝑥1 +3𝑥2 +5𝑥3 ≤8;
−𝑥1 + 3𝑥3 − 2𝑥4 ≤ 2;
𝑥1 , 𝑥2 , 𝑥3 : 𝑏𝑖𝑛𝑎𝑟𝑦
𝑥4 : 𝑟𝑒𝑎𝑙

Iteration 0: Solve the original problem with relaxation constraints: delete binary integer
constraints
Solution: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1.5, 0, 0.7, 0), Z= 10.9; Let Z* = -∞.
Because 𝑥1 , 𝑥2 , 𝑥3 not satisfying integer conditions ➔ Not fathomed, continue.

Iteration 1: Because binary values, we create two branches only with x = 0 and x = 1.
Select branching variable is 𝑥1 . Current value is 𝑥1 =1.5, creating 2 sub-problems BT1 & BT2
- BT1: submit 𝑥1 = 1 into original problem.
- BT2: submit 𝑥1 = 0 into original problem
Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong
Giải bài toán Qui hoạch Nguyên (TT)
BT1 (𝑥1 = 1):
Max. Z = 4 + 2𝑥2 + 7𝑥3 − 2𝑥4
Ràng buộc:
5𝑥3 ≤ 4;
𝑥2 + 𝑥3 ≤2;
3𝑥2 +5𝑥3 ≤ 5;
3𝑥3 − 2𝑥4 ≤ 3;
𝑥2 , 𝑥3 : 𝑏𝑖𝑛𝑎𝑟𝑦; 𝑥4 : 𝑟𝑒𝑎𝑙
Lời giải relaxation, bỏ điều kiện binary: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 0.33, 0.8, 0)
Z = 6.27+4 = 10.27 = Bound B1.
BT2 (𝑥1 = 0):
Max. Z = 2𝑥2 + 7𝑥3 − 2𝑥4
Ràng buộc:
5𝑥3 ≤ 5;
𝑥2 + 𝑥3 ≤2;
3𝑥2 +5𝑥3 ≤8;
3𝑥3 − 2𝑥4 ≤ 2;
𝑥2 , 𝑥3 : 𝑏𝑖𝑛𝑎𝑟𝑦; 𝑥4 : 𝑟𝑒𝑎𝑙
Lời giải relaxation, bỏ điều kiện binary: (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0, 1, 1, 0.5), Z = 8. Lời giải này
thỏa điều kiện binary nên là lời giải tối ưu hiện tại (incumbent), Z* =8 (nhánh này xác
nhận - fathomed).
Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong
Giải bài toán Qui hoạch Nguyên (TT)
Selec branch BT1 for branching. Select 𝑥2 as branching variable; Two branches:
BT11: BT1 + 𝑥2 = 1 and BT12: BT1 + 𝑥2 = 0.

BT11 (𝑥1 = 1, 𝑥2 = 1):

Max. Z = 6 + 7𝑥3 − 2𝑥4
Subject to:
5𝑥3 ≤ 4; Solution of relaxation problem, delete binary:
𝑥3 ≤ 1; (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 1, 0.4, 0)
5𝑥3 ≤ 2; Z = 6+2.8 = 8.8 = Bound B11.
3𝑥3 − 2𝑥4 ≤ 3;
𝑥3 : 𝑏𝑖𝑛𝑎𝑟𝑦; 𝑥4 : 𝑟𝑒𝑎𝑙

BT12 (𝑥1 = 1, 𝑥2 = 0):

Solution of relaxation problem, delete binary :
Max. Z = 4 + 7𝑥3 − 2𝑥4
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 0, 0.8, 0)
Subject to :
Z = 4+5.6 = 9.6 = Bound B12.
5𝑥3 ≤ 4;
𝑥3 ≤2;
Because both 2 branched not fathomed and Bound
5𝑥3 ≤5;
B12 > Bound B11, select branch BT12 to continue.
3𝑥3 − 2𝑥4 ≤ 3;
𝑥3 : 𝑏𝑖𝑛𝑎𝑟𝑦; 𝑥4 : 𝑟𝑒𝑎𝑙

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Giải bài toán Qui hoạch Nguyên (TT)
Select branch BT12 for branching. Select 𝑥3 as branching variable; Two branched :
BT121: BT11 + 𝑥3 = 1 and BT122: BT12 + 𝑥3 = 0.

BT121 (𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 1):

Max. Z = 11 − 2𝑥4
Subject to :
5𝑥3 ≤ 4; Infeasible.
𝑥3 ≤2;
5𝑥3 ≤5;
3𝑥3 − 2𝑥4 ≤ 3;
𝑥4 : 𝑟𝑒𝑎𝑙;

BT122 (𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 0):

Max. Z = 4 − 2𝑥4 Solution (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (1, 0, 0, 0)
Subject to : Z = 4. Bound B122 = 4. Vì B122 < Z* = 8: fathomed
−2𝑥4 ≤ 3;
𝑥4 : 𝑟𝑒𝑎𝑙
Because both two branched have fathomed, stop. Optimal solution for current problem is
incumbent Z* =8 corresponding (𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) = (0, 1, 1, 0.5).

With the Pure BIP problem, the solving procedure is the same as this algorithm.

Operations Research – Deterministic Model Assoc. Prof. Hồ Thanh Phong

Exercises
Text book: Introduction to Operations Research. F. Hillier & G. Lierberman.
Page 534
12.1- 1, 2, 4, 6
12.3- 1, 2, 3, 4, 5
12.4- 1, 5, 6, 7
12.5- 2, 3, 4
12.6- 2, 3
12.7- 2, 3, 7, 9, 10