(SEHS4648) Example (SEHS4648)

Unit-6 Big M Method and Integer Programming

Maximize z = 2x1 + x2
1. Big M method subject to x1 + x2 < 10 x1 + x2 + s1 = 10
2. Integer Programming x1 + x2 > 2 x1 + x2 s2 = 2
x1, x2 > 0

To form an equations, we introduce a slack variable s1 ( )

and surplus variable s2 ( ) to constraints.

1 3

Big M Method (SEHS4648) Example (SEHS4648)

We now express the linear programming problem as below:

In this section, another version of the simplex method Max z = 2x1 + x2

is presented that will solve nonstandard problems Subject to x1 + x2 + s1 = 10
including both maximization and minimization LP
problems with any combination of constraints x1 + x2 s2 =2
x1, x2, s1, s2 > 0

Basic Z x1 x2 s1 s2 r.h.s.
z 1 2 1 0 0 0
s1 0 1 1 1 0 10
s2 0 1 1 0 1 2
2 4
 Example (SEHS4648) Example (SEHS4648)

Basic Z x1 x2 s1 s2 r.h.s. An artificial variable a1 is introduced into the equation involving

z 1 2 1 0 0 0 the surplus variable s2:
s1 0 1 1 1 0 10 -x1 + x2 s2 + a 1 = 2
s2 0 1 1 0 1 2 To prevent an artificial variable from becoming part of an optimal
solution to the original problem, a very large penalty is
introduced into the objective function. This penalty is created by
Initial solution: Non-basic variables: x1 = x2 = 0
choosing a positive constant M so large that the value of the
Basic variables: s1= 10, s2 = -2 artificial variable is forced to be ZERO in any final optimal solution
of the original problem. Hence this is known as Big M method. We
A solution is not feasible if any of the variables are negative. add the term Ma1 to the objective function:
Hence the solution is not feasible because the surplus
variable s2 is negative. z = 2x1 + x2 Ma1

5 7

Artificial Variables (SEHS4648) Example (SEHS4648)

In order to use the simplex method on problems with mixed

constraints, a new artificial variable is introduced. This variable
has no physical meaning in the original problem and is introduced Original problem Big M method
solely for the purpose of obtaining a basic feasible solution so
that we can apply the simplex method. Maximize z = 2x1 + x2 Max z = 2x1 + x2 - Ma1
subject to x1 + x2 < 10 s.t. x1 + x2 + s1 = 10
An artificial variable is a variable introduced into each equation
that has a surplus variable. To ensure that we consider only x1 + x2 > 2 -x1 + x2 s2 + a1 = 2
feasible solutions, an artificial variable is required to satisfy the x1, x2 > 0 x1, x2, s1, s2, a1 > 0
nonnegative constraint. But the optimal solution should not
include any artificial variable.

6 8
 (SEHS4648) Preparatory step for the initial tableau (SEHS4648)
Basic Z x1 x2 s1 s2 a1 r.h.s.
Big M Method:
Form the Modified Problem z 1 2 1 0 0 M 0
If any problem constraints have negative constants on the right side, multiply s1 0 1 1 1 0 0 10
both sides by -1 to obtain a constraint with a nonnegative constant.
s2 0 1 1 0 1 1 2
Remember to reverse the direction of the inequality if the constraint is an
inequality.
The initial simplex tableau from our example does not satisfy
Introduce a slack variable the requirement that all variables are nonnegative since the
Introduce a surplus variable and an artificial variable solution is not feasible (s2 = -2).
constraint.
Introduce an artificial variable
To use the simplex method, we must first use row operations to
transform the tableau into the one that satisfies all initial
For each artificial variable aj , add Maj to the maximization objective
Maj minimization objective function. simplex tableau requirements.
Use the same constant M for all artificial variables. We need to replace s2 by choosing a1 as a basic variable and
thus to adjust numbers in the a1 column before starting simplex
9
method. This is not the pivot column in simplex method. 11

(SEHS4648) Preparatory step for the initial tableau (SEHS4648)

