Chapter 12: Integer Programming

IE 312
Operations
Research II
Second Semester
(2/2021)

1
Integer Programming
Integer Programming
• One key limitation of linear programming is the divisibilityassumption

• All decisions variable can be non-integer which, very often, no permissible

• E.g. number of people, machines, or vehicles

• With one addition restriction that the variables must have integer value, the system is then called
“integer programming (IP)”
• Integer linear programming (complete name)
• Mixed integer programming (MIP)
• Pure integer programming
• Binary integer programming

• E.g. the Wyndor Glass Co.

• X1 = glass door and x2 = wood-framed windows

2
Integer Program
Integer Programming
• Another important application → the “yes-or-no decisions”
• Should we undertake a particular fixed project?
• Should we make a particular fixed investment?
• Should we locate a facility in a particular site?

• Decisions are restricted to just yes = 1 or no = 0

• Binary decision variables

3
Integer Program
Prototype Example
California Manufacturing Company
• Consider building new factory in Los Angeles or San Francisco, or both
• Also consider building one new warehouse
• The warehouse must be with the new factory
• Given the NPV (total profit) of each alternatives and the capital required
• The total capital is $10 million

4
Integer Program
Prototype Example
California Manufacturing Company
• The BIP model
• Very small binary integer problem with few decision variables

• If the investment decision is yes → the full amount of respective NPV is granted
• If the investment decision is no → the respective NPV = 0

• The total NPV of the whole investment is:

5
Integer Program
Prototype Example
California Manufacturing Company
• The amount of capital expended on the four facilities cannot exceed $10 million:

• The mutually exclusive alternative (only one will be chosen) of the new warehouse:

• The warehouse decisions (x3 and x4) are contingent on (x1 and x2), the warehouse cannot be
built unless the factory is build:

6
Integer Program
Prototype Example
California Manufacturing Company
• The complete BIP is

• The last three lines can be replaced by

7
Integer Program
Some BIP applications
Investment analysis
• LP can be used for capital budgeting (how much to invest in each project)
• However, sometime a fixed amount is required (whether to invest or not)

• Example:
• Should we acquire a certain subsidiary being spun off by another company?
• Should we purchase a certain source of raw material
• Should we add a new production line to produce a certain input item ourselves or obtain
it from a supplier

8
Integer Program
Some BIP applications
Site selection
• Open up new plant in various parts of the world to take advantage of lower labor costs

9
Integer Program
Some BIP applications
Designing a production and distribution network
• Manufacturers try to get their products to market more quickly + reduce their production
and distribution costs

• Example:
• Should a certain plant remain open?
• Should a certain site be selected for a new plants?
• Should a certain 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?

• Application vignette – Midwest Independent Transmission System Operator, Inc

10
Integer Program
Some BIP applications
Dispatching shipments
• Daily operation decisions

• Determine after the production and distribution network has been designed and put into
operation

• Example:
• Trucks transport the shipments to customers
• Each truck make a series of deliveries in each trip
• Selecting a route (sequence of customers) for each truck

11
Integer Program
Some BIP applications
Dispatching shipments
• Objective – to minimize the total cost of making all the deliveries

• Complications:
• Different truck sizes – certain truck sizes may suit some certain routes
• Timing issue – time period for departure

12
Integer Program
Some BIP applications
Scheduling interrelated activities
• For every life …
• when to begin homework
• when to begin production for new orders
• when to begin marketing new products
• when to make capital investment to expand production capacities

• Frequently mutually exclusive as particular activity can be in only one period

• Selected reference A4 – Swedish municipalities

13
Integer Program
Some BIP applications
Airline applications
• Heavy user of OR
• Major airlines have large in-house department to work on OR applications

Fleet assignment problem:

• Assigning different type of airplanes to each flight leg in the schedule
• Maximize the total profit from meeting the schedule
• Assign too small → leave potential customers behind
• Assign too large → fly empty seat

• Selected reference A11 – Northwest Airlines

14
Integer Program
Some BIP applications
Airline applications
Crew scheduling problem:
• Assigning sequence of flight legs to crew (pilots and flight attendants)
• Leave and return to the same crew base

• Minimize the total cost of providing crews that cover each flight leg in the schedule

• Need to be revised quickly when flight delays or cancellations occur because of weather,
aircraft mechanical problems, or crew unavailability

• Selected reference A12 – Continental Airlines

