Integer Programming

DSO 547: Spreadsheet-Based Business

Modeling
Professor Bala Subramanian

1
Optimization Models
 Linear Programming (LP) Models
 Both objective and constraints are linear

functions of the decision variables.

 Integer Programming (IP) Models
 Objective and constraints are linear;

 Some variables must take integer values;

 Two types: integer linear programming, and

integer nonlinear programming

 Non-linear Programming (NP) Models
 Either objective or constraints are non-linear.

2
Outline
 Session 6
 Intro to Integer Programming
 Veerman Furniture revisited & Queen City problem
 Binary Variables: Capital Budgeting Problem
 Conditional constraints and Multiple-Choice constraints
 All or nothing constraints
 Binary Variables: Baseball Pitcher Selection problem
 Binary Variables: Emergency Medical Services
 Fixed Costs: Mayhugh Manufacturing problem
 Fixed Costs: Levinson Problem
 Solving Integer Programs: Branch and Bound algorithm
 Tatham Capital Budgeting Problem

3
Solver Behavior
 LP Models: Always find an optimal solution
 ILP Models: May take a long time to find
an optimal solution
 NP & INP Models: Cannot find an optimal
solution in general
Try the solver from different starting points,
choose the best solution.
 Whenever possible, model as LP.

4
Two Types of Integer Linear
Programming Models
 Some ILP models are simply LP models with certain
variables constrained to be integers
 Building such an ILP model requires just a couple

of additional steps beyond an LP model

 Some LP models generate integer solutions, e.g.

transportation models and assignment models

 Other ILP models (especially with binary variables)
can achieve more than LP models can do, but
require other modeling techniques

5
Sensitivity Analysis for
Integer Linear Programs
 Shadow prices, allowable ranges and reduced
costs are meaningless for ILPs.
 Sensitivity analysis must be performed
manually by changing parameters and re-
solving the model.

6
Solver Setup
 Solver constraints window allows
choices of int and bin for any variable
 int: variable must be an integer
 bin: variable must be binary, i.e, 0 or 1

7
Solver Setup
 Solver Tolerance parameter is set at 5%
(away from true optimum) initially
 Allows for fast solutions

 Used during debugging, or

 For solving large problems

 Set close to 0 after debugging, or for

smaller problems

8
An LP Model with Integer Solution
Veerman Furniture revisted

9
 Veerman Furniture with Non-integer Solution:
Fabrication capacity changed to 1800 (from 1850)

Suppose
Fabrication
had 1800
hours
available
instead of
1850 hours

10
When are Integer solutions
important?
 Situations where fractional values are
sufficient (LP is valid):
 Example--Veerman Furniture: 266.67

desks can be rounded to 266

 It can be interpreted as average

production quantity
 Situations integer values are necessary:
 Airplane production
 Project selection
 Employee scheduling
11
Example when Round-up Doesn’t
Work: Queen City Inc. problem
 Two machines: TopLathe, BigPress
 At least 5 machines per month
 Component requirements and profits:

TopLathe BigPress
Components 10 7
Profits $50,000 $34,000

 Components available: 49

12
Mathematical Model

Maximize 50,000x1 + 34,000x2

Subject to
10x1 + 7x2 ≤ 49
x1 + x 2 ≥ 5
x1, x2 ≥ 0 and integer

13
Excel Model: LP Relaxation

14
Excel Model: IP

15
 Graphical Solution

Feasible
Region: ABC
C

16
Binary Variables
 All or nothing variables (0 or 1)
 Represent go/no-go decisions
 PROJi = Indicator for Project i = 1, accept i
0, reject i

 Can use to represent structural or policy relationships

 Select at least m of the possible projects
 Select at most n of the possible projects
 Other logical relationships

17
Example: Project Selection
 Capital budgeting
 $160m budget for five possible capital
projects
 NPV and capital expenditures of the projects:

Project P1 P2 P3 P4 P5
NPV ($m) 10 17 6 8 14
Expenditure ($m) 48 96 80 32 64

 Maximize total NPV, subject to expenditures

of no more than $160m

18
Math Model
 Decision Variables:
P1, P2, P3, P4, P5 (binary)
(projects selected or not)

 Objective:
max Total NPV ($m)
= 10P1 + 17P2 + 6P3 + 8P4 + 14P5

 Constraints:
48P1 + 96P2 + 80P3 + 32P4 + 64P5 <= 160
(Expenditure) 19
Excel Model