The initial system for the modified problem is We want to use a1 as a basic variable instead of s2. We proceed to eliminate M
from the a1 column using row operations:
Max z = 2x1 + x2 Ma1 Basic Z x1 x2 s1 s2 a1 r.h.s.
x 1 + x 2 + s1 = 10 z 1 2 1 0 0 M 0

x1 + x2 s2 + a 1 =2 s1 0 1 1 1 0 0 10
s2 0 1 1 0 1 1 2
x1, x2, s1, s2, a1 > 0
Basic Z x1 x2 s1 s2 a1 r.h.s.
Then, the initial simplex tableau for the modified problem.
z 1 M 2 M 1 0 M 0 -2M
Basic Z x1 x2 s1 s2 a1 r.h.s.
s1 0 1 1 1 0 0 10
z 1 2 1 0 0 M 0
a1 0 1 1 0 1 1 2
s1 0 1 1 1 0 0 10
Initial solution: Non-basic variables: x1 = x2 = s2 = 0
s2 0 1 1 0 1 1 2
Basic variables: s1= 10, a1 = 2
10 The solution is now feasible. 12
 First step for the simplex method (SEHS4648) Second step for the simplex method (SEHS4648)

We now continue with the usual simplex process, using pivot

operations and keep in mind that M is unspecified, but a very Thus, we obtain:
large positive number.
Basic Z x1 x2 s1 s2 a1 r.h.s.

s2 z 1 0 0 3/2 1/2 M 14
Basic z x1 x2 s1 a1 r.h.s. ratio
z 1 2 1 0 M 0 x1 0 1 0 1/2 1/2 4

s1 0 1 1 1 0 0 10 x2 0 0 1 1/2 1/2 1/2 6

a1 0 1 1 0 1 1 2
The top row coefficients are all nonnegative and the artificial
variables is a non-basic variable, we have the optimal solution:
In this example, M 2 and M are positive, and M 1 is
negative. The first pivot column is column 2 and the first pivot Optimal solution: Non-basic variables: s1 = s2 = a1 = 0
row is row 2. Basic variables: x1 = 4, x2 = 6

13 15

First step for the simplex method (SEHS4648) Summary steps for example (SEHS4648)
Basic Z x1 x2 s1 s2 a1 r.h.s.
Basic Z x1 x2 s1 s2 a1 r.h.s. Preparation
z 1 2 1 0 0 M 0
z 1 2 1 0 M 0 step
s1 0 1 1 1 0 0 10
(optional)
s1 0 1 1 1 0 0 10 s2 0 1 1 0 1 1 2

a1 0 1 1* 0 1 1 2 Basic Z x1 x2 s1 s2 a1 r.h.s. ratio

z 1 M 2 M 1 0 M 0 -2M

After pivot operation, we have s1 0 1 1 1 0 0 10

a1 0 1 1* 0 1 1 2

Basic Z x1 x2 s1 s2 a1 r.h.s.
Basic Z x1 x2 s1 s2 a1 r.h.s. ratio
z 1 - 0 -1 M +1
z 1 - 0 -1 M +1 s1 0 2* 0 1 1 -1 8
s1 0 2 0 1 1 -1 8 x2 0 -1 1 0 -1 1 2

x2 0 -1 1 0 -1 1 2 Basic Z x1 x2 s1 s2 a1 r.h.s.
z 1 0 0 3/2 1/2 M 14
x1 0 1 0 1/2 1/2 4
14 16
x2 0 0 1 1/2 1/2 1/2 6
 First step for the simplex method
Example (SEHS4648) (SEHS4648)

Minimize z = 2x1 + 5x2 The selection of the leaving (basic) variable is the most negative coefficient, and the
entering (non-basic) variable is having the smallest positive ratio.
subject to 3x1 + x2 < 10
x1 + 2x2 > 10 In this example, we choose x2 to become basic in the first iteration.

x1, x2 > 0

Basic Z x1 x2 s1 s2 a1 r.h.s. ratio