15
Integer Program
Innovative uses of binary variables in model formulation
• Binary variables can be very useful in many ways
• E.g. use as auxiliary binary variable to help formulate problems (denote by yi in here)

Either-or constraints
• Situation where only one constraints must hold
• The decision is made by the model

• Rewritten as:

• Equivalent to:

16
Integer Program
Innovative uses of binary variables in model formulation
K out of N constraints must hold
• Overall model includes a set of N constraints
• Only K of them must hold where K < N
• Can be done by making N – K unchosen constraints ineffective
• The generalization of the previous case (the previous case K = 1 and N = 2)
• Constraints are:

• Using the same logic as the previous case:

17
Integer Program
Innovative uses of binary variables in model formulation
Function with N possible values
• The constraints are:

• With special case:

• The constraint can be rewritten as:

• Exactly one di will be chosen

18
Integer Program
Innovative uses of binary variables in model formulation
Function with N possible values
• Example: Wyndor Glass Co.
• 18 hours of production time is either 6 or 12 or 18

• With d1= 6, d2 = 12, and d3 = 18

• The constraints are:

19
Integer Program
Innovative uses of binary variables in model formulation
The fixed-charge problem
• A fixed charge or set up cost when undertake an activity
• Example: a production line must be set up before the batch production of a product
• The total cost is the sum of the variable cost relate to the activity and the setup cost
initiate the activity
• The total cost is in the form:

• Where
• xj = the level of activity (xj >= 0)
• kj = the set up cost
• cj = the incremental cost

20
Integer Program
Innovative uses of binary variables in model formulation
The fixed-charge problem
• The formulation is:

• yj is contingent on xj and the constraint is:

• The formulation is:

21
Integer Program
Innovative uses of binary variables in model formulation
The fixed-charge problem
• Example: Nori & Leets Co.
• Air pollution problem

• Increasing the height of the smokestacks involve a fixed charge of $2million

• The formulation is:

22
Integer Program
Innovative uses of binary variables in model formulation
Binary representation of general integer variables

Example:
• U = 5 for x1 and u = 10 for x2

• So the binary representation are:

• The constraints are:

• For x1 = 3 and x2 = 5, what is y?

23
Chapter 12: Integer Programming: Branch and Bound

IE 312
Operations
Research II
Second Semester
(2/2021)

24
Some perspectives on solving integer programming problems
Solving Integer Programming
• Some fallacies about solving IP
• IP with bounded feasible region also has finite number of solution
• IP has far fewer feasible solutions than LP
• So IP should be relatively easy to solve

However …

• Finite number can be very large and the number of solution grows exponentially
• And …
• Without the noninteger feasible solution, the optimal solution is not guaranteed to be at the
corner of the feasible region
• CPF solutions make solving LP efficiently possible, there is no such property for IP

• So … solving IP is difficult

25
Some perspectives on solving integer programming problems
Rounding solution from LP? → may be infeasible

26
Some perspectives on solving integer programming problems
Rounding solution from LP? → may be far from optimality

27
Some perspectives on solving integer programming problems

What can we do?

28
The branch-and-bound technique for binary integer programming
Branch-and-bound technique
• Pure IP has a finite number of feasible solutions → enumeration procedure can find optimal
solution

• Finite number can be very large → the procedure must be cleverly structured to examine
only small fraction of the total number of solutions

• Branch-and-bound technique utilizes “divide and conquer” concept

• Original large problem is “divide” into smaller subproblems … until the subproblems can be
“conquer”

• Dividing = branching = to partition the set of feasible solution into smaller subsets

• Conquering = fathoming = to find the bound on how good the best solution can be and
discard if the optimal solution is not in the subsets

• Three basic steps: branching → bounding → fathoming → repeat the process

29
The branch-and-bound technique for binary integer programming
Branch-and-bound technique
Example: California manufacturing co.

30
The branch-and-bound technique for binary integer programming
Branch-and-bound technique

Branching

31
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Branching
Example: California manufacturing co.
• To partition binary variable is to set the value equal to 0 and 1
• E.g. x1 = 0 and x1 = 1
• The smaller subproblems are

32
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Branching
Example: California manufacturing co.
• The dividing/branching create a tree

• The “All” node is the root node

• The branches are arc connecting one node to its two

subproblems

• The tree will grows branch iteration by iteration

→ “branching tree”

• The selection of variable to branch follow their natural order,

x1, x2, x3, …

33
The branch-and-bound technique for binary integer programming
Branch-and-bound technique

Bounding