20
Multiple Choice Constraints
 Choose exactly one of projects 2 and 5 (both are international
projects)
P2 + P5 = 1
 Choose at most one of projects 2 and 5 (require some of the same
resources)
P2 + P5 <= 1
 Choose at least one of projects 2 and 5

P2 + P5 >= 1
 By adding similar constraint, we can select at least m of the
projects or at most n of them.

21
Conditional Constraints
 If project 5 is chosen, then project 3 must be chosen
P5 <= P3 (or P3 - P5 >= 0)
 If project 3 is chosen, then project 1 or 2 (or both) must be
chosen
P3 <= P1 + P2
 If project 3 is chosen, then projects 1 and 2 must be chosen

2 * P3 <= P1 + P2
(P3 <= P1 & P3 <= P2)

22
Modeling Tip: Excel Use
 The logical functions in Excel (IF, AND, OR, etc.)
can express logical relationships
 Such functions are nonlinear
 Models with IF statements will often stop at local
optimum
 Using binary variables is the preferred approach

23
Example: Baseball Problem
 The Cubs are choosing from free-agent pitchers: Rick
Sutcliffe (RS), Bruce Sutter (BS), Dennis Eckersley
(DE), Steve Trout (ST), or Tim Stoddard (TS).
 Data table (next page)
 Constraints:
 At most $12 million can be spent

 At most two right-handed pitchers

 Cannot sign both BS and RS

 Goal: sign the pitchers to add the most victories

24
Data
Cost of Signing Victories Added
Pitcher ($m) to Cubs

RS (righty) $6 6
BS (righty) $4 5
DE (righty) $3 3
ST (lefty) $2 3
TS (righty) $2 2

25
Math Model
 Decision Variables:
RS, BS, DE, ST, TS (binary)
 Objective:
max total number of victories =
6RS + 5BS + 3DE + 3ST + 2TS
 Constraints:
(Cost) 6RS + 4BS + 3DE + 2ST + 2TS <= 12
(Righty) RS + BS + DE + TS <= 2
(Conflict) RS + BS <= 1

26
Excel Model

27
Example: Emergency Coverage (I)

 The City of Metropolis is divided into nine

districts and is considering seven possible
sites to place emergency vehicles
 The time (minutes) it takes an emergency
vehicle to travel from each site to each district
is shown in the next table
 Find the minimum number of sites so that all
districts are within three minutes of an
emergency vehicle.

28
Distance Table
Minutes between Sites and Districts
Sites
1 2 3 4 5 6 7
1 5 3 4 3 8 9 0
2 3 6 5 4 8 0 3
3 4 3 6 8 10 3 2
Districts 4 6 0 2 7 3 2 5
5 2 8 2 5 0 6 8
6 2 6 4 0 7 3 5
7 0 12 5 5 5 7 2
8 10 9 0 2 3 5 7
9 2 4 5 7 3 4 5

29
Coverage Matrix
for travel time = 3 mins

Site 1 2 3 4 5 6 7

District 1 0 1 0 1 0 0 1
2 1 0 0 0 0 1 1
3 0 1 0 0 0 1 1
4 0 1 1 0 1 1 0
5 1 0 1 0 1 0 0
6 1 0 0 1 0 1 0
7 1 0 0 0 0 0 1
8 0 0 1 1 1 0 0
9 1 0 0 0 1 0 0

30
Excel Model

31
Example: Emergency Coverage
(II)
 The population of each district (in
thousands) is as follows:
1 2 3 4 5 6 7 8 9
40 30 35 20 15 50 45 60 30

 Suppose Metropolis has only two

emergency vehicles
 Decide the locations of the vehicles to
maximize the number of people who live
within three minutes of an emergency
vehicle.
32
Mayhugh Manufacturing
(model with fixed costs)
 Mayhugh Manufacturing Company
 3 product families

 3 departments

 If a product is made, a fixed setup cost will be

incurred
 Setup cost may be sales cost or cost of sending up a
production line
 Objective: Find the optimal product mix that
maximizes profit

33
Mayhugh Manufacturing
Product F1 F2 F3
Unit Profit 1.2 1.8 2.2

Requirements
Hours available
Dept A 3 4 8 2000
Dept B 3 5 6 2000
Dept C 2 3 9 2000

Fixed cost 60 200 100

Demand Potential (UB) 400 300 50
Minimum Production(LB) 300 200 20

Objective: Find the optimal product mix

that maximizes profit

