Integer Programming
1. Integer Programming Graphical Solution
2. Integer Programming (IP) Models
3. Computer Solution of Integer Programming Problems With Excel
and QM for Windows
4. Branch and Bound Methods
Integer Programming Model
Integer programming (IP) problem is defined as an LP (Linear
Programming) which has some or all variables in positive integer
values
Types of IP Problem:
Pure IP problem: if all variables must be integer
Maximize z = 3x1 + 4x2
subject to 5x1 + 8x2 ≤ 24
x1, x2 ≥ 0, x1 dan x2 integer
Mixed IP problem: if only some variables are integer
Maximize z = 3x1 + 4x2
subject to 5x1 + 8x2 ≤ 24
x1, x2 ≥ 0, x1 integer
0-1 IP problem: if all variables must be 0 or 1
Maximize z = 3x1 + 4x2
subject to 5x1 + 8x2 ≤ 24
x1, x2 = 0 or 1
1
Integer Programming and LP relaxation
IP problems are usually more difficult to solve than LP problems
This is because there are many integer value combinations that
must be tested, and each combination requires a “normal” LP or
NLP solution
LP relaxation from IP is the LP which is obtained by removing all
integer constraints or constraints
E.g. Pure IP problem :
Maximize z = 3x1 + 4x2
subject to 5x1 + 8x2 ≤ 24
x1, x2 ≥ 0, x1 and x2 integer
E.g. Pure IP problem relaxed:
Maximize z = 3x1 + 4x2
subject to 5x1 + 8x2 ≤ 24
x1, x2 ≥ 0
Simple Approach for IP Solution
Approach 1:
Find all possible solutions
Determine its objective function values
Select the maximum (minimum) value
Approach 2:
Solve the LP relaxation
Round up/down the closer feasible integer solution
x2 7x1 + 4x2= 13
1
x x x x
1 2 3
x1
2
Integer Programming Solution
Example:
Max 1200 x1 + 2000 x2 x2
ST: 6
2x1 + 6 x2 27
x2 2 5
3x1 + x2 19
x1 , x2 0 and Integer 4
Use Integer 2
Programming to
solve the problem. 1
x1
Is the IP solution 1 2 3 4 5 6 7 8
rounded up/down
Optimal LP
to get the optimal x1 = 5 7/16
solution? x2 = 2 11/16
Integer Programming Solution (2)
LP relaxation, then round up/down?
x2
6 Round up/down?
x1 = 5
Max 1200 x1 + 2000 x2 5
x2 = 3
ST:
Round up?
2x1 + 6 x2 27 4
x1 = 6
x2 2 x2 = 3
3x1 + x2 19
3
x1 , x2 0 and Integer 2
Round down?
1
x1 = 5
x2 = 2
x1
1 2 3 4 5 6 7 8
Optimal LP
x1 = 5 7/16
x2 = 2 11/16
3
Integer Programming Solution (3)
x2
6
Optimal IP
x1 = 4
5 x2 = 3
x1
1 2 3 4 5 6 7 8
For MAX problem:
IP Optimal solution ≤ LP relaxation optimal solution
Integer Programming
Modeling
4
Case 1: Recreational Facilities Example (1)
A community council must decide which recreation facilities to construct
in its community. Four new recreation facilities have been proposed—a
swimming pool, a tennis center, an athletic field, and a gymnasium. The
council wants to construct facilities that will maximize the expected daily
usage by the residents of the community, subject to land and cost
limitations. The expected daily usage and cost and land requirements for
each facility follow:
The community has a $120,000 construction budget and 12 acres of land.
Because the swimming pool and tennis center must be built on the same
part of the land parcel, however, only one of these two facilities can be
constructed. The council wants to know which of the recreation facilities
to construct to maximize the expected daily usage.
Recreational Facilities Example (2)
Decision Variable:
Xi = 1 if the facility i is built,
= 0 otherwise
Objective Function:
Maximize Z = 300x1 + 90x2 + 400x3 + 150x4
Constraints:
subject to:
$35,000x1 + 10,000x2 + 25,000x3 + 90,000x4 $120,000 (budget)
4x1 + 2x2 + 7x3 + 3x3 12 (acres)
x1 + x2 1 (facility)
x1, x2, x3, x4 = 0 or 1
10
5
Recreational Facilities Example (3)
11
Recreational Facilities Example (4)
12
6
Recreational Facilities Example (5)
13
Recreational Facilities Example (6)
14
7
Recreational Facilities Example (7)
15
Recreational Facilities Example (8)
16
8
Case 2: Investment
Stockco Company considers 4 types of investment
Available capital for investment = $ 14,000
Formulate integer programming model to maximize NPV based on
the following investments:
Investment
1 2 3 4
Type
Capital ($) 5000 7000 4000 3000
NPV ($) 16000 22000 12000 8000
SOLUTION:
xi = total capital invested for investment type - i
Maximize
z = 16 x1+ 22 x + 12 x3 + 8 x4
Subject to
5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
x1, x2, x3, x4 = 0, 1
17
Investment
Stockco Company considers 4 types of investment
Available capital for investment = $ 14,000
Formulate integer programming model to maximize NPV based on
the following investments:
Investment
1 2 3 4
Type
Capital ($) 5000 7000 4000 3000
NPV ($) 16000 22000 12000 8000
SOLUTION:
xi = total capital invested for investment type - i
Maximize
z = 16 x1+ 22 x + 12 x3 + 8 x4
Subject to
5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
x1, x2, x3, x4 = 0, 1
18
9
Development of Investment Model
Stockco Co. needs to evaluate the following “logic” constraints:
1. Three investments are exactly selected
2. If Investment 2 is selected, then Investment 1 is selected either
3. If Investment 1 is selected, Investment 3 is not selected instead
4. One of Investment 3 or 4 must be selected, yet both can’t be
chosen
Additional constraints:
1. Three investments are exactly selected
x1+ x2+ x3+ x4 =3
2. If Investment 2 is chosen, then Investment 1 is chosen either
x1 ≥ x2
3. If Investment 1 is chosen, Investment 3 is not chosen instead
x1 + x3 ≤ 1
4. One of Investment 3 or 4 must be selected, yet neither is chosen
x3 + x4 = 1
19
Case 5: Fixed Charge and Facility
Frijo-Lane Food Products own farms in the Southwest and Midwest, where it grows
and harvests potatoes. It then ships these potatoes to three processing plants in
Atlanta, Baton Rouge, and Chicago, where different varieties of potato products,
including chips, are produced.
Recently, the company has experienced a growth in its product demand, so it wants
to buy one or more new farms to produce more potato products. The company is
considering six new farms with the following annual fixed costs and projected
harvest:
20
10
Case 5: Fixed Charge and Facility
The company currently has the following additional available production capacity
(tons) at its three plants, which it wants to utilize:
The shipping costs ($) per ton from the farms being considered for purchase to the
plants are as below.
The company wants to know which of the six farms it should purchase to meet
available production capacity at the minimum total cost, including annual fixed
costs and shipping costs.
21
Case 5: Fixed Charge and Facility
Decision Variables:
yi = 0 if farm i is not selected, and 1 if farm i is selected,
i = 1,2,3,4,5,6
xij = potatoes (tons, 1000s) shipped from farm i,
i = 1,2,3,4,5,6 to plant j, j= A,B,C.
Objective Function:
Minimize Z = 18x1A + 15x1B + 12x1C + 13x2A + 10x2B + 17x2C
+ 16x3A + 14x3B + 18x3C + 19x4A + 15x4b + 16x4C
+ 17x5A + 19x5B + 12x5C + 14x6A + 16x6B + 12x6C
+ 405y1 + 390y2 + 450y3 + 368y4 + 520y5 + 465y6
22
11
Case 5: Fixed Charge and Facility
Constraints:
23
Case 5: Fixed Charge and Facility
24
12
Case 5: Fixed Charge and Facility
25
Case 5: Fixed Charge and Facility
26
13
Case 5: Fixed Charge and Facility
27
Case 5: Fixed Charge and Facility
28
14
Case 5: Fixed Charge and Facility
29
Case 6: Gandhi’s Problem (Fixed Charge)
Textile Company - Gandhi produces 3 variety of clothing: shirts,
shorts, and trousers.
The machines must be rented every week to produce three types of
clothing at a rental fee, as follows:
$ 200 per week for shirt-making machine
$ 150 per week for shorts-making machine
$ 100 per week for trousers-making machine
There are 150 hrs of labor hours and 160 m² of clothing materials
available per week, with the following production data
Labor hours Materials Sales Variable
needed needed Price cost
Shirts 3 4 $12 $6
Shorts 2 3 $8 $4
Trousers 6 4 $15 $8
Formulate the problem to maximize weekly profit!
30
15
Gandhi’s Solution
Decision Variables:
xi = total number of clothing-i produced per week
yi = 1 clothing-i is produced, yet 0 not produced
Formulation:
Max. z = 6x1 + 4x2 + 7x3 – 200 y1 - 150 y2 - 100y3
subject to
3x1 + 2x2 + 6x3 150
4x1 + 3x2 + 4x3 160
x1 M y1, x1 y1
x2 M y2,
x3 M y3
x1, x2, x3 0, and integer
y1, y2, y3 0, and binary
31
LINDO
LINDO can be used to solve pure and mixed IPs.
In addition to the optimal solution, the LINDO output also
includes shadow prices and reduced costs.
LINGO and the Excel Solver can also be used to solve IPs
32
16
LINDO : “Gandhi” Problem
Definition of variables are placed after the command “END”
Definition of 0-1 or binary variables in LINDO
INTE x
Definition of integer variables in LINDO
GIN y
Example: GANDHI in LINDO:
33
LINDO : “Gandhi” Problem
LINDO
Solution:
34
17
Branch and Bound
Method
35
“Branch and Bound” Method
In practice, most IPs are solved by using the technique of Branch-and-
Bound
Branch-and-bound methods find the optimal solution to an IP by
efficiently enumerating the points in a subproblem’s feasible region.
Before explaining how branch-and-bound works, we need to make the
following elementary but important observation:
If you solve the LP relaxation of a pure IP and obtain a solution in which
all variables are integers, then the optimal solution to the LP relaxation
is also the optimal solution to the IP
36
18
Branch and Bound Strategy
The steps of Branch & Bound:
1) begins by solving the LP relaxation of the IP
2) Next step is to partition the feasible region for the
LP relaxation in an attempt to find out more about
the location of the IP’s optimal solution.
The Branch and Bound algorithm is a divide and
conquer algorithm, where a problem is divided into
smaller and smaller subproblems.
Each subproblem is solved separately, and the best
solution is taken.
37
Branch and Bound Strategy
38
19
Example
E.g. IP Problem:
Maximize z = 8x1 + 5x2
subject to
x1 + x2 6;
9x1 + 5x2 45;
x1, x2 ≥ 0; x1, x2 integer
The problem begins by dividing
solution into sub-problem
Sub-problem 1 is LP relaxation
solution of original problem.
Optimal LP Solution:
x1 = 3.75 and x2= 2.25
with z = 41.25
39
Feasible Region for Telfa’s Problem
Subproblem 1 : The LP relaxation
of original
Optimal LP Solution: x1 = 3.75
and x2 = 2.25 and z = 41.25
1 Subproblem 2: Subproblem 1 +
Constraint x1 4
Subproblem 3: Subproblem 1 +
Constraint x1 3
Subproblem 4: Subproblem 2 +
2 Constraint x2 2
Subproblem 5: Subproblem 2 +
Constraint x2 1
Feasible Region for Telfa Problem
40
20
Daerah Feasible untuk Sub-problem
Branching:
Process of dividing a sub-problem into
two or more sub-problems underneath
Subproblem 1 is divided by 2:
Subproblem 2: Subproblem 1 +
Constraint x1 4
(x1 value is rounded up)
Subproblem 3: Subproblem 1 +
Constraint x1 3
(x1 is rounded down)
Subproblem 2 - Optimal Solution:
z = 41, x1 = 4, x2 = 9/5 = 1.8
The optimal solution for Sub-
problem 1 has not yet produced an
integer number, and needs to be
branched again (using LIFO
concept, so Subproblem 3 is not
processed first) Feasible Region for
Subproblems 2 and 3 of Telfa Problem
41
Feasible Region for Subproblems 4 & 5
Subproblem 2 is divided by 2:
Subproblem 4: Subproblem 2 +
Constraint x2 2
(x1 value is rounded up)
Subproblem 5: Subproblem 2 +
Constraint x2 1
(x1 value is rounded down)
Subproblem 5 - Optimal Solution:
z = 40.05, x1 = 4.44, x2 = 1
Subproblem 2 optimal solution
has not yet produced an integer,
and needs to be further branched
Feasible Region for
Subproblems 4 and 5 of Telfa Problem
42
21
The Branch and Bound Tree
Optimal solution for Subproblem 5:
z = 40.05, x1 = 4.44, x2 = 1
Subproblem 5 is divided by 2:
Subproblem 6: Subproblem 5 + Constraint x1 5
Subproblem 7: Subproblem 5 + Constraint x1 4
43
Feasible Region for Subproblems 6 & 7
Optimal solution for
Subproblem 6:
z = 40, x1 = 5, x2 = 0
Optimal solution for
Subproblem 7:
z = 37, x1 = 4, x2 = 1
Feasible Region for
Subproblems 6 and 7 of Telfa Problem
44
22
The Branch and Bound Tree
1 2
45
The Branch and Bound Tree
3 4
46
23
Knapsack Problems
47
Contoh
48
24
Solving Knapsack Problems
Max z = 16x1+ 22x2 + 12x3 + 8x4
subject to
5x1+ 7x2 + 4x3 + 3x4 14
xi = 0 or 1 for all i = 1, 2, 3, 4
LP Relaxation:
Max z = 16x1+ 22x2 + 12x3 + 8x4
subject to
5x1+ 7x2 + 4x3 + 3x4 14
0 xi 1 for all i = 1, 2, 3, 4
Soving the LP Relaxation:
Order xi’s in the decreasing order of ci/ai where ci are the
cost coefficients and ai’s are the coefficients in the
constraint
Select items in this order until the constraint is satisfied with
equality
49
Solving Knapsack Problems
Using Branch and Bound:
1) We used the LIFO approach to determine which subproblem
should be solved.
2) We arbitrarily chose to solve subproblem 3 before subproblem 2.
To solve subproblem 3, we first set x3 = 1 and then solved
the resulting knapsack problem.
After setting x3 = 1, 14 – 4 = $10 million was still available for
investment.
Applying the technique used to solve the LP relaxation of a
knapsack problem yielded the following optimal solution to
subproblem 3: x3 = 1, x1 = 1, x2 = 5/7, x4 = 0, Z = 306/7
3) Other subproblems were solved similarly; of course,
If a subproblem specified xi = 0, the optimal solution to that
subproblem could not use investment i.
Subproblem 4 yielded the candidate solution x1 = x3 = x4 = 1,
z = 36. We then set LB = 36.
50
25
Solving Knapsack Problems
Using Branch and Bound:
4) Subproblem 6 yielded a candidate solution with z = 42. Thus,
subproblem 4 was eliminated from consideration, and the LB was
updated to 42.
5) Subproblem 7 was infeasible because it required x1 = x2 = x3 = 1,
and such a solution requires at least $16 million.
6) Subproblem 8 was eliminated because its z-value (z = 38) did not
exceed the current LB of 42.
7) Subproblem 9 had a z-value of 300/7. Because the z-value for any
all-integer solution must also be an integer, this meant that
branching on subproblem 9 could never yield a z-value larger than
42.
Thus, further branching on subproblem 9 could not beat the
current LB of 42, and subproblem 9 was eliminated from
consideration.
51
The Branch and Bound Tree
Subproblem 1
z = 44
1 x1 = x2 = 1
x3 =.5
x3 = 1
x3 = 0
Subproblem 3
Subproblem 2
z = 43.7
z = 43.3, LB=42 2
x1 =x3= 1,
7 x1 = x2=1
x3 = 0, x4 =.67 x2 = .7, x4=0
x2 = 0 x2 = 1
x4 = 0 x4 = 1
3 4
Subproblem 8 Subproblem 9 Subproblem 4 Subproblem 5
z = 38, LB=42 z= 42.85, LB=42 z = 36 z = 43.6
8 x1 = x2=1 9 x1 = x4 =1 x1 = x3=1 x1 =.6, x2=x3=1
x3 = x4 = 0 x3 = 0, x2 = .85 x2 = 0, x4 =1 x4 = 0, LB = 36
x1 = 0 x1 = 1
Subproblem 6
Subproblem 7
z = 42
LB = 42
5 x1 =0, x2=x3=1 6
Infeasible
x4 = 1, LB = 36
52
26
