Operations Research Ch02

Shiqian Ma, SEEM 3440, Dept.
of SEEM, CUHK
Chapter 2
Integer Programming
Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK
2.1. Introduction
In many practical applications, some decision variables actually
make sense only if they have integer values.
For example, it is often necessary to assign people, machines, and
vehicles to activities in integer quantities.
Integer programming (IP) problems /
integer linear programming (ILP) problems /
linear integer programming (LIP) problems
are linear programming (LP) problems in which some or all the
decision variables are restricted to integer (or discrete) values.
2.1.1. Binary Integer Programming (BIP)

Problem / 0-1 Integer Programming
Problem
IP problems that contain only binary variables / 0-1 variables.
Binary variable:
xj =
1, if decision j is yes,
0, if decision j is no.
Example 2.1 (Assignment Problem).

Assignee
Task
c11 = 1
s1 = 1
Machine 1
c14 = 3
s2 = 1
c12 = 4
Job 1
d1 = 1
Job 2
d2 = 1
Job 3
d3 = 1
Job 4
d4 = 1
c13 = 6
c21 = 9
c22 = 7
Machine 2
c23 = 10
c24 = 9
c31 = 4
s3 = 1
Machine 3
c33 = 11
c34 = 7
c41 = 8
s4 = 1
c32 = 5
Machine 4
c42 = 7
c43 = 8
c44 = 5
s1 + s2 + s3 + s4 = 4
d1 + d2 + d3 + d4 = 4
Let z = total cost.

For i = 1, 2, 3, 4 and j = 1, 2, 3, 4, let
xij =
1, if machine i is assigned to do job j,

0, otherwise.
The IP model is:

Minimize z = x11 + 4x12 + 6x13 + 3x14
+ 9x21 + 7x22 + 10x23 + 9x24
+ 4x31 + 5x32 + 11x33 + 7x34
+ 8x41 + 7x42 + 8x43 + 5x44
subject to
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
xij = 0 or 1, for all i and j.
(Cost)
(Machine
(Machine
(Machine
(Machine
(Job 1)
(Job 2)
(Job 3)
(Job 4)
1)
2)
3)
4)
2.1.2. Pure Integer Programming (PIP) Problem

All decision variables are required to have integer values.
Example 2.2 (Transportation Problem).

Source
Destination
c11 = 10
s1 = 15
d1 = 5
Shop 2
d2 = 15
Shop 3
d3 = 15
Shop 4
d4 = 15
c12 = 2
Factory 1
c14 = 11
s2 = 25
Shop 1
c13 = 20
c21 = 12
c22 = 7
Factory 2
c23 = 9
c24 = 20
c31 = 4
c32 = 14
s3 = 10
Factory 3
c33 = 16
c34 = 18
s1 + s2 + s3 = 50
d1 + d2 + d3 + d4 = 50
Let z = total cost.

Let xij = number of units transport from source i to destination j,
for i = 1, 2, 3 and j = 1, 2, 3, 4.
The IP model is:
Minimize z = 10x11 + 2x12 + 20x13 + 11x14
+ 12x21 + 7x22 + 9x23 + 20x24
+ 4x31 + 14x32 + 16x33 + 18x34 (Cost)
subject to
x11 + x12 + x13 + x14 = 15
(Factory 1)
x21 + x22 + x23 + x24 = 25
(Factory 2)
x31 + x32 + x33 + x34 = 10
(Factory 3)
x11 + x21 + x31 = 5
(Shop 1)
x12 + x22 + x32 = 15
(Shop 2)
x13 + x23 + x33 = 15
(Shop 3)
x14 + x24 + x34 = 15
(Shop 4)
xij 0, integer, for all i and j
10
2.1.3. Mixed Integer Programming (MIP)

Problem
Only some of the decision variables are required to have integer
values (so the divisibility assumption holds for the rest).
Example 2.3.
Maximize z = 4x1 2x2 + 7x3 x4
subject to
x1
+ 5x3
x1 + x2 x3
6x1 5x2
x1
+ 2x3 2x4
xj 0, for j = 1, 2, 3, 4
x1, x2, x3 integers.
10
1
0
3
11
2.2. Some Perspectives on Solving IP

Problems
2.2.1. IP Problems Are Hard to Solve
IP problems are, in general, much more difficult to solve than LP
problems, because
We are able to characterize the optimal solutions to LP problems:
Primal feasible
Dual feasible
Complementary slackness
With IP, no such characterization exists.
12
2.2.2. Approximation
Some IP problems with general integer variables can be approximated by LP problems.
Example 2.4. IP Problem:
Maximize z =
subject to
5x1 + 4x2
x1 + x2 5
10x1 + 6x2 45
x1 0, x2 0
x1, x2 integers.
13
By ignoring integrality restrictions, we have the following

LP Relaxation Problem:
Maximize z =
subject to
5x1 + 4x2
x1 + x2 5
10x1 + 6x2 45
x1 0, x2 0.
The optimal solution to the LP relaxation problem is

(x1 , x2 ) = (3.75, 1.25) with z = 23.75.
14
By rounding up or down of the above solution, we have the following

close-to-optimal solutions:
x1
3
3
4
4
x2 Feasible? z
1
Yes
19
2
Yes
23 *
1
No
2
No
Question: Is the solution (x1, x2) = (3, 2) with z = 23 optimal or