We can transform the above minimization problem into a maximization problem. Z 1 M M 0 M 0 -10M
s1 0 3 1 1 0 0 10
Maximize z = -2x1 5x2
a1 0 1 2 0 -1 1 10
subject to 3x1 + x2 < 10
x1 + 2x2 > 10
When checking the ratio, we choose the artificial variable a1 to become non-basic
x1 , x2 > 0 variable.

17 19

Preparatory step for the initial tableau (SEHS4648) (SEHS4648)

To form equations, we introduce a slack variable s1 , surplus variable s2 and
artificial variable a1 to constraints.
Basic Z x1 x2 s1 s2 a1 r.h.s.
Maximize z = -2x1 5x2 M a1 ratio

subject to 3x1 + x2 + s1 = 10
Z 1 -0.5 0 0 2.5 M-2.5 -25
5
s1 0 2.5 0 1 0.5 -0.5 5 2.5
2
x1 + 2x2 s2 + a1 = 10
x2 0 0.5 1 0 -0.5 0.5 5 5
0.5
10
x1, x2 , s1 , s2 , a1 > 0

Basic Z x1 x2 s1 s2 a1 r.h.s.
Z 1 2 5 0 0 M 0 Now, we choose x1 to become basic variable in the second iteration.

s1 0 3 1 1 0 0 10
s2 0 1 2 0 -1 1 10 When checking the ratio, we choose the slack variable s1 to become non-basic variable.

Basic Z x1 x2 s1 s2 a1 r.h.s.
Z 1 2 M M 0 M 0 -10M
s1 0 3 1 1 0 0 10
a1 0 1 2 0 -1 1 10 18 20
 Second step for the simplex method (SEHS4648) Big M Method: Summary (SEHS4648)

Basic Z x1 x2 s1 s2 a1 r.h.s. 1. Form the preliminary simplex tableau for the modified problem.

Z 1 -0.5 0 0 2.5 M-2.5 -25

2. [Preparatory step] Use row operations to eliminate the M in the top row of the
s1 0 2.5 0 1 0.5 -0.5 5 initial simplex tableau in the columns corresponding to the artificial variables.
x2 0 0.5 1 0 -0.5 0.5 5 The resulting tableau is the initial simplex tableau.

Basic Z x1 x2 s1 s2 a1 r.h.s.
3. Solve the modified problem by applying the simplex method to the initial
Z 1 0 0 0.2 2.6 M-2.6 -24 simplex tableau found in the second step.

x1 0 1 0 0.4 0.2 -0.2 2

4. Special cases:
x2 0 0 1 -0.2 -0.6 0.6 4 (i) if the modified problem has no optimal solution, the original problem has
no optimal solution.
The top row (Z-row) coefficients are all non-negative and the artificial variable (ii) if all artificial variables are zero in the optimal solution to the modified
are non-basic variables, we have the optimal solution: problem, delete the artificial variables to find an optimal solution to the
original problem
Optimal solution: Non-basic variables: s1 = s2 = a1 = 0 (iii) if any artificial variables are nonzero in the optimal solution, the original
Basic variables: x1 = 2, x2 = 4 problem has no optimal solution.
The optimal objective value z = 24 with x1 = 2 and x2 = 4 in the original
minimization problem. 21 23

Summary (SEHS4648) Integer programming (IP) problems (SEHS4648)

Basic Z x1 x2 s1 s2 a1 r.h.s.
Z 1 2 5 0 0 M 0
Preparation
step
s1 0 3 1 1 0 0 10 (optional) An IP model is a model that has constraints and an objective function
s2 0 1 2 0 -1 1 10
identical to that formulated by LP. But the value of one or more of the
Basic Z x1 x2 s1 s2 a1 r.h.s.
decision variables have to be an integer.
Z 1 2 M M 0 M 0 -10M ratio
s1 0 3 1 1 0 0 10
a1 0 1 2 0 -1 1 10
Integer programming techniques
Basic Z x1 x2 s1 s2 a1 r.h.s.
Z 1 -0.5 0 0 2.5 M-2.5 -25 Branch and Bound Method
s1 0 2.5 0 1 0.5 -0.5 5 5 2
2.5
x2 0 0.5 1 0 -0.5 0.5 5 5
10
0.5

