Management Science
Integer Linear Programming
Management Science
Management Science
Intro to Integer Programming
u Main assumption: that some (or all) variables can assume
only integer values u Three common variations: Pure IP -- all variables are integer Mixed integer linear programs (MILP) -- some variables are integers Zero-one IP -- the integer variables are binary and can take only the values one (yes) or zero (no) u Most IPs are very difficult to solve Thus, special algorithms for specific classes Heuristics important -- close -to-optimal solutions that are relatively easy to find
Management Science
Management Science
Integrality Conditions MAX: 350X 1 + 300X2 S.T.: 1X1 + 1X2 <= 200 9X1 + 6X2 <= 1566 12X1 + 16X2 <= 2880 X1, X2>= 0 X1, X2 must be integers } profit } pumps } labor } tubing } nonnegativity } integrality
Integrality conditions are easy to state but make the problem much more difficult (and sometimes impossible) to solve.
Management Science
Management Science
Relaxation
u
Original ILP
MAX: 2X1 + 3X2 S.T.: X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 , X2 >= 0 X1 , X2 must be integers u LP Relaxation MAX: 2X1 + 3X2 S.T.: X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 , X2 >= 0
Management Science
Management Science Integer Feasible vs. LP Feasible Region X2 Integer Feasible Solutions
3
0 0
Management Science
X1
Management Science
Solving ILP Problems
u
When solving an LP relaxation, sometimes you get lucky and obtain an integer feasible solution. u This was the case in the original Blue Ridge Hot Tubs problem in earlier chapters. u But what if we reduce the amount of labor available to 1520 hours and the amount of tubing to 2650 feet?
Management Science
Management Science
Bounds
u
The optimal solution to an LP relaxation of an ILP problem gives us a bound on the optimal objective function value. For maximization problems, the optimal relaxed objective function values is an upper bound on the optimal integer value. For minimization problems, the optimal relaxed objective function values is a lower bound on the optimal integer value.
Management Science
Management Science
Rounding
u
It is tempting to simply round a fractional solution to the closest integer solution.
In general, this does not work reliably: The rounded solution may be infeasible. The rounded solution may be suboptimal.
Management Science
Management Science How Rounding Down Can Result in an Infeasible Solution X2
3
optimal relaxed solution infeasible solution obtained by rounding down
0 0
Management Science
X1
Management Science
Branch-and-Bound
u
The Branch-and-Bound (B&B) algorithm can be used to solve ILP problems.
Requires the solution of a series of LP problems termed candidate problems. u Theoretically, this can solve any ILP. u Practically, it often takes LOTS of computational effort (and time).
Management Science
Management Science
The Branch-And-Bound Algorithm
MAX: 2X1 + 3X2 S.T. X1 + 3X2 <= 8.25 2.5X 1 + X 2 <= 8.75 X1, X2 >= 0 and integer
Management Science
Management Science X2
3
Solution to LP Relaxation
Feasible Integer Solutions
Optimal Relaxed Solution X1 = 2.769, X2=1.826 Obj = 11.019
0 0 1 2 3 4
X1
Management Science
Management Science
The Branch-And-Bound Algorithm
Problem I
MAX: S.T. 2X1 + 3X 2 X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 <= 2 X1, X2 >= 0 and integer
Problem II
MAX: S.T.
2X1 + 3X 2 X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 >= 3 X1, X2 >= 0 and integer
Management Science
Management Science X2
3
Solution to LP Relaxation
Problem I
X1=2, X2=2.083, Obj = 10.25
Problem II
1
0 0 1 2 3 4
X1
Management Science
Management Science
The Branch-And-Bound Algorithm
Problem III
MAX: S.T. 2X1 + 3X 2 X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 <= 2 X2 <= 2 X1, X2 >= 0 and integer
Problem IV
MAX: S.T.
2X1 + 3X 2 X1 + 3X2 <= 8.25 2.5X1 + X2 <= 8.75 X1 <= 2 X2 >= 3 X1, X2 >= 0 and integer
Management Science
Management Science X2
3
Solution to LP Relaxation
Problem III
X1=2, X2=2, Obj = 10 (Integer!)
Problem II
X1=3, X2=1.25, Obj = 9.75
0 0 1 2 3 4
X1
Management Science
Management Science
B&B Summary
Original Problem X1=2.769 X2=1.826 X1>=3 Obj = 11.019 Problem II Problem I X1=2 X2=2.083 Obj = 10.25 X1=3 X2=1.25 Obj = 9.75
X1<=2
X2<=2
Problem III X1=2 X2=2 Obj = 10
X2>=3
Problem IV infeasible
Management Science
Management Science
Some Common IP Formulation Techniques
u u u u u
All-or-nothing binary variables Start-up variables Fixed costs Capital budgeting with project dependencies Either-or constraints Satisfying a subset of constraints
Management Science
Management Science
All-or-Nothing Binary Variables
u
Example: simple production profit maximization subject to a constraint on time: max 100a + 400b subject to 3a + 5b < 50 u Suppose an optional second shift would add 35 hours to the available time for $500 Define y as a binary variable: 1 if we choose to use the second shift and 0 if we dont max 100a + 400b -500y subject to 3a + 5b < 50 + 35y
Management Science
Management Science
All-or-Nothing, cont.
u
Suppose a third shift is available with 30 hours for $700 max 100a + 400b - 500y - 700z subject to 3a + 5b < 50 + 35y + 30z u What if we cannot use third shift unless second shift used as well? Add constraint: z < y u What if at most one additional shift can be used? Add constraint: y + z < 1
Management Science
Management Science
Start-up Variables
u
In some situations, if we do something, we have to do at least a minimal amount of it Produce so many widgets, buy so many shares of stock Example of disjoint feasible set u Example: if stock A is purchased then we must purchase at least 1000 shares and no more than 10000 Let a = 1 if we purchase stock A and let A be the number of shares A > 1000a AND A < 10000a
Management Science
Management Science
Fixed Costs
u
Often, situations involve both fixed and variable costs u Example: buying stock involves a per share price plus a fixed commission Stock cost is cA + pAA or 0 Objective function becomes cAa + pAA Constraint of the form A < Ma is necessary to make this work correctly, where M is the largest number of shares we will purchase (or the limit, as above)
Management Science
Management Science
Capital Budgeting
u Budgets often require choosing between inter-related
projects
u Example: suppose we have 6 projects---let yi be binary
variables set to 1 if project i is invested in, and the interactions are as follows: Project 3 can only be done if project 2 is also done We must invest in at least one of the first three projects Only one of projects 2, 4 and 6 can be done Exactly two of the last four projects must be invested in, but we do not care which ones
Management Science
Management Science
Capital Budgeting, cont.
u
Project 3 can only be done if 2 is also done Add constraint: y3 < y2 u We must invest in at least one of the first three projects Add constraint: y1 + y2 + y3 > 1 u Only one of projects 2, 4 and 6 can be done Add constraint: y2 + y4 + y6 < 1 u Exactly two of the last four projects must be invested in, but we do not care which ones Add constraint: y3 + y4 + y5 + y6 = 2
Management Science
Management Science
Either-Or Constraints
u
Sometimes there are at least two ways that a certain requirement can be satisfied u Example: suppose that the problem is either to satisfy 5x + 2y < 10 OR 3x - 4y < 24 Let z = 0 if the first constraint is to hold and z = 1 if the second one is to hold Let M be a large enough number that any likely combination of x and y would satisfy 5x + 2y < M and 3x - 4y < M
Management Science
Management Science
Either-Or Constraints, cont.
u
5x + 2y < 10 + Mz 3x - 4y < 24 + M(1-z) u Satisfying k out of m constraints is just an extension Let yi = 1 if constraint i is to be satisfied A constraint yi > k will force at least k constraints to be satisfied M must be large enough to satisfy each constraint Each constraint will now look like:
Add constraints:
aij x j bi yi + (1 yi ) M
Management Science
Management Science
Solving IPs in Excel
General integer variables Add constraint to limit variables to integers Dont forget non-negativity u Binary variables In Excel 7.0, three constraint sets necessary (variables >= 0, <= 1, integer) In Excel 8.0, choose bin option from constraint dialog box
Management Science
Management Science
Solving IPs in Excel, cont.
u
Be aware of default Tolerance value of 5% Youll want to change this to 0% in most cases u Sensitivity analysis report no longer available Still need to explore sensitivity of solution to changes in neighborhood of optimal u Still need Assume Linear Model option u Use Automatic Scaling if numbers of different orders of magnitude involved Use common sense in setting large numbers
Management Science