only close-to-optimal?
15
However, the solutions of many IP problems cannot be approximated by the solutions of the corresponding LP relaxation problems.
1. Integrality conditions cannot be ignored for IP problems with
binary variables because binary variables are used to model logical conditions.
Example 2.5.
x1 =
1, if XYZ buys stock ABC,

0, otherwise.
If x1 = 0.123, should we round up or down?
16
2. An optimal LP solution is not necessarily feasible after it is

rounded.
Maximize z =
x2
subject to
x1 + x2 0.5
x1 + x2 3.5
x1 0, x2 0
x1, x2 integers.
Maximize z =
subject to
x1 +
x1 +
x1 0,
x2
x2 0.5
x2 3.5
x2 0.
17

(x1, x2 ) = (1.5, 2).
However, both (1, 2) and (2, 2) are infeasible to the original
IP problem.
18
3. There is no guarantee that the rounded solution will be the optimal integer solution. In fact, it may even be far from optimal.
Maximize z = 3x1 + 10x2
subject to
2x1 + 7x2 14
x1
6
x1 0, x2 0
x1, x2 integers.
subject to
2x1 + 7x2 14
x1
6
x1 0, x2 0.
19

(x1 , x2 ) = (6, 2/7).
By rounding up or down of the above solution, we have the
following close-to-optimal solutions:
x1 x2 Feasible? z
6 0
Yes
18 *
6 1
No
Notice that (x1, x2) = (6, 0) with z = 18 is far from the optimal
solution to the IP problem (x1 , x2 ) = (0, 2) with z = 20.
20
2.2.3. Exhaustive Enumeration

The Method
Checking each solution for feasibility and, if it is feasible, calculating
the value of the objective function.
Example 2.8. Consider the following IP Problem again:
subject to
2x1 + 7x2 14
x1
6
x1 0, x2 0
x1, x2 integers.
21
x2
x1
(x1, x2) Feasible? z (x1, x2) Feasible? z (x1, x2) Feasible? z

(0,0)
Yes
0 (0,1)
Yes 10 (0,2)
Yes 20
Yes 13 (1,2)
No
(1,0)
Yes
3 (1,1)
(2,0)
Yes
6 (2,1)
Yes 16 (2,2)
No
Yes 19 (3,2)
No
(3,0)
Yes
9 (3,1)
(4,0)
Yes 12 (4,1)
No
(4,2)
No
No
(5,2)
No
(5,0)
Yes 15 (5,1)
(6,0)
Yes 18 (6,1)
No
(6,2)
No
Optimal Solution: (x1, x2 ) = (0, 2) with z = 20.
22
23
Exponential growth of difficulty

Consider the simple case of BIP problems.
With n variables, there are 2n solutions to be considered (where
some of these solutions can subsequently be discarded because they
violate the functional constraints).
Thus, each time n is increased by 1, the number of solutions is
doubled.
Even the fastest computer can solve IP problems with only a few
dozens of variables by exhaustive enumeration.
24
Example 2.9.
Assume that there is a 1000-core 10 GHz computer system.
Assume that each core of this system can calculate and compare
the objective function values of 1010 integer points in 1 second.
Then, this computer solve a BIP problem with only 80 variables in
about 3830 years by exhaustive enumeration.
n Number of solutions Time required
40
240
0.11 seconds
50
250
1.88 minutes
60
260
1.33 days
70
270
3.74 years
80
280
3830.85 years
2.3. Modeling Techniques and

Illustrative Applications
2.3.1. Binary Choices
For j = 1, 2, . . . , N , let
yj =
1,
0,
if decision j is yes,
if decision j is no.
25
26
Example 2.10 (Capital Budgeting Problem).

Five projects are being evaluated over a 3-year planning horizon.
The following table gives the expected returns for each project and the
associated yearly expenditures. (M$ = million dollars)
Project 1
Project 2
Project 3
Project 4
Project 5
Available funds
Expenditures (M$)/year
Expected
Year 1 Year 2 Year 3 Returns (M$)
5
1
8
20
4
7
10
40
3
9
2
20
7
4
1
15
8
6
10
30
(M$)
25
25
25
Which projects should be selected over the 3-year horizon?
27
Solution
Let z = total expected returns (million dollars).
For j = 1, 2, 3, 4, 5, let
yj =
1,
0,
if project j is selected,
if project j is not selected.
The IP model is:

Max z = 20y1 + 40y2 + 20y3
s.t.
5y1 + 4y2 + 3y3
y1 + 7y2 + 9y3
8y1 + 10y2 + 2y3
y1, y2, y3 , y4, y5 binary.
+ 15y4 + 30y5
+ 7y4 + 8y5 25
+ 4y4 + 6y5 25
+ y4 + 10y5 25
28
2.3.2. Relations Between Variables

At Least K Decisions in the Group Must be YES
N
X
j=1
yj K.
Example 2.11 (Set Covering Problem).

To promote on-campus safety, the Security Department of a University is in the process of installing emergency telephones at selected
locations. The department wants to install the minimum number of
telephones provided that each of the campus main streets is served by
at least one telephone. The following figure shows that the layout of
the streets:

1
Street A
29
Street B
Street
I
Street
G
Street
F
Street
K
Street C
Street
H
Street D
Street E
6
Street
J
Solution
Let z = number of telephones to be installed.
For j = 1, 2, . . . , 8, let
yj =
1,
0,
if a telephone is installed at location j,

otherwise.
30
The IP model is:

Min z = y1 + y2 + y3 + y4 + y5 + y6 + y7 + y8
s.t.
y1 + y2
1
y2 + y3
1
y4 + y5
1
y7 + y8 1
y6 + y7
1
y2
+ y6
1
y1
+ y6
1
y4
+ y7
1
y2
+ y4
1
y5
+ y8 1
y3
+ y5
1
yj binary, for j = 1, 2, . . . , 8.
31
Exactly K Decisions in the Group Must be YES

N
X
j=1
yj = K.
At Most K Decisions in the Group Can be YES

N
X
j=1
yj K.
y2 is Allowed to be YES only if y1 is YES

y2 y1 .
32
33

The California Manufacturing Company is considering expansion by
building a new factory in either Los Angeles (LA) or San Francisco (SF),
or perhaps even in both cities. It also is considering building at most
one new warehouse, but the choice of location is restricted to a city
where a new factory is being built. The objective is to find the feasible
combination of alternatives that maximizes the total net present value
(NPV).
Decision
Number
1
2
3
4
(M = million)
Yes-or-No
Decision
Capital
Question
Variable NPV Required
Build factory in LA?
y1
$9M $6M
Build factory in SF?
y2
$5M $3M
Build warehouse in LA?
y3
$6M $5M
Build warehouse in SF?
y4
$4M $2M
Capital available: $10M
34
Solution
Let z = total net present value ($).
For j = 1, 2, 3, 4, let
yj =
1,
0,
if decision j is yes,
if decision j is no.
The IP model is:

Max z = 9y1 + 5y2 + 6y3 + 4y4
s.t.
6y1 + 3y2 + 5y3 + 2y4 10
y3 + y4 1
y1
+ y3
0
y2
+ y4 0
yj binary, for j = 1, 2, 3, 4.
35
36
2.3.3. Function with N Possible Values

g(x1, x2, . . . , xn ) = b1 or b2 or
...
is equivalent to
g(x1, x2, . . . , xn) =

N
X
i=1
N
X
i=1
biyi
yi = 1
yi binary, for i = 1, 2, . . . , N.
or
bN
37
Example 2.13 (Resource Allocation Problem).

The Wyndor Glass Co. has three plants: Plant 1, Plant 2 and Plant 3.
It recently launches two new products: Product 1 and Product 2. Product 1 requires some of the production capacity in Plants 1 and 3, but
none in Plant 2. Product 2 needs only Plants 2 and 3. The following
table gives the data for the Wyndor Glass Co. problem.
Production Time
Production Time
(Hours/Unit)
Available
Product 1 Product 2 (Hours/Week)
Plant 1
1
0
4
Plant 2
0
2
12
Plant 3
3
2
18
Profit/Unit ($)
3000
5000
38
18 hours of production time per week in Plant 3 currently is unused

and available for the two new products or for certain future products
that will be ready for production soon. In order to leave any remaining capacity in usable blocks for these future products, management
now wants to impose the restriction that the production time used by
Products 1 and 2 be 6 or 12 or 18 hours per week.
Determine what the production rates should be for the two products
in order to maximize the total profit subject to the foregoing restrictions.
39
Solution
Let z = total profit (thousand dollars)
Let xj = number of product j produced per week (j = 1, 2)
Let
1,
0,
1,
y2 =
0,
1,
y3 =
0,
y1 =
if 6 hours/week of production time in Plant 3 being used,

otherwise,
otherwise,
otherwise,
40
The IP model is:

Max z = 3x1 + 5x2
s.t.
x1
2x2
3x1 + 2x2 6y1 12y2 18y3
y1 + y2 + y3
x1 0, x2 0,
x1, x2 integer,
y1, y2, y3 binary.
4
12
= 0
= 1
2.3.4. Fixed-Charge Problem

Requirement
Minimize the cost function:
f (x) =
where k > 0, c > 0 and x 0.
k + cx, if x > 0,
0,
if x = 0,
41
42
IP Formulation
Let M be a positive number such that M x, for all feasible x, and
let
y=
1, if x > 0,
0, if x = 0.
Then, the problem can be reformulated as follows:

f(x, y)
x
= ky + cx
My
0
binary.
43
Note:
In practice, some care is taken to choose a value of M that definitely
is large enough to avoid eliminating any feasible solution, but as small
as possible otherwise in order to avoid unduly enlarging the feasible
region for the LP-relaxation and to avoid numerical instability.
44
Example 2.14 (Fixed-Charge Problem).

John has been approached by three telephone companies to subscribe
to their long distance service in the United States.
Company Flat Fee ($ Per Month) Charge ($ Per Minute)
1
16
0.25
2
25
0.21
3
18
0.22
He usually makes an average of 200 minutes of long-distance calls a
month. Assuming that he does not pay the flat monthly fee unless
he makes calls and that he can apportion his calls among all three
companies as he pleases, how would he use the three companies to
minimize his monthly telephone bill?
Solution
Let z = total cost ($ per month).
For j = 1, 2, 3, let
xj = company
j long-distance minutes per month
1, if x > 0,
j
yj =
0, if x = 0.
j
Let Mj 200 be a constant (j = 1, 2, 3).
45
The IP model is:

Min z = 0.25x1 + 16y1 + 0.21x2 + 25y2 + 0.22x3 + 18y3
s.t.
x1
+
x2
+
x3
= 200
x1 M1y1
0
x2 M2y2
0
x3 M3y3 0
x1 0, x2 0, x3 0,
y1, y2 , y3 binary.
46
47
2.3.5. Either-Or Constraints

