Introduction to Integer
Programming
MSCI 603
Intro to Integer Programming
Same as Linear Programs, but with the addition of integer
requirements
Types of integer variables:
General integer: 0, 1, 2, 3, …
Binary: 0 or 1
Types of integer programs:
Pure integer: All variables integer and ≥ 0
Mixed integer: Some variables restricted to be integer
Binary: All variables either 0 or 1
2
Example 1:
Solve the problem graphically:
max z = x1 + 4 x2
s.t. 6 x1 + 5 x2 £ 30
- x1 + x2 £ 3
2 x1 + 5 x2 £ 20
x1 , x2 ³ 0 and integer
3
Example 1: LP Relaxation Solution
x2 Constraint 1
8
Constraint 2
7
Constraint 3
6
5
LP Optimal Solution: x1 = 0.714286, x2 = 3.714286
4 OFV = 15.57143
0
0 1 2 3 4 5 6 7 8 9 10 11 12
x1
MSCI 603 [email protected]
4
Example 1: Rounding the LP Solution
x2 Constraint 1
8
Constraint 2
7
Constraint 3
6 Round up:
x1 = 0.714286 à 1
5 x2 = 3.714286 à 4
Solution is infeasible!
4
3 Round down:
x1 = 0.714286 à 0
2 x2 = 3.714286 à 3
OFV = 12
1 But is this the optimal all-integer solution?
0
0 1 2 3 4 5 6 7 8 9 10 11 12
x1
MSCI 603 [email protected]
5
Example 1: Optimal IP Solution
x2 Constraint 1
8
Constraint 2
7
Constraint 3
6
5
IP Optimal Solution: x1 = 2, x2 = 3
4 z(IP) = 14
3
Recall: z(LP) = 15.57143
2
0
0 1 2 3 4 5 6 7 8 9 10 11 12
x1
MSCI 603 [email protected]
6
Relationship between IP and LP
LP-relaxation solution is always as good as or better than
the IP solution
E.g. for a max problem: z(IP) ≤ z*(IP) ≤ z*(LP-relaxation)
No sensitivity report
Only meaningful for continuous variables
To perform sensitivity analysis on an IP, must re-solve the
entire model with the changes in question
IP problems are often extremely sensitive to changes in
parameters
7
Example 2: Capital Budgeting
Your company is considering investing in several projects that have
varying capital requirements over the next four years. Faced with
limited capital each year, management would like to select the most
profitable projects. The estimated net present value for each project, the
capital requirements, and the available capital over the four-year period
are shown below. Determine the projects that you should invest in to
maximize the net present value of the capital budgeting projects.
Total Capital
Project 1 Project 2 Project 3 Project 4
Available
Present Value $90000 $40000 $10000 $37000
Year 1 Cap Rqmt $15000 $10000 $10000 $15000 $40000
Year 2 Cap Rqmt $20000 $15000 $10000 $50000
Year 3 Cap Rqmt $20000 $20000 $10000 $40000
Year 4 Cap Rqmt $15000 $5000 $4000 $10000 $35000
8
Example 2: Capital Budgeting
9
Modeling Techniques
Logical Constraints
a) Of projects 1, 3, and 4, no more than one can be selected
(mutually exclusive)
b) Of projects 1, 3, and 4, exactly one must be selected
a) Project 4 cannot be selected unless project 3 is also selected
(if project 4 is selected then project 3 must be selected)
(conditional or prerequisite)
10
Example 3: Fixed Charge Problem
Remington Manufacturing wants to figure out the optimal
way to set up their production based on the following
information.
Hours Required by
Operation Product 1 Product 2 Product 3 Hrs Available
Machining 2 3 6 600
Grinding 6 3 4 300
Assembly 5 6 2 400
Unit Profit $48 $55 $50
Setup Cost $1000 $800 $900
11
Example 3: Fixed Charge Problem
12
Example 3: Fixed Charge Problem
13
Example 4: Set Covering Problem
There are six cities in the district. The county’s fire department
must determine where to build fire stations. They want to build
the minimum number of fire stations needed to ensure that at
least one fire station is within 15 minutes (driving time) of each
city. The times (in minutes) required to drive between the cities
are shown below.
City 1 City 2 City 3 City 4 City 5 City 6
City 1 0 10 20 30 30 20
City 2 10 0 25 35 20 10
City 3 20 25 0 15 30 20
City 4 30 35 15 0 15 25
City 5 30 20 30 15 0 14
City 6 20 10 20 25 14 0
MSCI 603
[email protected] 14
Example 4: Set Covering Problem
15
Either-Or Constraints
Given two conditions of the form
f1(x1, x2, x3, …, xn) ≤ 0
f2(x1, x2, x3, …, xn) ≤ 0
Introduce a new variable and a constant:
y = 1 if f2(x1, x2, x3, …, xn) ≤ 0 is true; 0 otherwise
M, a very large number
Add these constraints to the model:
f1(x1, x2, x3, …, xn) ≤ My
f2(x1, x2, x3, …, xn) ≤ M(1 – y)
16
Example 5: Job Sequencing
A company must complete three jobs. The amounts of processing time
(in minutes) required are shown below. A job cannot be processed on
machine j unless for all i < j the job has completed its processing on
machine i. Once a job begins its processing on machine j, the job
cannot be preempted on machine j. The flow time for a job is the
difference between its completion time and the time at which the job
begins its first stage of processing.
Machine
Job 1 2 3 4
1 20 - 25 30
2 15 20 - 18
3 - 35 28 -
Formulate an IP whose solution can be used to minimize the flow time
of the three jobs
MSCI 603
[email protected] 17
Example 5: Job Sequencing
18
Example 5: Job Sequencing
19
Knapsack Problems
An IP with only one constraint is called a knapsack problem
Problem Setting:
n items to be packed into one knapsack
Knapsack capacity = W
Each item has “weight” wi and benefit bi
Goal:
Pack the knapsack such that the total benefit is maximized
20
Knapsack Problems
21