Basic Z x1 x2 s1 s2 a1 r.h.s.
Z 1 0 0 0.2 2.6 M-2.6 -24
x1 0 1 0 0.4 0.2 -0.2 2
22 24
x2 0 0 1 -0.2 -0.6 0.6 4
 Harrison electric company (SEHS4648) Integer Solution to Harrison Electric Co. (SEHS4648)

IP formulation
X1 = number of chandeliers to be produced
X2 = number of ceiling fans to be produced

Maximize profit = $7X1 + $6X2

Subject to: 2X1 + 3X2 Optimal
6X1 + 5X2 solution
X1, X2 must be nonnegative integer values

The optimal, non-integer solution is Solution if

X1 = 3.75 chandeliers, X2 = 1.5 ceiling fans, Profit = $35.25 rounding off

25 27

X2
6
Graphical solution (SEHS4648) Branch and bound method (SEHS4648)

The branch and bound method begins with the solution to the relaxation of the
integer LP problem.
5
6X1 + 5X2 30 If these variables are integer valued, this solution must also be the solution to
the integer problem.
4
+ means possible integer solution If these variables are not integer valued, the feasible region is divided by adding
constraints restricting the value of one of the variables that was not integer
valued.
3 + Optimal LP Solution
(X1 = 3.75, X2 = 1.5, Profit = $35.25) The divided feasible region results in subproblems that are then solved. Bounds
on the value of the objective function are found and used to help determine
which subproblems can be eliminated from consideration and when the optimal
2 + + + solution has been found.

If the solution to a subproblem does not yield an optimal solution, a new

1 + + + + subproblem is selected and branching continues.
2X1 + 3X2 12
7X1 + 6X2 = 21 (isoprofit line)
0
X1 26 28
1 2 3 4 5 6
 Harrison electric company (SEHS4648)
X2 (SEHS4648)
6
IP formulation Graphical solution of subproblem A
X1 = number of chandeliers to be produced
X2 = number of ceiling fans to be produced 5
Maximize profit = $7X1 + $6X2 6X1 + 5X2 30
Subject to: 2X1 + 3X2
6X1 + 5X2 4
X1 , X2 must be nonnegative integer values + possible integer solution
The optimal, noninteger solution is
3 X1 4 (add this new constraint)
X1 = 3.75 chandeliers, X2 = 1.5 ceiling fans, Profit = $35.25 +
Since X1 and X2 are NOT integers, this solution is not valid. Optimal solution
The profit value of $35.25 will serve as the initial upper bound. (X1 = 4, X2 = 1.2 Profit = $35.20)
Rounding down of X1 and X2 gives X1 = 3, X2 = 1, and profit = $27,
2 + + +
which is feasible and
can be used as the initial lower bound.
1 + + + +
Note: the profit does not necessary to be an integer, but X1 and X2 should be. 2X1 + 3X2 12

0
29 X1 31
1 2 3 4 5 6

(SEHS4648)
X2 (SEHS4648)
6
Divide the problem into 2 subproblems Graphical solution of subproblem B