Requirement
Only one (either one) constraint must hold (whereas the other one
can hold but is not required to do so).
Either g1(x1, x2, . . . , xn) b1
or
g2(x1, x2, . . . , xn) b2
IP Formulation
Let M be a positive number such that
g1(x1, x2, . . . , xn) b1 + M
g (x , x , . . . , x ) b + M
2 1 2
n
2
for all feasible solutions (x1, x2, . . . , xn).
Then, the problem can be reformulated as follows:
g1 (x1, x2, . . . , xn) b1 + M y

g2 (x1, x2, . . . , xn) b2 + M (1 y)
y binary.
48
49
Example 2.15 (Resource Allocation Problem).

Product 1 Product 2 Product 3 Available
Steel (tons)
1.5
3
5
6000
30
25
40
60000
Labor (hours)
Profit ($)
2000
3000
4000
For production of a type of product to be economically feasible, at
least 1000 units of that type must be produced.
Solution
Let z = total profit (thousand dollars).
Let xj = number of product j produced (j = 1, 2, 3).
Let M1 2000, M2 2000 and M3 1200 be constants.
50
The IP model is:

Max z = 2x1 + 3x2 + 4x3
s.t.
1.5x1 + 3x2 + 5x3 6000
30x1 + 25x2 + 40x3 60000
x1 M1y1
x1 1000 + M1(1 y1)
x2 M2y2
x2 1000 + M2(1 y2)
x3 M3y3
x3 1000 + M3(1 y3)
x1 0, x2 0, x3 0
x1, x2, x3 integer
y1, y2 , y3 binary.
51
2.3.6. K out of N Constraints

Requirement
K out of the following N constraints must hold:
g1(x1, x2, . . . , xn) b1
g2(x1, x2, . . . , xn) b2
...
gN (x1, x2, . . . , xn) bN
52
IP Formulation
g1(x1, x2, . . . , xn) b1 + M

g2(x1, x2, . . . , xn) b2 + M
...
g (x , x , . . . , x ) b
N 1 2
n
N +M
for all feasible solution (x1, x2, . . . , xn).
53
Then, the problem can be reformulate as follows:
g1(x1, x2, . . . , xn) b1 + M (1 y1)

g2(x1, x2, . . . , xn) b2 + M (1 y2)
...
g (x1, x2, . . . , xn) bN + M (1 yN )
N
X
i=1
yi = K
yi binary, for i = 1, 2, . . . , N .
54
55
2.3.7. If-Then Constraints

Requirement
h(x1, x2, . . . , xn) > 0
g(x1, x2, . . . , xn) 0.
IP Formulation
g(x1, x2, . . . , xn ) M
h(x1, x2, . . . , xn ) M
for all feasible solution (x1, x2, . . . , xn).

Then, the problem can be reformulate as follows:
g(x1, x2, . . . , xn) M y

h(x1, x2, . . . , xn) M (1 y)
y binary.
56

In Example 2.10, if project 5 is selected, then no other project can
be selected.
Solution
Let M 4 be a constant.
IP formulation:
y1 + y2 + y3 + y4 M y
y5 M (1 y)
y binary
57
2.3.8. Binary Representation of General Integer

Variables
0 x u, integer
is equivalent to
x=
N
X
i=0
2i yi
yi binary, for i = 0, 1, 2, . . . , N
where N is the integer such that 2N u < 2N+1.
58
Example 2.17.
Use the binary representation for integer variables to reformulate the
following PIP problem as BIP problem.
Max z = 3x1 + 4x2
s.t.
x1
5
2x1 + 3x2 30
x1 0, x2 0
x1, x2 are integers.
59
Solution
Since 0 x1 5 and 22 5 < 22+1, we let
x1 = y0 + 2y1 + 4y2 .
Since 0 x2 10 and 23 10 < 23+1, we let
x2 = y3 + 2y4 + 4y5 + 8y6.
Thus, the equivalent BIP formulation of the problem is:
Max z = 3 ( y0 + 2y1 + 4y3 ) + 4 ( y3 + 2y4 + 4y5 + 8y6 )
s.t.
y0 + 2y1 + 4y2
5
2 ( y0 + 2y1 + 4y2 ) + 3 ( y3 + 2y4 + 4y5 + 8y6 ) 30
yi 0, binary, i = 0, 1, 2, 3, 4, 5, 6.
60
2.4. The Branch-and-Bound (B&B)

Method for IP
2.4.1. Introduction
The first B&B algorithm was developed in 1960 by A. Land and
G. Doig.
The basic concept underlying the B&B technique is to divide and
conquer.
Since the original large problem is too difficult to be solved directly, it is divided into smaller and smaller subproblems until these
subproblems can be conquered.
The B&B method has three basic steps: branching, bounding and
fathoming.
61
Branching
Consider the following problems:
(P )
Maximize
subject to
(PA) Maximize
subject to
(PB ) Maximize
subject to
z = cT x
x X = XA XB
z = cT x
x XA
z = cT x
x XB
Theorem 1. If zA and zB are the optimal values of problems

(PA) and (PB ), respectively, then z = max{zA , zB } is the optimal
value of problem (P ).
62
Branching involves selecting one remaining subproblem (P ) and