34
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Bounding
Example: California manufacturing co.
• For each subproblem, the bound is how good the best feasible solution can be

• Not necessary the optimal solution (since it can be too difficult)

• Can relax the subproblem by delete some of the complex constraints

• Most widely used LP relaxation → relax the integer restriction

35
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Bounding
Example: California manufacturing co.
• For “All” node
• Replace “xj is binary for j = 1, 2 ,3 ,4” by

• The optimal solution is

• The bound is 16.5 which can be rounded down to 16

• All objective function coefficients are integer → Z value must also be integer

36
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Bounding
Example: California manufacturing co.
• For the subproblems
• Replace “xj is binary for j = 2 ,3 ,4” by

• The optimal solutions are

• The bounds are

37
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Bounding
Example: California manufacturing co.

38
The branch-and-bound technique for binary integer programming
Branch-and-bound technique

Fathoming

39
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Fathoming
Example: California manufacturing co.
• A subproblem is conquered = it is fathomed/dismissed from further consideration

Fathom situation 1)
• Subproblem 1 (x1 = 0) the optimal LP relaxation is (x1, x2, x3, x4) = (0, 1, 0, 1)
• The solution is integer
• It is the first incumbent = the best feasible solution found so far

• Z* = 9
• No further branching → only give inferior solution
• Subproblem 1 is now fathomed

40
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Fathoming
Example: California manufacturing co.
Fathom situation 2)
• Since Z* = 9, any subproblem whose bound ≤ 9 can be fathomed
• The feasible solution will be worse than the incumbent

Fathom situation 3)
• If the subproblem has no feasible solution

Summary of fathoming test: a sub problem is fathomed if

• Test 1): its bound ≤ Z*
• Test 2): its LP relaxation has no feasible solution
• Test 3): the optimal solution for its LP relaxation is integer (the incumbent is updated if the new
incumbent if founded + reapply test 1 to all unfathomed subproblems)

41
The branch-and-bound technique for binary integer programming
Branch-and-bound technique - Fathoming
Example: California manufacturing co.

42
The branch-and-bound technique for binary integer programming
Summary of the BIP branch-and-bound algorithm
Initialization:
• set Z* = -∞
• Apply bounding step, fathoming step, optimality test to the whole problem
• If not fathomed, let it be the remaining “subproblem” and proceed to the iteration

Steps for each iteration

Branching:
• Among the remaining unfathomed subproblems, select the most recently created one (break
ties using the larger bound)
• Branch from the node of this subproblem to create two new subproblem by fixing the next
variable (the branching variable) to 0 or 1

Bounding:
• For each new subproblem, solve for the optimal solution and Z of the LP relaxation
• If Z is not an integer, round it down to an integer
• Z is the bound for the subproblem

43
The branch-and-bound technique for binary integer programming
Summary of the BIP branch-and-bound algorithm (cont.)
Fathoming:
• For each new subproblem, apply the 3 fathoming test and discarded the fathomed
subproblems

Optimality test:
• Stop when there are no remaining subproblem that have not been fathomed & the current
incumbent is optimal
• Otherwise, go to next iteration

• In the branching step, an alternative is to select subproblem with best bound but as it is
likely to contain the optimal solution
• However, for solving large problem, utilizing the reoptimization tend to be more promising
than skipping around and start from scratch

44
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 2:
• Create 2 subproblems from node x1 = 1 → Subproblem 3 and 4

45
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 2:
• Fathom test 1 + 2 + 3 failed

46
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 2:

47
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 3:
• Subproblem 2 is replace by subproblem 3 and 4 → Select subproblem 4 due to its larger bound
• Create 2 subproblems from node x1 = 1, x2 = 1 → subproblem 3 and 4

48
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 3:
• Subproblem 5 give the same solution as subproblem 2 → all test failed
• Subproblem 6 is infeasible → fathomed by test 2

49
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 3:

50
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 4:
• 2 subproblems left unexamined, node (1, 0) and (1, 1, 0)
• Select the latter one (more recently created)
• x4 is the only variable left for branching
• x4 = 0 or 1 create “single solution” rather than subproblem

• The first pass test 3 with better solution than the incumbent → the new incumbent with Z* = 14
• The second pass test 2 → infeasible and fathomed

• Reapply test 1: Subproblem 3 pass test 1 and fathomed

• No unfathomed subproblem → the optimal solution is

51
The branch-and-bound technique for binary integer programming
Example: California manufacturing co. - Completing the example
Iteration 4:

52
The branch-and-bound technique for mixed integer programming
Branch-and-bound technique - MIP
• Some I variable are restricted to be integer (not necessarily binary)
• The rest are continuous

• Algorithm is similar to the BIP algorithm with 4 changes

53
The branch-and-bound technique for mixed integer programming
Branch-and-bound technique - MIP
• Change 1) select the integer-restricted variables that have a noninteger value in the
optimal solution of the LP relaxation in natural order

• Change 2) creating 2 subproblems by specifying two ranges of the variable values

• Let x*j be the noninteger value in the optimal solution

• The range for 2 new subproblems are

• E.g. x*j = 3.5 then

54
The branch-and-bound technique for mixed integer programming
Branch-and-bound technique - MIP
• Change 2)
• Recurring branching variable can occur

• Change 3) in the bounding step, the bound is not rounded down because some variables are
not integer restricted

• Change 4) in fathoming test 3), the optimal solution may not be integer
• only the integer restricted variable must be integer to pass test 3)

55
The branch-and-bound technique for mixed integer programming
Summary of the MIP branch-and-bound algorithm
Initialization:
• set Z* = -∞
• Apply bounding step, fathoming step, optimality test to the whole problem
• If not fathomed, let it be the remaining “subproblem” and proceed to the iteration

Steps for each iteration

Branching:
• Among the remaining unfathomed subproblems, select the most recently created one (break
ties using the larger bound)
• Branch from the node of this subproblem to create two new subproblem by selecting the
integer restricted variables that have a noninteger value in the optimal solution of the LP
relaxation
• Choose the variable by natural order → let it be xj with value of x*j
• Create 2 new subproblems by adding constraints

56
The branch-and-bound technique for mixed integer programming
Summary of the MIP branch-and-bound algorithm (cont.)
Bounding:
• For each new subproblem, solve for the optimal solution and Z of the LP relaxation
• If Z is not an integer, round it down to an integer
• Z is the bound for the subproblem

Fathoming:
• For each new subproblem, apply the 3 fathoming test and discarded the fathomed
subproblems
• Fathoming test: a sub problem is fathomed if
• Test 1): its bound ≤ Z*
• 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 variable (the incumbent is updated if the new incumbent if founded +
reapply test 1 to all unfathomed subproblems)

Optimality test:
• Stop when there are no remaining subproblem that have not been fathomed & the current
incumbent is optimal
• Otherwise, go to next iteration

57
The branch-and-bound technique for mixed integer programming
MIP example

Initialization:
• Set Z* = -∞
• Solve the LP relaxation to obtain the optimal solution

• Feasible solutions but noninteger for the integer restricted variables

• Not fathomed

58
The branch-and-bound technique for binary integer programming
MIP example
Iteration 1:
• The first integer restricted variable with noninteger value is x1 = 5/4 → the branching variable
• Create 2 subproblems

• Subproblem 1 fails all test

• Subproblem 2 is fathomed by test 2

59
The branch-and-bound technique for mixed integer programming
MIP example
Iteration 2:
• One subproblem remains (x1 ≤ 1)
• x2 = 6/5 → the next branching variable

• Both are feasible and noninteger

• Neither is fathomed

60
The branch-and-bound technique for mixed integer programming
MIP example
Iteration 2:

61
The branch-and-bound technique for mixed integer programming
MIP example
Iteration 3:
• Select subproblem 3 (larger bound)
• x1 = 5/6 → the next branching variable
• Recurring branching variable

• Subproblem 5 passes test 3 (integer values for integer restricted variables) fathom and update
the incumbent solution
• Incumbent = (0, 0, 2, ½) and Z* = 13.5
• Subproblem 6 pass test 2 (infeasibility) fathomed the node

62
The branch-and-bound technique for mixed integer programming
MIP example
Iteration 3:
• Select subproblem 3 (larger bound)
• x1 = 5/6 → the next branching variable
• Recurring branching variable

• Subproblem 5 passes test 3 (integer values for integer restricted variables) → fathom and
update the incumbent solution
• Incumbent = (0, 0, 2, ½) and Z* = 13.5
• Subproblem 6 passes test 2 (infeasibility) → fathomed the node
63
The branch-and-bound technique for mixed integer programming
MIP example
Iteration 3:
• Reapply test 1 to subproblem 4 → fathom subproblem 4

• No unfathomed subproblem
• The incumbent solution is optimal

64