Understanding Linear Optimization in MS&E 214
Linear optimization involves maximizing or minimizing a linear function subject to constraints. This week's focus in MS&E 214 is on linear programming, basic feasible solutions, duality theory, and extreme point solutions. The concept of linear programs, such as the example of maximizing x + 3y subject to constraints, is discussed with feasible and optimum solutions. While simple cases can be reasoned out, larger problems are typically solved using automated LP solvers.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
MS&E 214 Week 1: Linear Programs Ashish Goel
Optimization Maximize/Minimize f(x), subject to some constraints Examples: Find the driving route from Sacramento to SFO that minimizes travel time; maximize airline revenue while making sure you do not lose valuable long-term customers; find the shape that maximizes the strength of a window arch; find the bag of stocks and bonds that give an expected 5% return while minimizing volatility
This week Primary focus: linear optimization review Formulation and solution of linear programs Basic Feasible Solutions Duality theory; Extreme point solutions
Linear Optimization The function that we are trying to maximize or minimize is a linear function, and the constraints are expressed as linear equalities (=) or inequalities ( or ). Such an optimization problem is called a Linear Program (LP) Example: Maximize x + 3y Subject to: x + y 2x + 3y x, y 2 5 0
Linear Optimization Example Maximize Subject to: x + 3y x + y 2x + 3y x, y 2 5 0 x, y : Decision variables x + 3y : Objective function x + y 2 : Constraint
Example Solution x = 0, y=1 satisfies all the constraints: Feasible Solution x = 1, y=1 also satisfies all the constraints: Another feasible solution The set of all feasible solutions is called the Feasible Set x = 0, y = 5/3 is a feasible solution which maximizes the objective function; hence this is an Optimum Solution At x = 0, y = 5/3, the value of the objective function is 5. We call this the Optimum Value
Finding an Optimum Solution In this case, it is easy to reason about this LP from first principles: 1. Since x, y 0, we know that x + 3y 2x + 3y 5. 2. Setting x = 0, y = 5/3 gives us a feasible solution and also achieves x + 3y = 5, hence it must be optimum. But imagine using this reasoning for LPs with 100,000 variables and 50,000 constraints In general, LPs are solved using automated LP solvers
Local vs Global Optimum Let us solve the problem Maximize 4x3/3 + x2(1-x2) without any constraints Bring out the elementary calculus: y = x2+ 4x3/3 x4; dy/dx = 0 when 1. x = 0, y = 0 2. x = 1.366, y = 1.783 [Local and Global Maximum] 3. x = -0.366, y= 0.051 [Local Maximum] dy/dx = 2x + 4x2- 4x3 [Local Minimum] BIG PROBLEM!
x = -0.366, y = 0.051 (Local Maximum) x = 1.366, y = 1.783 (Global Maximum) x = 0, y = 0 (Local Minimum)
Linear Programs: Some Facts A LP may have zero, one, or infinitely many feasible solutions A LP may have zero, one, or infinitely many optimum solutions The optimum and feasible solutions of an LP have several useful properties A local maximum for a LP is also a global maximum A local minimum for a LP is also a global minimum If we average two feasible solutions, we get another feasible solution If we average two optimum solutions, we get another optimum solution This mathematical structure allows us to solve Linear Programs efficiently, in contrast to general optimization problems or mathematical programs
Identifying Parts of a LP Maximize Subject to: 3x + 4y + 7z x + 5y 2 3z 5x + y 1 x 0
Identifying Parts of a LP Maximize Subject to: 3x + 4y + 7z Is x=0, y=0, z=0 a feasible solution? Yes No x + 5y 2 3z 5x + y 1 x 0
Identifying Parts of a LP Maximize Subject to: 3x + 4y + 7z Is x=0, y=1, z=1 a feasible solution? Yes No x + 5y 2 3z 5x + y 1 x 0
Identifying Parts of a LP Maximize Subject to: 3x + 4y + 7z How many feasible solutions does this LP have? x + 5y 2 3z 5x + y 1 x 0 Zero Two One Infinite
The Knapsack problem An illustrative example for Linear Programming Modeling Solving Analysis
The Knapsack problem A thief wants to rob a warehouse, but only has a small knapsack to carry her loot back. What should she carry? The warehouse has many goods, all divisible, so she can take 50% of a good (for example) and sell it for 50% of the total value. Examples: gold dust, diamonds, sugar, oil, cash The knapsack has a limited capacity for the amount of weight, but not for the amount of volume The thief wants to maximize her profit The thief asks you, the optimization expert, to help her figure out what goods to carry
Modeling: Step 1a Name the quantities that are given to you as part of the problem. i.e. the parameters W: The capacity of the knapsack N: The number of goods vi: The value of the i-th good wi: The weight of the i-th good
Modeling: Step 1b Name the quantities that you are free to choose, i.e., the decision variables xi: The fraction of the i-th good carried away by the thief
Modeling: Step 2a Define your goal; i.e. what is your objective in solving the problem First in English: Maximize the total value of the goods the thief can carry away Then in Math, to obtain your objective Function N i=1 Maximize vi xi
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 I N: xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 I N: xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 i N:xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 i N:xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 i N:xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Modeling: Step 2b Then, define the restrictions placed on you by the problem, i.e. the constraints You can not carry more of a good than you have available For all i, 1 i N: xi 1 You can not carry more total weight than the knapsack capacity wi xi W i=1 N You can not carry negative amounts of any good For all i, 1 i N: xi 0
Putting it all together The end result of modeling: A mathematical statement of the knapsack problem. N i=1 Maximize vi xi subject to: For all i, 1 i N:xi 1 N wi xi W i=1 For all i, 1 i N: xi 0
Putting it all together The end result of modeling: A mathematical statement of the knapsack problem. N i=1 Maximize vi xi subject to: (i):xi 1 " N wi xi W i=1 (i):xi 0 "
In Vector Notation w : N-dimensional column vector containing the N weights v = N-dimensional column vector containing the N values x = N-dimensional column vector containing the N decision variables Maximize vTx Subject to: wTx W x 1 x 0
Standard Forms We will often use the standard forms: Maximize cTx Subject to: OR Minimize bTy Subject to: (Packing LP) x: N x 1; A: M x N; c: N x 1; b: M x 1 N variables, M constraints Ax b x 0 (Covering LP) y: M x 1; A: M x N; c: N x 1; b: M x 1 M variables, N constraints ATy c y 0
An Instance An instance of a problem is where we actually give values to all the parameters. Example: Three goods: gold, diamond dust, and silver. Weights: (2, 3, 4) and Values: (5, 20, 3), respectively. Knapsack capacity: 4 Maximize 5x1 + 20x2 + 3x3 Subject to: 2x1 + 3x2 + 4x3 4 x1, x2, x3 0 x1 1 x2 1 x3 1
The Example Instance 2 3 4 5 x1 x2 x3 20 3 w = ; v = ; x = N = 3; W = 4
The Example Instance Maximize 5x1 + 20x2 + 3x3 Subject to: 2x1 + 3x2 + 4x3 4 x1, x2, x3 0 x1 1 x2 1 x3 1 1 Is x = a feasible solution? 1 1
The Example Instance Maximize 5x1 + 20x2 + 3x3 Subject to: 2x1 + 3x2 + 4x3 4 x1, x2, x3 0 x1 1 x2 1 x3 1 0 Is x = a feasible solution? 0 1
The Example Instance Maximize 5x1 + 20x2 + 3x3 Subject to: 2x1 + 3x2 + 4x3 4 x1, x2, x3 0 x1 1 x2 1 x3 1 0 0 Is x = a feasible solution? 0 1
The Example Instance Maximize 5x1 + 20x2 + 3x3 Subject to: 2x1 + 3x2 + 4x3 4 x1, x2, x3 0 x1 1 x2 1 x3 1 Is it possible for the optimum value to be 2?
One simple trick Minimize max {cTx, dTx} 0 Subject to: Ax b, x 0 Minimize z 0 Subject to: Ax b, x 0 z cTx z dTx Reduces to a Linear Program Works for Maximizing the min of linear functions, minimizing absolute value, etc. Does not work for maximizing max of linear functions. More on this later