dividing it into smaller subproblems (PA) and (PB ).
By comparing the optimal values, zA and zB , of the subproblems,
and selecting the maximum value between them, the original problem can be solved.
Some popular rules for branching are:
Select the subproblem with the best bound.
Select the most recently created subproblem.
63
Bounding
Consider the following problems:
(P ) Maximize
subject to
(P ) Maximize
subject to
z = cT x
xX = Z
z = cT x
x
Theorem 2. If z and z are the optimal values of problems (P )

and (P ), respectively, then z z .
Theorem 3. If
x is an optimal solution to problem (P ) and
x Z,
then x is an optimal solution to problem (P ) and z = z .
Bounding usually is done by solving a relaxation.

Some popular relaxations for bounding are:
LP relaxation
Lagrangian relaxation
64
65
Fathoming
Fathoming of a subproblem, and thereby dismissing from further
consideration, generally is done by an analysis of its relaxation in
the three ways described below.
Criterion 1: An upper bound of the optimal objective function
value of the subproblem the objective function value of the incumbent, or
Criterion 2: The subproblem has no feasible solutions, or
Criterion 3: An optimal solution of the subproblem has been
found.
66
2.4.2. The Branch-and-Bound Algorithm

Initialization
Set z = (incumbent optimal value).
Apply the bounding step, fathoming step, and optimality test described below to the whole problem.
If not fathomed, classify this problem as the one remaining subproblem for performing the first full iteration below.
67
Iteration
Step 1: Branching
Among the remaining (unfathomed) subproblems, select the one
with the best bound or the one that was created most recently.
Among the integer-restricted variables that have a non-integer value
in the optimal solution for the LP relaxation of the subproblem,
choose the first one in the natural ordering of the variable to be the
branching variable.
Let xj be this variable and xj its value in this solution. Branch
from the node for the subproblem to create two new subproblems
by adding the respective constraints xj
xj and xj
xj + 1.
(Note:
xj = greatest integer xj .)
68
Step 2: Bounding
For each new subproblem, obtain its bound by applying the simplex method (or the dual simplex method when reoptimizing) to its LP
relaxation and using the value of z for the resulting optimal solution.
69
Step 3: 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 upper bound z , where z is the value of z for the
incumbent.
Test 2: Its LP relaxation has no feasible solution.
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 .)
70
Optimality Test
Stop when there are no remaining subproblems; the incumbent is
optimal. (If there is no incumbent, the conclusion is that the problem
has no feasible solutions.) Otherwise, perform another iteration.
2.4.3. A 2-D Pure IP Example

Maximize z =
subject to
5x1 + 4x2
x1 + x2 5
10x1 + 6x2 45
x1 0, x2 0
x1, x2 integers.
71
72
Initialization
Initializing the Current Optimal Value
Set the current optimal value z = .
Obtaining a Bound for the Original Problem
Deleting the integer constraints and solving the resulting LP relaxation of the original problem by the graphical method or the
simplex method, we obtain
(x1, x2) = (3.75, 1.25) with z = 23.75.
Set the bound for the original problem = 23.75.
73
Performing Fathoming Tests for the Original Problem

Test 1: Bound = 23.75 > z = = failed.
Test 2: (3.75, 1.25) is a feasible solution to the LP relaxation of the
original problem = failed.
Test 3: (3.75, 1.25) violates the integer restrictions for x1 and x2
= failed.
The original problem is not fathomed.
74
Iteration 1
Creating Branches for the Original Problem
The first integer-restricted variable that has a non-integer value is
x1 = 3.75, so x1 becomes the branching variable.
Since 3 x1 4, we then create the following two subproblems:
Subproblem 1: Original problem plus additional constraint:
x1 3.
x1 4.
75
Obtaining a Bound for the Subproblem 1

Solving the LP relaxation of the Subproblem 1 by the graphical
method or the dual simplex method, we obtain
(x1, x2) = (3, 2) with z = 23.
Set the bound for the Subproblem 1 = 23.
Performing Fathoming Tests for the Subproblem 1
Since the optimal solution to the LP relaxation of the Subproblem 1,
(x1, x2) = (3, 2), has integer values for all its integer-restricted
variables, the Subproblem 1 is fathomed by test 3.
Since the optimal value of the LP relaxation of the Subproblem 1,
z = 23, satisfies z > z = , we then update
(x1 , x2 ) = (3, 2) and z = 23.
76

(x1, x2) = (4, 5/6) with z = 70/3 23.33.
Set the bound for the Subproblem 2 = 70/3.
Test 1: Bound 23.33 > z = 23 = failed.
Test 2: (4, 5/6) is a feasible solution to the LP relaxation of the
Subproblem 2 = failed.
Test 3: (4, 5/6) violates the integer restriction for x2 = failed.
The Subproblem 2 is not fathomed.
77
Iteration 2
Select a Subproblem for Branching
With only one remaining subproblem, we select Subproblem 2 for
branching.
Create Branches for the Subproblem 2
x2 = 5/6, so x2 becomes the branching variable.
Subproblem 3: Subproblem 2 plus additional constraint:
x2 0.
x2 1.
78

(x1, x2) = (4.5, 0) with z = 22.5.
Set the bound for the Subproblem 3 = 22.5.
The Subproblem 3 is fathomed by test 1 because its bound = 22.5
z = 23.
79

method or the dual simplex method, we find that it has no feasible
solutions.
The Subproblem 4 is fathomed by test 2.
Result
There are no remaining subproblems, so the current solution is optimal. Thus (x1 , x2) = (3, 2) with z = 23.
80
Branch-and-Bound Tree/Solution Tree/Enumeration Tree

