MSBA 403:
Optimization
Lecture 1
November 6, 2020
Optimization and decision-making
§ We live in a world that is resource-constrained: § Money
§ Time
§ Labor
§ Physical space
§ Optimization is fundamentally about making decisions that lead to favorable outcomes in the face of constraints
§ Building optimization models is both an art and science
§ Science because we rely on math and algorithms
§ Art because we often want to translate real-world problems into a model. The best way to do this is not always obvious!
2
Example: Pricing and revenue management
How should Expedia set prices and manage capacity to maximize revenue?
3
Example: GPS routing
What is the optimal route to get home the fastest?
(My drive home)
4
Example: Portfolio optimization
Which financial assets should we invest in to maximize returns?
5
Example: Radiation therapy
How can we maximize radiation to a tumor while minimizing damage to surrounding tissues?
6
Example: Ride-hailing matching
How should Uber match riders and drivers to minimize wait times?
7
Course objectives
§ Understand the fundamentals of optimization
§ Express various optimization problems as mathematical models
§ Implement and solve optimization models computationally
§ Gain an appreciation for the value of optimization modeling in practice
8
Syllabus
9
Models vs reality
“All models are wrong, but some are useful.”
George Box
§ Mathematical models are just an approximation of reality
§ Goal is to capture the most important features of the problem
10
Model structure: Decision variables
§ Decision variables are denoted by letters, for example: x1,x2,…,xn
§ Decision variables are at the heart of optimization § What prices should we set to maximize profit?
§ Which streets should we take?
§ How much should we invest in each stock?
§ How much radiation should be delivered from each beam? § Which rider should be matched to which Uber driver?
§ The value of these variables are to be set by the decision-maker § Often interpretable, but not always the case
11
Model structure: Constraints
§ Constraints are denoted by functions of decision variables: f1(x1,x2,…,xn) 0
§ Can have sign ≤, ≥ or =
f2(x1,x2,…,xn) 0 .
fm(x1,x2,…,xn) 0
§ Constraints capture limitations on functions of the decision variables, e.g. § Prices cannot be negative
§ Geographic constraints in GPS routing
§ Maximum acceptable risk or variance in portfolio
§ Maximum acceptable dose to healthy organs
§ Maximum time or distance constraints in ride-hailing matching
12
Model structure: Objective function
§ The objective is a function we would like to either maximize or minimize: max f0(x1,x2,…,xn)
or
min f0(x1,x2,…,xn)
§ The objective function is the quantity that we are trying to optimize, e.g. § Revenue from bookings
§ Total travel time by car
§ Return on investment
§ Radiation dosage to tumor
§ Total ride-hailing passenger wait time
13
Model structure: Summary
§ The general form of an optimization model is given by
max f0(x1,x2,…,xn)
s.t. f1(x1,x2,…,xn) 0 f2(x1,x2,…,xn) 0
.
fm(x1,x2,…,xn) 0
§ Optimization problems written in this form are often called mathematical programs
§ Development of algorithms to solve mathematical programs is a significant area of research
(although we won’t focus on algorithms too much in this course)
§ The format above is very general: We will first focus on an important class known as linear programming
14
Linear programming (LP)
§ A linear program is an optimization model in which the objective function f0 and constraints f1, f2, …, fm are all linear functions of the decision variables x1, x2, …,
xn
§ Sounds restrictive, but this is an extremely useful class of models
§ In practice, LPs can be solved very efficiently for thousands (or sometimes millions) of decision variables, which makes them a powerful optimization framework
§ We will focus on LPs for the remainder of this class
15
Example: Bag production
§ Consider a company that produces UCLA-branded bags to be sold in the UCLA Store.
§ Two types of bags can be made: Standard and Deluxe
§ Each standard bag sold generates a profit of $10; each Deluxe bag sold generates a
profit of $9
§ Due to machine and labor restrictions, the company has 630 hours of cutting, 600 hours of sewing, 708 hours of finishing, and 135 hours of inspecting
§ Each Standard bag requires 7/10 hours of cutting, 1⁄2 hours of sewing, 1 hour of finishing, and 1/10 hour of inspecting
§ Each Deluxe bag requires 1 hour of cutting, 5/6 hours of sewing, 2/3 hours of finishing, and 1/4 hours of inspecting
§ How many of each bag should be produced to maximize profit?
16
17
Example: Bag production
§ Let xS and xD be the decision variables for the number of standard and deluxe bags to produce, respectively
§ The bag production problem can be formulated as the following linear program:
hours of cutting used hours of sewing used
max
xS ,xD s.t.
10xS + 9xD
7 xS + xD 630
1xS + 5xD 600 26
xS + 2 xD 708 3
1 xS + 1 xD 135 10 4
xS,xD 0.
profit function
hours of cutting available
hours of sewing available hours of finishing time available
hours of inspection time available non-negativityconstraints
10
hours of finishing used hours of inspection used
18
Example: Cargo revenue management
You are the manager of a cargo plane that ships goods overseas. You are deciding how much cargo to accept for an upcoming flight. The cargo plane has three compartments: front, center and back. Each of these compartments have capacities on both weight and volume:
To ensure that the weight distribution on the plane remains balanced, the ratio of cargo weights in the respective compartments must be equal to the ratio of weight capacities. The following four cargoes have been offered for shipment for the flight:
Any portion of each cargo can be accepted. Your decision problem is to determine how much of each cargo to accept, and how to distribute them among the compartments of the plane to maximize profit. Formulate a linear program for this problem.
19
20
21
Example: Cargo revenue management
Decisionvariables:Letxij betheamountofcargoiacceptedintocompartmentj,wherej=1isthefrontcompartment,j=2is the center, and j = 3 is the back
Objective function:
maximize 320(x11 + x12 + x13) + 400(x21 + x22 + x23) + 360(x31 + x32 + x33) + 290(x41 + x42 + x43) subject to x11 + x21 + x31 + x41 12
ectto x +x +xx++xx+x12+x 10 11 21 1331 2341 33 43
41
Weight capacity constraints:
imize 320(x +x +x )+x400+(xx +x18+x )+360(x +x +x )+290(x +x +x ) 11 12 1232 32 2412 22 23 31 32 33 41 42 43
imize 320(x11 + x12 + x13) + 400(x21 + x22 + x23) + 360(x31 + x32 + x33) + 290(x41 + x42 + x43)
x + x +50x0x ++x 700x18 + 600x 12 22 3211 42 21 31
+ 400x
7000 9000 5000
ectto x11+x21+x31+x41 12
x + x +50x0x ++x 700x10 + 600x
+ 400x 500x + 75000xx ++67000xx ++46000xx +74000x
13 23 3312 43 22 32
42 11 213 3213 4313 43
x12 +x22 +x32 +x42 18 Voxlum+e cxapac+ityxcon+strxaints: 10
13 23 33 43
500x + 7x00x+ x+ 60+0x + 4200x 9000 121122123123 42
500×11 + 700×21 + 600×31 + 400×41 7000 500x + 7x00x+ x+ 60+0x + 41060x 5000
13212322323 43
500×12 + 700×22 + 600×32 + 400×42 9000
x +x +xx+x20+x 25 11 12 3113 32 33
500×13 + 700×23 + 600×33 + 400×43 5000 x +x +xx+x16+x 13
21 22 4123 42 43 x11 +x12 +x13 20
x +x +18x(x+25x +x +x )=12(x +x +x +x ) 31 32 3311 21 31 41 12 22 32 42
x21 +x22 +x23 16
x +x +10x(x+13x +x +x )=12(x +x +x +x )
x41+x42+x4311 2521 31 41 13 23 33 43 31 32 33
22
x
j x
j
18(x +xx+ x0,+i=x1,)2=,3,142,(xj=+1,×2,3+.x +x ) 11 21ij 31 41 12 22 32 42
x +x +x +x 18 ttox +x +x +x 12
m t
12 22 32 42
11 21 31 41
x +x +x +x 10 x13+x23+x33+x43 18
Example: Cargo revenue management
12 22 32 42
ize 320(x11 +x12 +x13)+400(x21 +x22 +x23)+360(x31 +x32 +x33)+290(x41 +x42 +x43)
500x + 700x + 600x + 400x 7000 11 21 31 41
x +x +x +x 10 to x13+x23+x33+x4312
11 21 31 41
500x + 700x + 600x + 400x 9000 12 22 32 42
500x + 700x + 600x + 400x 7000 11 21 31 41
x12 +x22 +x32 +x42 18 M5a0x0imxum+av7a0ila0bxle c+arg6o0:0x + 400x 5000
13 23 33 43
500×12 + 700×22 + 600×32 + 400×42 9000
x13 +x23 +x33 +x43 10 x11 +x12 +x13 20
500×13 + 700×23 + 600×33 + 400×43 5000 500×11 + 700×21 + 600×31 + 400×41 7000
x21 +x22 +x23 16
x +x +x 20 11 12 13
500x + 700x + 600x + 400x 9000 12 22 32 42
x +x +x 25
x31+x32+x33 16 21 22 23
5000 x10(+xx+x+x+x1+6x )=12(x +x +x +x )
500x + 700x + 600x x +13x +x2313 33
+ 400x
181(x11 1+2 x21 +13×31 + x41) = 12(x12 + x22 + x32 + x42)
x41+x42+x43 25 x31 + x32 + x33 20
43
x +x +x 13 B4a1lance c4o2nstrai4n3ts:
21 1122 2123 31 41 13 23 33 43
18(x +x +x +x)=12(x +x +x +x) ij11 21 31 41 12 22 32 42
xx + x0,i+=x1,2,3,245,j=1,2,3. 31 32 33
10(x +x +x +x)=12(x +x +x +x) 41 1142 2143 31 41 13 23 33 43
x +x +x 13
x 0, i=1,2,3,4, j =1,2,3.
1N0o(nx-nega+tivxity c+onsxtrain+tsx: ) = 12(x 11 21 31 41
xij 0, i = 1, 2, 3, 4, j = 1, 2, 3.
18(x +x +x +x)=12(x +x +x +x)
ij
11 21 31 41
12 22 32 42
+ x + x + x ) 13 23 33 43
23
Solving linear programs
§ How do we solve a linear program?
§ Let’s focus on the bag production problem again
max 10xS+9xD xS ,xD
s.t. 7xS+xD630 10
1xS + 5xD 600 26
xS + 2xD 708 3
1 xS + 1xD 135 10 4
xS,xD 0.
24
Feasible solutions and optimal solutions
§ A feasible solution to a linear program is a set of values for the decision variables
that does not violate any constraints
§ E.g. (xS,xD) = (100, 200) is feasible, because it satisfies all constraints
§ E.g. (xS,xD) = (50, 550) is infeasible, because it violates the inspection time constraint
§ An optimal solution is a feasible solution that produces at least as good of an objective function value as every other possible feasible solution
§ We will refer to the best possible objective function value as the optimal value
§ There can be more than one optimal solution! In other words, two different solutions can attain the optimal value
25
Graphical representation
§ Because we have two decision variables in the bag production problem, we can represent the feasible solution of this LP graphically
xD
1200 1000 800 600 400 200 0
Cutting constraint
feasible
infeasible
0 500 1000 1500
xS
26
7 xS + xD = 630 10
Graphical representation
§ Because we have two decision variables in the bag production problem, we can represent the feasible solution of this LP graphically
xD
1200 1000 800 600 400 200 0
Sewing constraint
0 500
1000
1500
feasible
xS
infeasible
27
1xS + 5xD = 600 26
Graphical representation
§ Because we have two decision variables in the bag production problem, we can represent the feasible solution of this LP graphically
xD
1200 1000 800 600 400 200 0
Finishing constraint
0
500 1000 1500
feasible
xS
infeasible
28
xS + 2xD = 708 3
Graphical representation
§ Because we have two decision variables in the bag production problem, we can represent the feasible solution of this LP graphically
xD
1200 1000 800 600 400 200 0
Inspecting constraint
feasible
infeasible
1000 1500
xS
0 500
29
1 xS + 1xD = 135 10 4
Graphical representation
§ Because we have two decision variables in the bag production problem, we can represent the feasible solution of this LP graphically
xD
1200 1000 800 600 400 200 0
All constraints
0 500
Sewing constraint is redundant
xS
1000 1500
30
Graphical representation
§ The feasible region is the set of all feasible solutions xD
1200 1000 800 600 400 200 0
0
Feasible region
500
1000 1500
xS
31
1200
Visualizing the objective function
1000
§ What is the objective function value (i.e. profit) associated with each solution?
§ We can visualize the objective by using profit line: every point along this line yields
the same profit800 xD
600 400 200
0
0 500
xS
1000
32
10xS + 9xD = 1800
1200
Visualizing the objective function
1000
§ Shifting the profit line yields a higher profit 800 xD
600 400 200
0
0 500
xS
1000
33
10xS + 9xD = 5400
10xS + 9xD = 3600
1200
Visualizing the objective function
1000
800 xD
§ Optimal solution is attained at an extreme point of the feasible region
§ Optimal solution is to make 540 Standard bags and 252 Deluxe bags, which gives profit of $7668
§ Is an optimal solution to a linear program always attained at an extreme point of the feasible region? Yes!
600 400 200
0
0 500
Optimal solution: (xS*, xD*) = (540, 252)
xS
1000
34
10xS + 9xD = 7668
Solving linear programs
1200
1000
§ Property of LP that a solution is always obtained at an extreme point is useful – we only need to search extreme points to find an optimal solution
§ Note that each extreme point is a solution to a set of linear equations 800 xD
Solution to:
1 xS + 1xD = 135 10 4
xS = 0
xS
1000
35
600 400 200
0
0 500
1
Solving linear programs
1200
1000
§ Property of LP that a solution is always obtained at an extreme point is useful – we only need to search extreme points to find an optimal solution
§ Note that each extreme point is a solution to a set of linear equations 800 xD
Solution to:
7 xS + xD = 630 10
1 xS + 1xD = 135 10 4
xS
1000
36
600 400 200
0
0 500
1
Solving linear programs
1200
1000
§ Property of LP that a solution is always obtained at an extreme point is useful – we only need to search extreme points to find an optimal solution
§ Note that each extreme point is a solution to a set of linear equations 800 xD
Solution to:
xS + 2xD = 708 3
7 xS + xD = 630 10
xS
1000
37
600 400 200
0
0 500
1
Solving linear programs
1200
1000
§ Property of LP that a solution is always obtained at an extreme point is useful – we only need to search extreme points to find an optimal solution
§ Note that each extreme point is a solution to a set of linear equations 800 xD
Solution to:
xD = 0
xS + 2xD = 708
3
xS
1000
38
600 400 200
0_ 0 500
1
Solving linear programs
1200
1000
§ Property of LP that a solution is always obtained at an extreme point is useful – we only need to search extreme points to find an optimal solution
§ Note that each extreme point is a solution to a set of linear equations 800 xD
Solution to:
xD = 0 xS = 0
xS
1000
39
600 400 200
_
0
0 500
1
Solving linear programs
§ What if we just solved for every possible extreme point? How many are there?
§ An upper bound on the number of extreme points of the feasible region is the number of intersections
between constraint lines
§ Because we have 6 constraints (including non-negativity) and 2 variables, there are a total of
1200
1000
800
600
400
200
✓6◆ = 6!
2 2!(6 2)!
intersection points.
= 15
§ In general, with m constraints and n
variables, the number of intersection points
is combinatorial: ✓m◆
n
0
m! 0 500
Enumerating all possible n!(m n)! solutions is not practical!
1000 1500
=
40
The Simplex Method
1200
§ LPs can be solved using an extremely efficient algorithm known as the simplex method (also
known as “simplex algorithm”)
§ The simplex algorithm is the reason why we can solve large scale linear programs with
thousands or millions of variables
1000 800 xD
600 400 200
0
0 500
(Rough) Simplex Method Steps
1. Start at an extreme point.
2. Check to see if objective function can be improved
by moving to an adjacent extreme point.
3. If objective can be improved, move to adjacent
extreme point, and go back to step 2.
4. If objective cannot be improved, current extreme
point is optimal.
Adjacent extreme points: All but one constraint in common.
An edge of the feasible region connects adjacent extreme points.
xS
100
41
0
The Simplex Method
The simplex method moves from one extreme point to another, by traversing edges of the feasible region, until an optimal solution is found.
42
Linear programs: General notation
§ For larger problems, it may not be realistic to write out all of the variables and constraints explicitly
§ We can write linear programs in a concise way by using set and index notation
43
Example: Product delivery
Consider a company that wishes to delivery a product to a set of customers in different locations in the most cost- efficient way possible.
• The available supply of the product is si at warehouses i = 1,2,…,m.
• The company must satisfy demand dj at locations j = 1,2,…,n.
• The cost of delivering the product warehouse i to location j is given by cij.
Formulate a linear program that provides a cost- minimizing delivery plan.
44
Example: Product delivery
The linear program for the product delivery problem is given by:
min
x
s.t.
X X cij xij i=1 j=1
Minimize total delivery cost
mn
m i=1
Xn
xij dj, xij si,
j = 1,2,…,n, i=1,2,…,m,
Total delivery to each location must satisfy demand
Eachwarehousecannotdelivermorethan available supply
Non-negativity constraints
j=1
xij 0, i = 1,2,…,m, j = 1,2,…,n.
45
Solving LPs with Python and Gurobi
§ We will use Python to implement and solve optimization models in this class
§ In particular, we will use optimization solver called Gurobi, which implements various solution algorithms (including the Simplex Method)
§ Let’s look at a couple of examples
46
Python and Gurobi installation
1. Install Python 3.8 using the Anaconda distribution.
https://www.anaconda.com/distribution/
2. Request a free academic license for Gurobi using your UCLA email address. Follow the steps in the page below to retrieve and install your license key. https://www.gurobi.com/academia/academic-program-and-licenses/
3. Install Gurobi. To do this, open terminal (Mac) or cmd (Windows) and type
conda config –add channels http://conda.anaconda.org/gurobi conda install gurobi
4. We will use a user-friendly interface for Python called Jupyter Notebook. To launch Jupyter Notebook, open terminal or cmd and type
jupyter notebook
This will launch Jupyter Notebook in your browser. We can now open and run Jupyter Notebook files (extension .ipynb) from within the browser.
Do this before lecture 2!
47