Pick X1 (you can also pick X2) and divide the problem into 2 subproblems by 5
restricting the value of X1 (thus to make it to be an integer). 6X1 + 5X2 30
As X1 =3.75, the integer value of X1 should be either:
4 or greater than 4 (X1
3 or less than 3 (X1 4
+ possible integer solution
Subproblem A
3 X1 3 (add this new constraint)
Maximize profit = $7X1 + $6X2 +
Subject to: 2X1 + 3X2
6X1 + 5X2 Optimal solution (see next slide): Optimal solution
X1 X1 = 4, X2 = 1.2, profit = $35.20 2 + + + (X1 = 3, X2 = 2, Profit = $33)
Subproblem B
Maximize profit = $7X1 + $6X2
Subject to: 2X1 + 3X2
Solve subproblem B by yourself 1 + + + + 2X1 + 3X2 12
6X1 + 5X2 Optimal solution:
X1 X1 = 3, X2 = 2 profit = $ 33
7X1 + 6X2 = 21 (isoprofit line)
0
30 X1 32
1 2 3 4 5 6
 Divide the problem into 2 subproblems (SEHS4648) (SEHS4648)

We stop the search of the subproblem B branch because it has an all-integer feasible Divide subproblem A into subproblems C & D
solution. Subproblem A is now branched into 2 new subproblems C & D.
As X2=1.2, the integer value of X2 should be either:
2 or greater than 2 (X2 or
The profit value of $33 becomes the new lower bound. This is because this profit value 1 or less than 1 (X2 .
is greater than the initial lower bound of $27 (which is also a feasible integer solution). Subproblem C adds the constraint of X2
Subproblem D adds the constraint of X2
Subproblem C
IMPORTANT: lower bound is replaced ONLY IF a feasible integer solution with a Solve subproblem C by yourself
higher total profit is found. Maximize profit = $7X1 + $6X2
Subject to: 2X1 + 3X2
6X1 + 5X2
There is no feasible solution, so this
That means the current best integer solution is X1=3, X2=2, profit=$33. This solution is X1 branch is terminated. See next slide
better than the initial solution due to a higher profit is obtained ($33 vs. $27). X2
Subproblem D
-integer solution (X2=1.2). Maximize profit = $7X1 + $6X2
The 2nd upper bound takes on the value $35.20 (subproblem A:$35.20 vs. subproblem Subject to: 2X1 + 3X2
B:$33), replacing $35.25 from the 1st node. X1 = 4.17, X2 = 1, profit = $35.16
6X1 + 5X2
This non-integer solution yields a new
X1
upper bound of $35.16, replacing $35.20
IMPORTANT: the largest profit value of the subproblems is selected as the new X2
upper bound in EVERY iteration.
1

33
as this constraint is part of subproblem A 35

X2 Graphical solution of subproblem C

First branching: subproblems A & B (SEHS4648) (SEHS4648)
6

Note: you can work A 5

on X2 instead of X1 Next branch C 6X1 + 5X2 30
first, because the X1=4
value of X2 is also Infeasible (noninteger) solution 4
not an integer.
X2=1.2 + possible integer solution
Upper bound = $35.20 ($35.20 vs. $33)
P=35.20 Lower bound = $33.00 Infeasible solution:
X1 3 two feasible regions are
+ indicated because of
Next branch D
Original X1=3.75 conflicting constraints.
LP X2=1.5 Upper bound = $35.25 2
Lower bound = $27 + + + X2 2 (add this new constraint)
Solution P=35.25
X1 4 (this constraint has already been
B
1 added in subproblem A, so keep it.)
X1
X1=3 Stop branch B, + + + +
as solution is integer, feasible.
2X1 + 3X2 12
X2=2 It provides new lower bound of $33,
P=33.00 because its profit is greater than that of 0
initial feasible solutions (i.e. $27).
34 X1 36
1 2 3 4 5 6
 X2 Graphical solution of subproblem D (SEHS4648) (SEHS4648)
6
Divide subproblem D into subproblems E & F
5 Subproblem D is now branched into 2 new subproblems E & F
6X1 + 5X2 30 As X1=4.17, the integer value of X1 should be either:
5 or greater than 5 (X1 or
4 or less than 4 (X1 .
Subproblem E adds the constraint of X1
4 + possible integer solution Subproblem F adds the constraint of X1
Subproblem E
Maximize profit = $7X1 + $6X2
X1
3 + added in subproblem A, so keep it.)
Subject to: 2X1 + 3X2 Solve subproblem E by yourself
6X1 + 5X2
Optimal solution (see next slide):
Optimal solution X1
X1 = 4, X2 = 1, profit = $ 34
X1
2 + + + (X1 = 4.17, X2 = 1, Profit = $35.16) X2
Subproblem F Solve subproblem F by yourself
Maximize profit = $7X1 + $6X2
Subject to: 2X1 + 3X2 Optimal solution:
1 + + + + X2 1 (add this new constraint) 6X1 + 5X2 X 1 = 5 , X2 = 0 , profit = $ 35
X1 This is a feasible integer solution for the
2X1 + 3X2 12 X1 problem, no further branching is necessary.
X2
0
X1 37 2
as this constraint is part of subproblem D.
39
1 2 3 4 5 6

Second branching: subproblems C & D X2

(SEHS4648) Graphical solution of subproblem E (SEHS4648)
6
C
A No 5
X2 Feasible 6X1 + 5X2 30
X1=4 Solution
X2=1.2 4 + possible integer solution
P=35.20
X1
D Next branch E 3 X1 4 and X1 4 Note: only
X2
+ when X1=4 will
X1=3.75 X1=4.17 Optimal solution satisfy these
Upper bound = $35.16 (X1 = 4, X2 = 1 two constraints.
X2=1.5 X2=1 2 + + +
Lower bound = $33
P=35.25 P=35.16 Profit = $34)
B
Next branch F 1 + + + + X2 1
X1 X1=3
2X1 + 3X2 12
X2=2
P=33.00 0
38 X1 40
1 2 3 4 5 6
 X2 Graphical solution of subproblem F (SEHS4648) Summary (SEHS4648)
6
Maximize 7X1 + 6X2
Subject to: 2X1 + 3X2
5 6X1 + 5X2
6X1 + 5X2 30 X1 , X2 must be nonnegative integer values

4 Added Solution Upper Lower

+ possible integer solution Branch level
Constraint type
Value X1 X2
bound bound

Original LP 0 Non-integer 35.25 3.75 1.5 35.25 27

3 X1 4
+ A 1 X1 Non-Integer 35.2 4 1.2
X1 5 35.2 33
B 1 X1 Integer 33 3 2
Optimal solution
2 + + + (X1 = 5, X2 = 0 C 2 X2 Infeasible
35.16 33
Profit = $35) D 2 X2 Non-integer 35.16 4.17 1

1 + + + + X2 1 E 3 X1 Integer 34 4 1
35 35
2X1 + 3X2 12 F 3 X1 Integer 35 5 0

0 Optimal solution occurs when X1 = 5 and X2 = 0 with optimal value at 35.

X1 41 43
1 2 3 4 5 6

Third branching: subproblems E & F (SEHS4648) Steps in branch & bound (SEHS4648)

C For maximization problems:

A No
X2 Feasible E 1.Solve problem using LP. If solution is integer - finished.
If not, the objective function value will serve as the initial upper bound.
X1=4 Solution
X2=1.2 X1=4 Feasible, 2.Find any feasible integer solution to get lower bound. Usually, rounding down each
integer variable will do.
P=35.20 X2=1 solution
X1 P=34.00
X1 3.Branch on noninteger variable from step 1. Split problem into two pieces: integer
D above, and integer below.
X2
X1=3.75 X1=4.17 Upper bound = $35.16
4.Create nodes at top of these branches by solving the new problems.
X2=1.5 X2=1 Lower bound = $33
P=35.25 P=35.16 Optimal Note: Minimization problem involves reversing the roles of the
B F solution upper and lower bounds.
X1 X1=3 X1=5 Feasible,
X1 integer
X2=2 X2=0 solution
P=33.00 P=35.00
42 44
42
 Steps in branch & bound (cont.) (SEHS4648)

5. a) Branch solution not feasible, terminate branch.

b) Branch solution feasible, not integer, go to step 6.
c) Branch solution feasible, integer, check.
If equal to upper bound solution.
If less than upper bound, but greater than lower bound new lower bound and proceed.
If less than lower bound terminate branch.

6. Check branches. New upper bound is the maximum value of objective function
at all final nodes. If upper bound equals lower bound, stop; if not, go to step 3.

45

(SEHS4648)

Reference:

1. Frederick s. Hillier and Gerald J. Lieberman,

Introduction to Operations Research, Eighth Edition
McGraw Hill, 2000
Chapter 4. Solving Linear Programming Problems: The Simplex
Method, pp. 103 ~ 121.

46