LP0
(x1, x2) = (3.75, 1.25), z = 23.75
z* = f
x1 4
x1 d 3
LP1
(x1, x2) = (3, 2), z = 23
Fathomed
(x1*, x2*) = (3, 2), z* = 23
LP2
(x1, x2) = (4, 0.833), z | 23.3 > 23
(x1*, x2*) = (3, 2), z* = 23
x2 d 0
LP3
(x1, x2) = (4.5, 0), z = 22.5 d 23
Fathomed
(x1*, x2*) = (3, 2), z* = 23
x2 1
LP4
Infeasible
Fathomed
(x1*, x2*) = (3, 2), z* = 23
2.4.4. Another 2-D Pure IP Example

subject to
x1 + x2 6
9x1 + 5x2 45
x1 0, x2 0
x1, x2 integers.
81
82
Initialization
Deleting the integer constraints and solving the resulting LP relaxation of the original problem by the graphical method or the
simplex method, we obtain
(x1, x2) = (3.75, 2.25) with z = 41.25.
83

Test 2: (3.75, 2.25) is a feasible solution to the LP relaxation of the
original problem = failed.
Test 3: (3.75, 2.25) violates the integer restrictions for x1 and x2
= failed.
84
Iteration 1
x1 3.
x1 4.
85

(x1, x2) = (3, 3) with z = 39.
(x1 , x2 ) = (3, 3) and z = 39.
86

(x1, x2) = (4, 1.8) with z = 41.
Test 1: Bound = 41 > z = 39 = failed.
Test 2: (4, 1.8) is a feasible solution to the LP relaxation of the
Test 3: (4, 1.8) violates the integer restriction for x2 = failed.
87
Iteration 2
branching.
x2 1.
x2 2.
88

(x1, x2) = (40/9, 1) (4.44, 1) with z = 365/9 40.56.
Test 1: Bound 40.56 > z = 39 = failed.
Test 2: (40/9, 1) is a feasible solution to the LP relaxation of the
Test 3: (40/9, 1) violates the integer restriction for x1 = failed.
89

method or the dual simplex method, we find that it has no feasible
solutions.
90
Iteration 3
branching.
x1 4.44, so x1 becomes the branching variable.
x1 4.
x1 5.
91

(x1, x2) = (4, 1) with z = 37.
The Subproblem 5 is fathomed by test 1 because its bound = 37
z = 39.
92

(x1, x2) = (5, 0) with z = 40.
z = 40, satisfies z > z = 39, we then update
(x1 , x2 ) = (5, 0) and z = 40.
93
Result
There are no remaining subproblems, so the current solution is optimal. Thus (x1 , x2) = (5, 0) with z = 40.
94
Branch-and-Bound Tree
LP0
(x1, x2) = (3.75, 2.25), z = 41.25
z* = f
x1 4
x1 d 3
LP1
(x1, x2) = (3, 3), z = 39
Fathomed
(x1*, x2*) = (3, 3), z* = 39
LP2
(x1, x2) = (4, 1.8), z = 41 > 39
(x1*, x2*) = (3, 3), z* = 39
x2 2
x2 d 1
LP3
(x1, x2) = (4.44, 1), z | 40.6 > 39
(x1*, x2*) = (3, 3), z* = 39
x1 5
x1 d 4
LP5
(x1, x2) = (4, 1), z = 37 d 39
Fathomed
(x1*, x2*) = (3, 3), z* = 39
LP4
Infeasible
Fathomed
(x1*, x2*) = (3, 3), z* = 39
LP6
(x1, x2) = (5, 0), z = 40 > 39
Fathomed
(x1*, x2*) = (5, 0), z* = 40
95
2.4.5. An MIP Example

Maximize z = 4x1 2x2 + 7x3 x4
subject to
x1
+ 5x3
x1 + x2 x3
6x1 5x2
x1
+ 2x3 2x4
xj 0, for j = 1, 2, 3, 4
x1, x2, x3 integer.
10
1
0
3
96
Initialization
Deleting the integer constraints and solving the resulting LP relaxation of the original problem by the simplex method, we obtain
(x1, x2, x3, x4) = (1.25, 1.5, 1.75, 0) with z = 14.25.
97

Test 2: (1.25, 1.5, 1.75, 0) is a feasible solution to the LP relaxation
of the original problem = failed.
Test 3: (1.25, 1.5, 1.75, 0) violates the integer restrictions for x1, x2
and x3 = failed.
98
Iteration 1
x1 1.
x1 2.
99

Solving the LP relaxation of the Subproblem 1 by the dual simplex
method, we obtain
(x1, x2, x3, x4) = (1, 1.2, 1.8, 0) with z = 14.2.
Test 2: (1, 1.2, 1.8, 0) is a feasible solution to the LP relaxation of
the Subproblem 1 = failed.
Test 3: (1, 1.2, 1.8, 0) violates the integer restriction for x2 and x3
= failed.
100

method, we find that it has no feasible solutions.
101
Iteration 2
branching.
x2 1.
x2 2.
102

method, we obtain
(x1, x2, x3, x4) = (5/6, 1, 11/6, 0) with z = 85/6 14.17.
Test 1: Bound 14.17 > z = = failed.
Test 2: (5/6, 1, 11/6, 0) is a feasible solution to the LP relaxation
of the Subproblem 3 = failed.
Test 3: (5/6, 1, 11/6, 0) violates the integer restriction for x1 and
x3 = failed.
103

