MSBA 403:
Optimization
Lecture 2
November 13, 2020
Lecture 1 Recap
§ Structure of a mathematical program
§ Decision variables
§ Constraints
§ Objective (minimize or maximize)
§ Examples of linear programs (LPs) § Bag production
§ Cargo revenue management § Product delivery
§ Geometry of LPs and simplex algorithm
§ Constraints define a “feasible region” for the LP
§ One of the corner points (extreme points) of the feasible region is always optimal
2
Sensitivity analysis
§ The purpose of performing a sensitivity analysis is to understand how the optimal value of an optimization problem varies as one of the parameters changes
§ Doing this gives us an idea of the value of a particular resource
§ In linear programs, the shadow price of a constraint describes the change in the optimal value from a small increase in the right hand side of the constraint
§ Let’s see how to perform sensitivity analyses in Jupyter
3
Absolute value functions in LPs
§ What if the objective function contains absolute values? E.g., min |f(x)|
§Notethat |f(x)|z ifandonlyif f(x)z andf(x) z f (x)
z § Then we have
z min z
(Non-linear)
min |f (x)| () s.t. z f (x) (Linear!) z f(x)
4
Example: Inventory management
Suppose you are managing the inventory of a warehouse over periods i = 1, 2, …, N, and you are required to meet demand di in each period i. You need to decide how much product to order in each period. There are two costs involved:
§ For every unit of product held in inventory from the end of period i to the beginning of period i + 1, you incur a holding cost of c1.
§ if you change the quantity of product ordered in i to a different amount in i + 1, you incur a cost that is equal to c2 multiplied by the absolute value of the change. For example, if your order quantity from one period to the next increases or decreases by 5 units, the associated order change cost is 5*c2.
Assume you start with zero inventory. Formulate a linear programming model for this problem.
5
Example: Inventory management
A cost minimizing solution is given by the LP:
min c1
XN i=1
XN si + c2 yi
i=1
Minimize total cost
Inventory balance constraint for period 1
s.t. s1 = x1 d1
si=si 1+xi di, i=2,…,N,
yi xi xi+1, i=1,…,N, yi xi+1 xi, i=1,…,N, xi,yi,si 0, i = 1,…,N.
Inventory balance constraint for periods 2…N
Absolute deviation from previous order quantity
6
Integer programming
§ In linear programs, all decision variables are continuous
§ We might also have an optimization problem where decisions are inherently discrete, e.g. “yes or no” type
decisions
§ This requires the use of binary variables
0 , i 0f , i i =f i n =o n o xi =xi =
1 , i 1 f , i i = f i y =e s y e s
§ Binary variables allow us to model an broad range of decisions § Should we build a warehouse at location i?
§ Should we buy ads in market i?
§ Should we invest in project i?
§ Should we assign surgery i to operating room j at time k?
§ Optimization models with binary variables are called integer programs
§ More specifically, when the objective an all constraints are linear, the model is an integer linear program
((
7
Example: Fleet assignment at Delta Air Lines
§ In 1994, Delta Air Lines flew 2,500 domestic flight legs each day, using 450 different aircraft from 10 different fleet types
§ Every empty seat on an airline is lost revenue — the goal is therefore to determine a schedule that captures as much business as possible
§ A major component of an airlines schedule is the fleet assignment problem, which is to determine which aircraft should be assigned to each flight leg
§ Delta developed a mixed-integer optimization model to solve the fleet assignment problem, which was estimated to save $100 million per year
8
Example: Chilean soccer league
§ Sports scheduling: Which teams should play each other, and when?
§ Many factors to consider, including
§ Balance (equal number of “home” and “away” games)
§ Fairness (unfair for some teams to travel much larger
distances than other teams)
§ Economic (Ticket revenue might be higher on Friday
evening vs Tuesday evening)
§ Appeal (scheduling two strong teams late in the season
generates more excitement)
§ Since 2005, the Chilean soccer league has been constructing the schedule using integer linear programming
§ Ticket revenue increased from 6 million to 12 million pesos from 2004 to 2006, due to improved attendance
9
Example: Virginia Court of Appeals
§ Court systems need to assign judges to sessions
§ Virginia’s Court of Appeals constructed judge schedules for the year manually, taking into account
§ Timing and location of sessions
§ Availability of judges on certain days
§ Balancing judge workload
§ Each judge much sit with every other judge at least once
during the year
§ Etc.
§ Construction of schedule by hand took a single employee 150 hours over a few months
§ “Small” requested changes can ripple through the schedule
§ Starting in 2011, the Virginia Court of Appeals an integer linear programming approach for judge assignment, which could be solved in 1 day, saving an employee months of work
§ Using optimization also increases fairness of the judicial system by removing human discretion
10
Example: Real estate development
§ An LA-based real estate development firm is considering five different projects, one in each of the following locations: Santa Monica, Westwood, Venice, West Hollywood, and Marina Del Rey.
§ The following table describes the estimated profit and the investment required in each project (in millions):
§ The firm has raised $20 million of investment capital for these projects, and is now deciding which projects to invest in.
§ Formulate an integer program to maximize profit without exceed the $20 million budget.
11
Example: Real estate development
§ An optimal development plan is given by a solution to the following integer program:
max x1 + 1.8×2 + 1.6×3 + 0.8×4 + 1.4×5 s.t. 6×1 +12×2 +10×3 +4×4 +8×5 20
xi 2 {0,1}, i = 1,…,5.
Profit
Budget constraint
Force all variables to be 0 or 1
12
Solving integer programs
§ How do we solve integer programs? What if we brute force searched?
§ Consider the real estate development problem: One approach is to enumerate all solutions, eliminating
those that violate the budget constraint, and then compare the rest on profit. Is this a viable approach?
Suppose we had a super computer that could evaluate 1 million solutions per second.
# of projects
CPU time
20
1 second
25
1 minute
30
20 minutes
35
10 hours
40
2 weeks
45
1 year
50
35 years
55
1000 years
60
36000 years
There are 2n possible solutions! Enumeration is not feasible. Gurobi solves the n = 60 case in 1 second. How?
13
Geometry of IPs
§ Consider the following simple integer program: max 5×1 + 8×2
x1 ,x2
s.t. x1 + x2 6
5×1 + 9×2 45
x,x 2{0,1}. 1 2 integer
(Figure from Bradley, Hax, Magnanti)
14
The branch-and-bound algorithm
§ Branch-and-bound algorithm is the engine of IP solvers (e.g. Gurobi)
§ Main idea: Partition feasible region into sub-regions, and solve
optimization over each sub-region (”Divide and conquer”)
§ The LP relaxation of an integer program is the LP obtained when we drop the integrality constraints from the original IP
§ In a maximization (minimization) problem, the optimal value of the LP
relaxation is an upper (lower) bound on the IP optimal value
§ In our example problem, the optimal solution of LP relaxation is (x1,x2)=(2.25, 3.75),
with optimal value z = 41.25
§ Optimal value of integer solution must therefore be ≤ 41.25
15
The branch-and-bound algorithm
§ Because we want integer solutions, we can partition by focusing on two cases: x2 ≥ 4 and x2 ≤ 3. Let’s call these subregions L1 and L2
§ Let’s take region L1. Adding x2 ≥ 4 gives an LP relaxation solution of (x1,x2)=(1.8,4) with optimal value z = 41
§ Because x1 is not integer, we subdivide again, producing subregion L3 with x1 ≥ 2 and L4 withx1≤1
16
The branch-and-bound algorithm
§ Because we want integer solutions, we can partition by focusing on two cases: x2 ≥ 4 and x2 ≤ 3. Let’s call these subregions L1 and L2
§ Let’s take region L1. Adding x2 ≥ 4 gives an LP relaxation solution of (x1,x2)=(1.8,4) with optimal value z = 41
§ Because x1 is not integer, we subdivide
again, producing subregion L3 with x1 ≥ 2
and L4 withx1≤1
§ L3 is infeasible
§ L4 has solution (x1,x2)=(1,40/9)
§ Because x2 is not integer in the L4 solution, we
divide again into L5 with x1 ≤ 4 and L6 with x2 ≥ 5
17
The branch-and-bound algorithm
§ L5 gives solution (x1,x2)=(1,4), which is integer, with optimal value z = 37
§ Because L5 gave an integer solution, we don’t need to subdivide it further
§Wealsoknowthat 37≤z*≤41
§ (x1,x2)=(1,4) with z = 37 is the best integer solution so far — we now search over L2 and L6 in a similar manner to see if we can do better
18
The branch-and-bound algorithm
§ L6 gives solution (x1,x2)=(0,5) with optimal value z = 40
§ L2 gives solution (x1,x2)=(3,3) with optimal value z = 39
§ We have searched all the subregions, so the optimal solution of the IP is the best integer solution found so far, which is (x1,x2)=(0,5) with z* = 40
19
Tree representation
L0
x1= 2.25 x2 = 3.75 z = 41.25
Optimal solution found!
x2 ≥ 4
z* ≤ 41.25 x2 ≤ 3
L2
x1= 3 x2 = 3 z = 39
L1
x1= 1.8 x2 = 4
z = 41
LP bound: z* ≤ 410.255/9
Best integer solution found: Nz*/A≥ 3490
x1 ≥ 2
x1 ≤ 1
L4
x1= 1
x2 = 40/9
z = 40 !”
L3
Infeasible
x2 ≤ 4
x2 ≥ 5
L5
x1= 1 x2 = 4 z = 37
L6
x1= 0 x2 = 5 z = 40
z* ≥ 37
z* ≥ 40
20
Branch-and-bound summary
§ Main idea is to develop bounds z < z* < "̅ on z*
§ For maximization problem, lower bound z is best integer solution found
so far; upper bound "̅ is largest LP optimal value at any “hanging” box
§ After considering a subregion, we branch to split it into two more
subregions
§ Three rules for stopping branching on a sub-region:
1) LP over subregion Lj is infeasible,
2) LPsolutionoversubregionLjgivesoptimalvalueworsethanourbest
integer solution so far, or
3) LPsolutionoversubregionLjisinteger-valued.
When we stop branching, this is known as fathoming that part of the branch-and-bound tree
21
Optimality gap
§ The optimality gap associated with an integer solution is a measure of how far off we are from the true optimal value
x2 ≥ 4
z* ≤ 41.25 x2 ≤ 3
L0
x1= 2.25 x2 = 3.75 z = 41.25
L2
x1= 3 x2 = 3 z = 39
L1
x1= 1.8 x2 = 4
z = 41
§ Suppose we stopped the example problem after branching once and solving L1 and L2. The upper bound is 41.25, and the lower bound is 39 (because z = 39 corresponds to the best integer solution so far)
§ The optimality gap associated with the solution (x1,x2)=(3,3) is then Gap = "̅ #" = $%.'(#)* = 0.057 (or 5.7%)
§ For large problems where branch-and-bound takes hours to solve, we may prefer to terminate after reaching an optimality gap of 5%, 1%, or 0.1%, etc.
" )*
22
Tractability of integer programming
§ Integer programming solvers like Gurobi have improved dramatically in recent years, due to advances in optimization theory and algorithms
§ Estimated machine-independent speedup from 1991 to present (Gurobi 8.0) is a factor of 2 million
§ Taking hardware advancements into account, total speedup since 1991 is factor of around 500 billion
§ Despite computational complexity of integer programming, many models with millions of variables and constraints can now be solved on your laptop
§ A caveat: Solution time of IPs is not just a function of # of variables and constraints; some IPs are much harder than others, and may still not be solvable. In general, its hard to predict which IPs will solve fast or slow unless you try it
§ Let’s see the real estate investment example in Gurobi
23
Modeling logical conditions
§ A very useful feature of binary variables is the expression of logical conditions in the optimization model § Consider the real estate development example, where xi=1 if we select project i, and xi=0 if we don’t
§ Let’s look at some examples of logical conditions that frequently arise in integer programming
1. If project 1 is selected, project 5 cannot be selected:
x1 + x5 1 2. If project 2 is selected, then project 3 must be selected:
x2 x3
24
Modeling logical conditions
3. You must selected project 1 or 4, or both:
x1 + x4 1 4. Exactly 3 projects must be selected:
X5
xi = 3
i=1
25
Modeling logical conditions
§ Careful: These logical conditions are not always straightforward!
5. Project 3 can be selected only if both projects 1 and 2 are selected
1 + x3 x1 + x2 2x3 x1 + x2
Incorrect! Why?
§ We have so far looked at interactions between binary variables only; we can also use binary variables to model more complex interactions
Correct!
26
Non-exclusive OR constraints
§ Let xi, i =1,2,3,4 be continuous decision variables, and assume they are bounded, e.g., 0 ≤ xi ≤ 100 for i = 1,2,3,4
§ Suppose we want at least one of the following two constraints to hold 2x1 + x2 5
2x3 x4 2
§ We can do this by introducing a binary variable y1 and a large constant M:
2x1 + x2 5 My1
2x3 x4 2 + M(1 y1)
§ It is important that we pick M to be large enough so we don’t accidentally "cut off” other feasible solutions; in this example we can select M = 200 because we know 0 ≤ xi ≤ 100
27
Fixed costs
§ In many optimization problems, we would like to model “one-time” fixed costs
§ Example: Suppose we are deciding which, if any, of three different products to manufacture
and sell:
§ Products 1, 2 and 3 earn profit of $3, $4, and $7 per unit, respectively
§ Products 1, 2 and 3 have market demand of 30, 50 and 25 units, respectively (in thousands)
§ Due to labor constraints, we cannot produce more than 60 thousand units of all products
combined
§ Selling each product requires an initial investment for research and development and factory
equipment. The required investment to be able to make products 1, 2, and 3 are $15,000, $40,000 and $20,000, respectively.
§ Formulate an integer program to determine which products to invest in, and how much of each product to manufacture.
28
Fixed costs
§ Let xi denote the number of units of product i to manufacture
§ Let yi be an auxiliary variable to denote whether we choose to develop product i § Let M be a large constant
max 3x1 + 4x2 + 7x3 15, 000y1 40, 000y2 20, 000y3 Profit function x1 ,x2 ,x3
s.t. x1 30, 000 x2 50,000 x3 20,000
x1 + x2 + x3 60, 000 x1 My1
x2 My2
x3 My3
x1,x2,x3 0 y1,y2,y3 2{0,1}.
demand constraints labor constraint production decisions
§ Because the maximum demand for any product is 50,000, we can use M = 50,000
29
In-class assignment 1:
Hospital operating room scheduling
30