34
Fixed Costs and Upper Bounds
 Notation
 F – fixed cost
 c – per unit cost
 x – units of activity (regular variable)
 y – go/no go of activity (binary variable)
 Cost = Fy + cx (in the objective)

35
Linking Constraints
 Linking constraint for Upper Bound
x <= My or equivalently, x - My <= 0
 M = upper bound on x
 If y=0, we must have x =0
 Substituting y=0 in x <= My, we get x <= 0
 By non-negativity x>=0
 x has to be equal to 0
 If y=1, substituting y=1 in x <= My, we get x <=M

 Linking constraint for Lower Bound

x >= my or equivalently, x - my >= 0
 m = lower bound on x
 If y=0, we must have x >=0, which is just non-negativity
 If y=1, substituting y=1 in x >= my, we get x >=m
36
Summary of Linking Constraints
 x – units of activity (regular variable)
 m – lower limit of x when x>0
 M – upper limit of x when x>0
 y – go/no-go of activity (binary variable)
 Linking constraints:

x >= my OR x - my >= 0 (lower limit)

and x <= My OR x – My <= 0 (upper limit)
 If y=0 we have x>=0 & x<=0 (so x=0)
 If y=1 we have x>=m & x<=M (so x is in the
desired region)

37
 Model with Upper Bounds - 1
Objective Function
Maximize Net Profit =1.20 x 1 + 1.80 x2 + 2.20 x3 - 60 y1 - 200 y2 - 100 y3
Constraints
 Capacity constraints
3 x1 + 4 x2 + 8 x3 <= 2000
3 x1 + 5 x2 + 6 x3 <= 2000
2 x1 + 3 x2 + 9 x3 <= 2000
 Upper Bound constraints
x1 <= 400
x2 <= 300
x3 <= 50
 Linking constraints for UB:
x1 - M y1 <=0 (can choose M=400)
x2 - M y2 <=0 (can choose M=300)
x3 - M y3 <=0 (can choose M=50)
 Non-negativity
 y is binary

38
 Model with Upper Bounds-2
 By choosing M properly, we can combine the Upper Bound
constraints with the linking constraints
Objective Function
Maximize Net Profit =1.20 x1 + 1.80 x2 + 2.20 x3 - 60 y1 - 200 y2 - 100 y3
Constraints
 Capacity constraints

3 x1 + 4 x2 + 8 x3 <= 2000
3 x1 + 5 x2 + 6 x3 <= 2000
2 x1 + 3 x2 + 9 x3 <= 2000
 Linking constraints incorporating Upper Bound constraints:
x1 - 400 y1 <=0 (can choose M=400)
x2 - 300 y2 <=0 (can choose M=300)
x3 - 50 y3 <=0 (can choose M=50)
 Nonnegativity
 y is binary
39
 Model with Lower & Upper Bounds-2
Objective Function
Maximize Net Profit =1.20 x1 + 1.80 x2 + 2.20 x3 - 60 y1 - 200 y2 - 100 y3
Constraints
 Capacity constraints
 Linking constraints incorporating Upper Bound constraints:
 Linking constraints incorporating Lower Bound constraints:
x1 – 300 y1 >=0 (can choose m=300)
x2 - 200 y2 >=0 (can choose m=200)
x3 - 20 y3 >=0 (can choose m=20)
 Non-negativity
 y is binary

40
Model with Fixed Costs regardless if
Product is made (no linking)

41
Model with Fixed Costs only when
Product is made (upper bound linking)

Upper limit (threshold

X2 – 300*Y2 <= 0

42
Model with Threshold Constraints & Fixed costs
when product is made (upper & lower linking)

Upper limit (threshold):

X2 – 300*Y2 <= 0

Lower limit (threshold):

X2 – 250*Y2 >= 0

43
Levinson Problem
 This is a capacitated facility location problem
 There are 6 plants that can supply 10
warehouses
 We know demand in each warehouse location
and capacity in each plant location
 Also cost of transportation between each plant
and each warehouse
 Issue is that there is a fixed cost associated with
operating each plant
 What is the optimum solution?
44
Facility Location: Capacitated
(fixed costs to operate plants)

• Capacity of plants cannot be exceeded

• If plant is operational, fixed costs are incurred
• Demand at each warehouse must be met (if possible)
• How would you plan to meet warehouse demand from available
plants to minimize overall cost (fixed + transportation)?
45
Facility Location: Capacitated

Linking Constraint: Sent - Capacity * Open? <= 0

46