method, we obtain
(x1, x2, x3, x4) = (5/6, 2, 11/6, 0) with z = 73/6 12.17.
Test 1: Bound 12.17 > z = = failed.
Test 2: (5/6, 2, 11/6, 0) is a feasible solution to the LP relaxation
of the Subproblem 4 = failed.
Test 3: (5/6, 2, 11/6, 0) violates the integer restriction for x1 and
x3 = failed.
104
Iteration 3
With more than one subproblem, the one with the largest bound
(Subproblem 3) is selected for branching.
x1 0.
x1 1.
105

method, we obtain
(x1, x2, x3, x4) = (0, 0, 2, 0.5) with z = 13.5.
(x1, x2, x3, x4) = (0, 0, 2, 0.5), has integer values for all its integerrestricted variables, the Subproblem 5 is fathomed by test 3.
z = 13.5, satisfies z > z = , we then update
(x1 , x2 , x3, x4 ) = (0, 0, 2, 0.5) with z = 13.5.
106

method, we find that it has no feasible solutions.
107
Perform Fathoming Test 1 for all the Remaining Subproblems

Subproblem 4: Bound 12.17 z = 13.5 = fathomed.
Result
There are no remaining subproblems, so the current solution is optimal. Thus (x1 , x2, x3 , x4 ) = (0, 0, 2, 0.5) with z = 13.5.
108
LP0
x = (1.25, 1.5, 1.75, 0), z = 14.25
z* = f
x1 2
x1 d 1
LP1
x = (1, 1.2, 1.8, 0), z = 14.2
z* = f
x2 d 1
x2 2
LP2
Infeasible
Fathomed
z* = f
x1 1
LP4
x = (5/6, 2, 11/6, 0), z = 12.17
z* = f
z = 12.17 d 13.5 Fathomed
LP3
x = (5/6, 1, 11/6, 0), z = 14.17
z* = f
x1 d 0
LP5
x = (0, 0, 2, 0.5), z = 13.5
Fathomed
x* = (0, 0, 2, 0.5), z* = 13.5
LP6
Infeasible
Fathomed
x* = (0, 0, 2, 0.5), z* = 13.5
109
2.4.6. A BIP Example

Maximize z = 9x1 + 5x2 + 6x3 + 4x4
subject to
6x1 + 3x2 + 5x3 + 2x4
x3 + x4
x1
+ x3
x2
+ x4
xj binary, for j = 1, 2, 3, 4.
10
1
0
0
110
Initialization
Note that the binary restriction on each variable xj (j = 1, 2, 3, 4)
is equivalent to the following set of constraints:
0 xj 1
x integer.
j
Hence, the original problem can be rewritten as:

Maximize z = 9x1 + 5x2 + 6x3
subject to
6x1 + 3x2 + 5x3
x3
x1
+ x3
x2
x1
x2
x3
+ 4x4
+ 2x4 10
+ x4 1
0
+ x4 0
1
1
1
x4 1
xj 0, for j = 1, 2, 3, 4
xj integer, for j = 1, 2, 3, 4.
111
112
Deleting the integer constraints and solving the resulting LP relaxation of the original problem by the simplex method, we obtain
(x1, x2, x3, x4) = (5/6, 1, 0, 1) with z = 16.5.
Test 2: (5/6, 1, 0, 1) is a feasible solution to the LP relaxation of
the original problem = failed.
Test 3: (5/6, 1, 0, 1) violates the integer restrictions for x1 =
failed.
113
Iteration 1
Since x1 is a binary variable, we then create the following two subproblems:
Subproblem 1: Fix x1 = 0 in the original problem.
Maximize z = 5x2 + 6x3 + 4x4
subject to
3x2 + 5x3 + 2x4 10
x3 + x4 1
x3
0
x2
+ x4 0
xj binary, for j = 2, 3, 4.
Subproblem 2: Fix x1 = 1 in the original problem.

Maximize z = 5x2 + 6x3 + 4x4 + 9
subject to
3x2 + 5x3 + 2x4 4
x3 + x4 1
x3
1
x2
+ x4 0
xj binary, for j = 2, 3, 4.
114
115

method, we obtain
(x1, x2, x3, x4) = (0, 1, 0, 1) with z = 9.
(x1, x2, x3, x4) = (0, 1, 0, 1), has integer values for all its integerrestricted variables, the Subproblem 1 is fathomed by test 3.
(x1 , x2, x3 , x4 ) = (0, 1, 0, 1) with z = 9.
116

method, we obtain
(x1, x2, x3, x4) = (1, 0.8, 0, 0.8) with z = 16.2.
Test 1: Bound = 16.2 > z = 9 = failed.
Test 2: (1, 0.8, 0, 0.8) is a feasible solution to the LP relaxation of
the Subproblem 2 = failed.
Test 3: (1, 0.8, 0, 0.8) violates the integer restriction for x2 and x4
= failed.
117
Iteration 2
branching.
Since x2 is binary variable, we then create the following two subproblems:
Subproblem 3: Fix x2 = 0 in the Subproblem 2.

Maximize z = 6x3 + 4x4 + 9
subject to
5x3 + 2x4 4
x3 + x4 1
x3
1
x4 0
xj binary, for j = 3, 4.
Subproblem 4: Fix x2 = 1 in the Subproblem 2.
Maximize z = 6x3 + 4x4 + 14
subject to
5x3 + 2x4 1
x3 + x4 1
x3
1
x4 1
xj binary, for j = 3, 4.
118
119

method or the graphical method, we obtain
(x1, x2, x3, x4) = (1, 0, 0.8, 0) with z = 13.8.
Test 2: (1, 0, 0.8, 0) is a feasible solution to the LP relaxation of the
Test 3: (1, 0, 0.8, 0) violates the integer restriction for x3 = failed.
120

(x1, x2, x3, x4) = (1, 1, 0, 0.5) with z = 16.
Test 1: Bound = 16 > z = 9 = failed.
Test 2: (1, 1, 0, 0.5) is a feasible solution to the LP relaxation of the
Test 3: (1, 1, 0, 0.5) violates the integer restriction for x4 = failed.
121
Iteration 3
Since x4 is a binary variable, we then create the following two subproblems:
Subproblem 5: Fix x4 = 0 in Subproblem 4.

Maximize z = 6x3 + 14
subject to
5x3 1
x3 1
x3 1
x3 binary.
Subproblem 6: Fix x4 = 1 in Subproblem 4.
Maximize z = 6x3 + 18
subject to
5x3 1
x3 0
x3 1
x3 binary.
122
123

(x1, x2, x3, x4) = (1, 1, 0.2, 0) with z = 15.2.
Test 2: (1, 1, 0.2, 0) is a feasible solution to the LP relaxation of the
Test 3: (1, 1, 0.2, 0) violates the integer restriction for x3 = failed.
124

method or the graphical method, we find that it has no feasible
solutions.
125
Iteration 4
Since the resulting branching variable x3 is the last variable, fixing
its value at either 0 or 1 actually creates a single solution rather
than subproblems requiring further investigation.
126
Fix x3 = 0 in Subproblem 5
(x1, x2, x3, x4) = (1, 1, 0, 0) with z = 14 is a feasible solution to the
original problem.
Since (x1, x2, x3, x4) = (1, 1, 0, 0) has integer values for all its
integer-restricted variables, it is fathomed by test 3.
Since z = 14, satisfies z > z = 9, we then update
(x1 , x2, x3 , x4 ) = (1, 1, 0, 0) with z = 14.
Fix x3 = 1 in Subproblem 5
(x1, x2, x3, x4) = (1, 1, 1, 0) is an infeasible solution to the original
problem.
It is fathomed by test 2.
127
Perform Fathoming Test 1 for all the Remaining Subproblems

Subproblem 3: Bound = 13.8 z = 14 = fathomed.
Result
There are no remaining subproblems, so the current solution is optimal. Thus (x1 , x2, x3 , x4 ) = (1, 1, 0, 0) with z = 14.
128
LP0
x = (5/6, 1, 0, 1), z = 16.5
z* = f
x1 = 1
x1 = 0
LP1
x = (0, 1, 0, 1), z = 9
Fathomed
x* = (0, 1, 0, 1), z* = 9
LP2
x = (1, 0.8, 0, 0.8), z = 16.2
x* = (0, 1, 0, 1), z* = 9
x2 = 1
x2 = 0
LP3
x = (1, 0, 0.8, 0), z = 13.8
x* = (0, 1, 0, 1), z* = 9
z = 13.8 d 14 Fathomed
LP4
x = (1, 1, 0, 0.5), z = 16
x* = (0, 1, 0, 1), z* = 9
x4 = 0
x4 = 1
LP5
x = (1, 1, 0.2, 0), z = 15.2
x* = (0, 1, 0, 1), z* = 9
x3 = 0
x3 = 1
LP7
x = (1, 1, 0, 0), z = 14 > 9
Fathomed
x* = (1, 1, 0, 0), z* = 14
LP6
Infeasible
Fathomed
x* = (0, 1, 0, 1), z* = 9
LP8
Infeasible
Fathomed
x* = (1, 1, 0, 0), z* = 14

Operations Research Ch02

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Operations Research Ch02

Uploaded by

Document Information

Original Description:

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

Operations Research Ch02

Uploaded by

Copyright:

Available Formats

Shiqian Ma, SEEM 3440, Dept.

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.1.1. Binary Integer Programming (BIP)

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Example 2.1 (Assignment Problem).

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Let z = total cost.

1, if machine i is assigned to do job j,

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

The IP model is:

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.1.2. Pure Integer Programming (PIP) Problem

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Example 2.2 (Transportation Problem).

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Let z = total cost.

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.1.3. Mixed Integer Programming (MIP)

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.2. Some Perspectives on Solving IP

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

By ignoring integrality restrictions, we have the following

The optimal solution to the LP relaxation problem is

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

By rounding up or down of the above solution, we have the following

Question: Is the solution (x1, x2) = (3, 2) with z = 23 optimal or

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

1, if XYZ buys stock ABC,

If x1 = 0.123, should we round up or down?

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2. An optimal LP solution is not necessarily feasible after it is

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

The optimal solution to the LP relaxation problem is

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

The optimal solution to the LP relaxation problem is

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.2.3. Exhaustive Enumeration

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

(x1, x2) Feasible? z (x1, x2) Feasible? z (x1, x2) Feasible? z

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Exponential growth of difficulty

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.3. Modeling Techniques and

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Example 2.10 (Capital Budgeting Problem).

Which projects should be selected over the 3-year horizon?

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

The IP model is:

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

2.3.2. Relations Between Variables

Example 2.11 (Set Covering Problem).

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK

Shiqian Ma, SEEM 3440, Dept. of SEEM, CUHK