CSC373
Week 6: Linear Programming
Illustration Courtesy: Kevin Wayne & Denis Pankratov
373F20 – Nisarg Shah 1
Announcement
• ACM ICPC Qualification Round • Oct 24, 3-8pm EST
• Sign up at: https://www.teach.cs.toronto.edu/~acm/
• Top 9 participants will be chosen to represent U of T at the regional contest (broken into three teams of 3 each)
373F20 – Nisarg Shah 2
Recap
• Network flow
➢ Ford-Fulkerson algorithm
o Ways to make the running time polynomial
➢ Correctness using max-flow, min-cut ➢ Applications:
o Edge-disjoint paths
o Multiple sources/sinks
o Circulation
o Circulation with lower bounds o Survey design
o Image segmentation
o Profit maximization
373F20 – Nisarg Shah 3
Brewery Example
• A brewery can invest its inventory of corn, hops and malt into producing some amount of ale and some amount of beer
➢ Per unit resource requirement and profit of the two items are as given below
Example Courtesy: Kevin Wayne
373F20 – Nisarg Shah 4
Brewery Example
• Suppose it produces 𝐴 units of ale and 𝐵 units of beer
• Then we want to solve this program:
373F20 – Nisarg Shah 5
Linear Function
• 𝑓: R𝑛 → R is a linear function if 𝑓 𝑥 = 𝑎𝑇𝑥 for some 𝑎 ∈ R𝑛
3 𝑇 𝑥1 −5 𝑥2
• Linear constraints:
➢ 𝑔 𝑥 = 𝑐, where 𝑔: R𝑛 → R is a linear function and 𝑐 ∈ R
➢ Line in the plane (or a hyperplane in R𝑛) ➢ Example: 5𝑥1 + 7𝑥2 = 10
➢Example:𝑓𝑥1,𝑥2 =3𝑥1−5𝑥2= • Linear objective: 𝑓
373F20 – Nisarg Shah 6
Linear Function
• Geometrically, 𝑎 is the normal vector of the line(or hyperplane) represented by 𝑎𝑇𝑥 = 𝑐
373F20 – Nisarg Shah 7
Linear Inequality
• 𝑎𝑇𝑥 ≤ 𝑐 represents a “half-space”
373F20 – Nisarg Shah 8
Linear Programming
• Maximize/minimize a linear function subject to linear equality/inequality constraints
373F20 – Nisarg Shah 9
Geometrically…
373F20 – Nisarg Shah 10
Back to Brewery Example
373F20 – Nisarg Shah 11
Back to Brewery Example
373F20 – Nisarg Shah 12
Optimal Solution At A Vertex
• Claim: Regardless of the objective function, there must be a vertex that is an optimal solution
373F20 – Nisarg Shah 13
Convexity
• Convex set: 𝑆 is convex if 𝑥,𝑦∈𝑆,𝜆∈[0,1]⇒𝜆𝑥+ 1−𝜆 𝑦∈𝑆
• Vertex: A point which cannot be written as a strict convex combination of any two points in the set
• Observation: Feasible region of an LP is a convex set
373F20 – Nisarg Shah 14
Optimal Solution At A Vertex
• Intuitive proof of the claim:
➢ Start at some point 𝑥 in the feasible region ➢ If 𝑥 is not a vertex:
o Find a direction 𝑑 such that points within a positive distance of 𝜖 from 𝑥 in both 𝑑 and −𝑑 directions are within the feasible region
o Objective must not decrease in at least one of the two directions
o Follow that direction until you reach a new point 𝑥 for which at least one
more constraint is “tight”
➢ Repeat until we are at a vertex
373F20 – Nisarg Shah 15
LP, Standard Formulation • Input: 𝑐,𝑎1,𝑎2,…,𝑎𝑚 ∈ R𝑛,𝑏 ∈ R𝑚
➢ There are 𝑛 variables and 𝑚 constraints • Goal:
373F20 – Nisarg Shah 16
LP, Standard Matrix Form • Input: 𝑐,𝑎1,𝑎2,…,𝑎𝑚 ∈ R𝑛,𝑏 ∈ R𝑚
➢ There are 𝑛 variables and 𝑚 constraints • Goal:
373F20 – Nisarg Shah 17
Convert to Standard Form
• What if the LP is not in standard form? ➢ Constraints that use ≥
o𝑎𝑇𝑥≥𝑏 ⇔ −𝑎𝑇𝑥≤−𝑏
➢ Constraints that use equality
o𝑎𝑇𝑥=𝑏 ⇔ 𝑎𝑇𝑥≤𝑏, 𝑎𝑇𝑥≥𝑏
➢ Objective function is a minimization
o Minimize 𝑐𝑇𝑥 ⇔ Maximize −𝑐𝑇𝑥 ➢ Variable is unconstrained
o 𝑥 with no constraint ⇔ Replace 𝑥 by two variables 𝑥′and 𝑥′′, replace every occurrence of 𝑥 with 𝑥′ − 𝑥′′, and add constraints 𝑥′ ≥ 0, 𝑥′′ ≥ 0
373F20 – Nisarg Shah 18
LP Transformation Example
373F20 – Nisarg Shah 19
Optimal Solution
• Does an LP always have an optimal solution? • No! The LP can “fail” for two reasons:
1. Itisinfeasible,i.e. 𝑥 𝐴𝑥≤𝑏}=∅
o E.g. the set of constraints is 𝑥1 ≤ 1, −𝑥1≤ −2
2. It is unbounded, i.e. the objective function can be made arbitrarily large (for maximization) or small (for minimization)
o E.g. “maximize 𝑥1 subject to 𝑥1 ≥ 0”
• But if the LP has an optimal solution, we know that there must be a vertex which is optimal
373F20 – Nisarg Shah 20
Simplex Algorithm
• Simple algorithm, easy to specify geometrically • Worst-case running time is exponential
• Excellent performance in practice
373F20 – Nisarg Shah 21
Simplex: Geometric View
373F20 – Nisarg Shah 22
Algorithmic Implementation
Move to a neighbor vertex with better objective value
Start at a vertex of feasible polytope
Is there a neighbor vertex with better objective value?
Terminate, declare the current solution and value as optimal
373F20 – Nisarg Shah 23
How Do We Implement This?
• We’ll work with the slack form of LP
➢ Convenient for implementing simplex operations
➢ We want to maximize 𝑧 in the slack form, but for now, forget about the maximization objective
373F20 – Nisarg Shah 24
Slack Form
373F20 – Nisarg Shah 25
Slack Form
373F20 – Nisarg Shah 26
Simplex: Step 1
• Start at a feasible vertex
➢ How do we find a feasible vertex? ➢Fornow,assume𝑏≥0(each𝑏𝑖 ≥0)
o In this case, 𝑥 = 0 is a feasible vertex.
o In the slack form, this means setting the nonbasic variables to 0 ➢ We’ll later see what to do in the general case
373F20 – Nisarg Shah 27
Simple: Step 2
• What next? Let’s look at an example
• To increase the value of 𝑧:
➢ Find a nonbasic variable with a positive coefficient o This is called an entering variable
➢ See how much you can increase its value without violating any constraints
373F20 – Nisarg Shah 28
Simple: Step 2
This is because the current values of 𝑥2 and 𝑥3 are 0, and we need 𝑥4,𝑥5,𝑥6 ≥ 0
373F20 – Nisarg Shah 29
Simple: Step 2
➢ Solve the tightest obstacle for the nonbasic variable 𝑥1 = 9 − 𝑥2 − 𝑥3 − 𝑥6
Tightest obstacle
424
o Substitute the entering variable (called pivot) in other equations o Now 𝑥1 becomes basic and 𝑥6 becomes non-basic
o 𝑥6 is called the leaving variable
373F20 – Nisarg Shah 30
Simplex: Step 2
• After one iteration of this step:
➢ The basic feasible solution (i.e. substituting 0 for all nonbasic
variables) improves from 𝑧 = 0 to 𝑧 = 27 • Repeat!
373F20 – Nisarg Shah 31
Simplex: Step 2
373F20 – Nisarg Shah 32
Simplex: Step 2
373F20 – Nisarg Shah 33
Simplex: Step 2
• There is no leaving variable (nonbasic variable with positive coefficient).
• What now? Nothing! We are done.
• Take the basic feasible solution (𝑥3 = 𝑥5 = 𝑥6 = 0).
• Gives the optimal value 𝑧 = 28
• Intheoptimalsolution,𝑥1 =8,𝑥2 =4,𝑥3 =0
373F20 – Nisarg Shah 34
Simplex Overview
Move to a neighbor vertex with better objective value
Start at a vertex of feasible polytope
Is there a neighbor vertex with better objective value?
Terminate, declare the current solution and value as optimal
373F20 – Nisarg Shah 35
Simplex Overview
Move to a neighbor vertex with better objective value
Assuming 𝑏 ≥ 0, start with a basic feasible solution
Is there a neighbor vertex with better objective value?
Terminate, declare the current solution and value as optimal
373F20 – Nisarg Shah 36
Simplex Overview
Move to a neighbor vertex with better objective value
Assuming 𝑏 ≥ 0, start with a basic feasible solution
Is there an entering variable with positive coefficient?
Terminate, declare the current solution and value as optimal
373F20 – Nisarg Shah 37
Simplex Overview
Pivot on a leaving variable
Assuming 𝑏 ≥ 0, start with a basic feasible solution
Is there an entering variable with positive coefficient?
Terminate, declare the current solution and value as optimal
373F20 – Nisarg Shah 38
Simplex Overview
Pivot on a leaving variable
Assuming 𝑏 ≥ 0, start with a basic feasible solution
Is there an entering variable with positive coefficient?
Terminate, declare optimal value
373F20 – Nisarg Shah 39
Some Outstanding Issues
• What if the entering variable has no upper bound?
➢ If it doesn’t appear in any constraints, or only appears in constraints
where it can go to ∞
➢ Then 𝑧 can also go to ∞, so declare that LP is unbounded
• What if pivoting doesn’t change the constant in 𝑧?
➢ Known as degeneracy, and can lead to infinite loops
➢ Can be prevented by “perturbing” 𝑏 by a small random amount in each coordinate
➢ Or by carefully breaking ties among entering and leaving variables, e.g., by smallest index (known as Bland’s rule)
373F20 – Nisarg Shah 40
Some Outstanding Issues
• We assumed 𝑏 ≥ 0, and then started with the vertex 𝑥 = 0 • What if this assumption does not hold?
𝐿𝑃 1
Max𝑐𝑇𝑥 s.t. 𝑎𝑇𝑥 ≤ 𝑏
11
𝑎𝑇𝑥 ≤ 𝑏 22
⋮
𝑎𝑇 𝑥 ≤ 𝑏 𝑚𝑚
𝑥≥0
𝐿𝑃 2
Max𝑐𝑇𝑥 s.t.𝑎𝑇𝑥+𝑠 =𝑏
111
𝑎𝑇𝑥+𝑠 =𝑏 222
⋮
𝑎𝑇𝑥+𝑠 =𝑏 𝑚𝑚𝑚
𝑥, 𝑠 ≥ 0
𝐿𝑃 3
Max𝑐𝑇𝑥 s.t.𝑎𝑇𝑥+𝑠 =𝑏
111
−𝑎𝑇𝑥−𝑠 =−𝑏 222
⋮
−𝑎𝑇𝑥−𝑠 =−𝑏 𝑚𝑚𝑚
𝑥, 𝑠 ≥ 0
Multiply every constraint with negative 𝑏𝑖 by − 1 so RHS is now positive
373F20 – Nisarg Shah 41
Some Outstanding Issues
• We assumed 𝑏 ≥ 0, and then started with the vertex 𝑥 = 0
• What if this assumption does not hold?
𝐿𝑃 3
Max𝑐𝑇𝑥 s.t.𝑎𝑇𝑥+𝑠 =𝑏
111
−𝑎𝑇𝑥−𝑠 =−𝑏 222
⋮
−𝑎𝑇𝑥−𝑠 =−𝑏 𝑚𝑚𝑚
𝑥, 𝑠 ≥ 0
𝐿𝑃 4
Min σ𝑖 𝑧𝑖
s.t.𝑎𝑇𝑥+𝑠 +𝑧 =𝑏
1111
−𝑎𝑇𝑥−𝑠 +𝑧 =−𝑏 2222
⋮
−𝑎𝑇𝑥−𝑠 +𝑧 =−𝑏 𝑚𝑚𝑚𝑚
𝑥,𝑠,𝑧 ≥ 0
Remember: RHS is now positive
Remember: we only want to find a basic feasible solution to
𝐿𝑃 1
373F20 – Nisarg Shah 42
Some Outstanding Issues
• We assumed 𝑏 ≥ 0, and then started with the vertex 𝑥 = 0
• What if this assumption does not hold? What now?
Remember: the RHS is now positive
𝐿𝑃 4
Min σ𝑖 𝑧𝑖
s.t.𝑎𝑇𝑥+𝑠 +𝑧 =𝑏
1111
−𝑎𝑇𝑥−𝑠 +𝑧 =−𝑏 2222
⋮
−𝑎𝑇𝑥−𝑠 +𝑧 =−𝑏 𝑚𝑚𝑚𝑚
𝑥,𝑠,𝑧 ≥ 0
• •
•
Solve 𝐿𝑃 using simplex with 4
the initial basic solution being𝑥=𝑠=0,𝑧= 𝑏
If its optimum value is 0, extract a basic feasible solution 𝑥∗ from it, use it to solve𝐿𝑃 usingsimplex
If optimum value for 𝐿𝑃 is 4
greater than 0, then 𝐿𝑃 is 1
infeasible
1
373F20 – Nisarg Shah 43
Some Outstanding Issues
• We assumed 𝑏 ≥ 0, and then started with the vertex 𝑥 = 0
• What if this assumption does not hold?
• Solve 𝐿𝑃 using simplex with 𝐿𝑃 𝐿𝑃 2
12
the initial basic feasible
solution 𝑥 = 𝑠 = 0, 𝑧 = 𝑏
If its optimum value is 0,
extract a basic feasible
solution 𝑥∗ from it, use it to
solve𝐿𝑃 usingsimplex 1
• If optimum value for 𝐿𝑃 is 2
greater than 0, then 𝐿𝑃 is 1
infeasible
Max 𝑐𝑇𝑥 Min σ𝑖 𝑧𝑖 𝑇𝑇
1 1 • + 𝑧 = 𝑏
s.t.𝑎 𝑥≤𝑏 1 1
s.t.𝑎 𝑥+𝑠 +𝑧 =𝑏
𝑎𝑇𝑥 ≤ 𝑏 2 2
⋮
1 1
𝑎𝑇𝑥 + 𝑠 2 2
⋮
2 2
𝑎𝑇𝑥≤𝑏
𝑚𝑚 𝑚𝑚𝑚𝑚
𝑥 ≥ 0
𝑎𝑇𝑥+𝑠 +𝑧 =𝑏 𝑥, 𝑠 ≥ 0
373F20 – Nisarg Shah 44
Some Outstanding Issues
• Curious about pseudocode? Proof of correctness? Running time analysis?
• See textbook for details, but this is NOT in syllabus!
373F20 – Nisarg Shah 45
Running Time
• Notes
➢ Number of vertices of a polytope can be exponential in the number
of constraints
o There are examples where simplex takes exponential time if you choose your pivots arbitrarily
o No pivot rule known which guarantees polynomial running time ➢ There are other algorithms which run in polynomial time
o Ellipsoid method, interior point method, …
o Ellipsoid uses 𝑂(𝑚𝑛3𝐿) arithmetic operations, where 𝐿 = length of input o But no known strongly polynomial time algorithm
• Number of arithmetic operations = poly(m,n)
373F20 – Nisarg Shah 46
Certificate of Optimality
• Suppose you design a state-of-the-art LP solver that can solve very large problem instances
• You want to convince someone that you have this new technology without showing them the code
➢ Idea: They can give you very large LPs and you can quickly return the optimal solutions
➢ Question: But how would they know that your solutions are optimal, if they don’t have the technology to solve those LPs?
373F20 – Nisarg Shah 47
Certificate of Optimality
• Suppose I tell you that 𝑥1, 𝑥2 = (100,300) is optimal with objective value 1900
• How can you check this?
➢ Note: Can easily substitute (𝑥1, 𝑥2), and verify that it is feasible, and its objective value is indeed 1900
373F20 – Nisarg Shah 48
Certificate of Optimality
• Claim: 𝑥1, 𝑥2 = (100,300) is
optimal with objective value 1900
• Any solution that satisfies these inequalities also satisfies their positive combinations
➢ E.g. 2*first_constraint + 5*second_constraint + 3*third_constraint ➢ Try to take combinations which give you 𝑥1 + 6𝑥2 on LHS
373F20 – Nisarg Shah 49
Certificate of Optimality
• Claim: 𝑥1, 𝑥2 = (100,300) is
optimal with objective value 1900
• first_constraint + 6*second_constraint
➢𝑥1 +6𝑥2 ≤200+6∗300=2000
➢ This shows that no feasible solution can beat 2000
373F20 – Nisarg Shah 50
Certificate of Optimality
• Claim: 𝑥1, 𝑥2 = (100,300) is
optimal with objective value 1900
• 5*second_constraint + third_constraint ➢5𝑥2 + 𝑥1 +𝑥2 ≤5∗300+400=1900
➢ This shows that no feasible solution can beat 1900
o No need to proceed further
o We already know one solution that achieves 1900, so it must be optimal!
373F20 – Nisarg Shah 51
Is There a General Algorithm?
• Introduce variables 𝑦 , 𝑦 , 𝑦 by which we will be 123
multiplying the three constraints
➢ Note: These need not be integers. They can be reals.
• After multiplying and adding constraints, we get:
𝑦 +𝑦 𝑥 + 𝑦 +𝑦 𝑥 ≤200𝑦 +300𝑦 +400𝑦 131232123
373F20 – Nisarg Shah 52
Is There a General Algorithm?
➢ We have:
𝑦 +𝑦 𝑥 + 𝑦 +𝑦 𝑥 ≤200𝑦 +300𝑦 +400𝑦
131232123
➢ What do we want?
o 𝑦1, 𝑦2, 𝑦3 ≥ 0 because otherwise direction of inequality flips o LHS to look like objective 𝑥1 + 6𝑥2
• In fact, it is sufficient for LHS to be an upper bound on objective
• So we want 𝑦 + 𝑦 ≥ 1 and 𝑦 + 𝑦 ≥ 6 13 23
373F20 – Nisarg Shah 53
Is There a General Algorithm?
➢ We have:
𝑦 +𝑦 𝑥 + 𝑦 +𝑦 𝑥 ≤200𝑦 +300𝑦 +400𝑦
131232123
➢ What do we want? o𝑦1,𝑦2,𝑦3 ≥0
o 𝑦1 + 𝑦3 ≥ 1, 𝑦2 + 𝑦3 ≥ 6
o Subject to these, we want to minimize the upper bound 200𝑦1 + 300𝑦2 + 400𝑦3
373F20 – Nisarg Shah 54
Is There a General Algorithm?
➢ We have:
𝑦 +𝑦 𝑥 + 𝑦 +𝑦 𝑥 ≤200𝑦 +300𝑦 +400𝑦
131232123
➢ What do we want?
o This is just another LP!
o Called the dual
o Original LP is called the primal
373F20 – Nisarg Shah 55
Is There a General Algorithm?
➢ The problem of verifying optimality is another LP
o For any 𝑦1, 𝑦2, 𝑦3 that you can find, the objective value of the dual is an
upper bound on the objective value of the primal
o If you found a specific 𝑦1, 𝑦2, 𝑦3 for which this dual objective becomes equal to the primal objective for the (𝑥1, 𝑥2) given to you, then you would know that the given 𝑥1, 𝑥2 is optimal for primal (and your
(𝑦1, 𝑦2, 𝑦3) is optimal for dual)
373F20 – Nisarg Shah 56
Is There a General Algorithm?
➢ The problem of verifying optimality is another LP
o Issue 1: But…but…if I can’t solve large LPs, how will I solve the dual to
verify if optimality of (𝑥1, 𝑥2) given to me?
• You don’t. Ask the other party to give you both (𝑥1, 𝑥2) and the
corresponding 𝑦 , 𝑦 , 𝑦 for proof of optimality 123
o Issue 2: What if there are no (𝑦1, 𝑦2, 𝑦3) for which dual objective matches primal objective under optimal solution (𝑥1, 𝑥2)?
• As we will see, this can’t happen!
373F20 – Nisarg Shah 57
Is There a General Algorithm?
Primal LP
Dual LP
➢ General version, in our standard form for LPs
373F20 – Nisarg Shah 58
Is There a General Algorithm?
Primal LP
Dual LP
o 𝑐𝑇𝑥 for any feasible 𝑥 ≤ 𝑦𝑇𝑏 for any feasible 𝑦 o max 𝑐𝑇𝑥 ≤ min 𝑦𝑇𝑏
primal feasible 𝑥 dual feasible 𝑦
o If there is (𝑥∗, 𝑦∗) with 𝑐𝑇𝑥∗ = 𝑦∗ 𝑇𝑏, then both must be optimal
o In fact, for optimal 𝑥∗, 𝑦∗ , we claim that this must happen! • Does this remind you of something? Max-flow, min-cut…
373F20 – Nisarg Shah 59
Weak Duality
Primal LP
Dual LP
• From here on, assume primal LP is feasible and bounded • Weak duality theorem:
➢ For any primal feasible 𝑥 and dual feasible 𝑦, 𝑐𝑇𝑥 ≤ 𝑦𝑇𝑏
• Proof:
𝑐𝑇𝑥≤ 𝑦𝑇𝐴𝑥=𝑦𝑇 𝐴𝑥 ≤𝑦𝑇𝑏
373F20 – Nisarg Shah 60
Strong Duality
Primal LP
Dual LP
• Strong duality theorem:
➢ For any primal optimal 𝑥∗ and dual optimal 𝑦∗, 𝑐𝑇𝑥∗ = 𝑦∗ 𝑇𝑏
373F20 – Nisarg Shah 61
Strong Duality Proof
• Farkas’ lemma (one of many, many versions): ➢ Exactly one of the following holds:
1) There exists 𝑥 such that 𝐴𝑥 ≤ 𝑏
2) There exists 𝑦 such that 𝑦𝑇𝐴 = 0, 𝑦 ≥ 0, 𝑦𝑇𝑏 < 0
• Geometric intuition:
➢ Define image of 𝐴 = set of all possible values of 𝐴𝑥
This slide is not in the scope of the course
➢ It is known that this is a “linear subspace” (e.g. a line in a plane, a line or plane in 3D, etc)
373F20 - Nisarg Shah 62
Strong Duality Proof
This slide is not in the scope of the course
• Farkas’ lemma: Exactly one of the following holds:
1) There exists 𝑥 such that 𝐴𝑥 ≤ 𝑏
2) There exists 𝑦 such that 𝑦𝑇𝐴 = 0, 𝑦 ≥ 0, 𝑦𝑇𝑏 < 0
1) Image of 𝐴 contains a point “below” 𝑏 2) The region “below” 𝑏 doesn’t intersect image of 𝐴 this is witnessed by normal vector to the image of 𝐴
373F20 - Nisarg Shah 63
Strong Duality
Primal LP
This slide is not in the scope of the course
Dual LP
• Strong duality theorem:
➢ For any primal optimal 𝑥∗ and dual optimal 𝑦∗, 𝑐𝑇𝑥∗ = 𝑦∗ 𝑇𝑏 ➢ Proof (by contradiction):
o Let 𝑧∗ = 𝑐𝑇𝑥∗ be the optimal primal value.
o Suppose optimal dual objective value > 𝑧∗
o So there is no 𝑦 such that 𝑦𝑇𝐴 ≥ 𝑐𝑇 and 𝑦𝑇𝑏 ≤ 𝑧∗, i.e.,
373F20 – Nisarg Shah 64
Strong Duality ➢ There is no 𝑦 such that
➢ By Farkas’ lemma, there is 𝑥 and 𝜆 such that ➢ Case 1: 𝜆 > 0
This slide is not in the scope of the course
oNote:𝑐𝑇𝑥>𝜆𝑧∗ and𝐴𝑥=0=𝜆𝑏. oDividebothby𝜆toget𝐴 𝑥 =𝑏and𝑐𝑇 𝑥 >𝑧∗
𝜆𝜆 • Contradicts optimality of 𝑧∗
➢ Case 2: 𝜆 = 0
o We have 𝐴𝑥 = 0 and 𝑐𝑇𝑥 > 0
o Adding 𝑥 to optimal 𝑥∗ of primal improves objective value beyond 𝑧∗ ⇒ contradiction
373F20 – Nisarg Shah 65
Exercise: Formulating LPs
• A canning company operates two canning plants (A and B).
• Three suppliers of fresh fruits:
• Shipping costs in $/tonne:
• Plant capacities and labour costs:
• Selling price: $50/tonne, no limit
• Objective: Find which plant should get how much supply from each grower to maximize profit
373F20 – Nisarg Shah 66
Exercise: Formulating LPs
• Similarly to the brewery example from the beginning:
➢ A brewery can invest its inventory of corn, hops and malt into
producing three types of beer
➢ Per unit resource requirement and profit are as given below
➢ The brewery cannot produce positive amounts of both A and B
➢ Goal: maximize profit
Beverage
Corn (kg)
Hops (kg)
Malt (kg)
Profit ($)
A
5
4
35
13
B
15
4
20
23
C
10
7
25
15
Limit
500
300
1000
373F20 – Nisarg Shah 68
Exercise: Formulating LPs
• Similarly to the brewery example from the beginning:
➢ A brewery can invest its inventory of corn, hops and malt into
producing three types of beer
➢ Per unit resource requirement and profit are as given below
➢ The brewery can only produce 𝐶 in integral quantities up to 100
➢ Goal: maximize profit
Beverage
Corn (kg)
Hops (kg)
Malt (kg)
Profit ($)
A
5
4
35
13
B
15
4
20
23
C
10
7
25
15
Limit
500
300
1000
373F20 – Nisarg Shah 69
Exercise: Formulating LPs
• Similarly to the brewery example from the beginning: ➢ A brewery can invest its inventory of corn, hops and malt into
producing three types of beer
➢ Per unit resource requirement and profit are as given below
➢ Goal: maximize profit, but if there are multiple profit-maximizing solutions, then…
o Break ties to choose those with the largest quantity of 𝐴
o Break any further ties to choose those with the largest quantity of 𝐵
Beverage
Corn (kg)
Hops (kg)
Malt (kg)
Profit ($)
A
5
4
35
13
B
15
4
20
23
C
10
7
25
15
Limit
500
300
1000
373F20 – Nisarg Shah 70
More Tricks
• Constraint: 𝑥 ≤ 3
➢ Replace with constraints 𝑥 ≤ 3 and −𝑥 ≤ 3 ➢ What if the constraint is 𝑥 ≥ 3?
• Objective: minimize 3 𝑥 + 𝑦 ➢ Add a variable 𝑡
➢ Add the constraints 𝑡 ≥ 𝑥 and 𝑡 ≥ −𝑥 (so 𝑡 ≥ |𝑥|) ➢ Change the objective to minimize 3𝑡 + 𝑦
➢ What if the objective is to maximize 3 𝑥 + 𝑦?
• Objective: minimize max(3𝑥 + 𝑦, 𝑥 + 2𝑦)
➢ Hint: minimizing 3 𝑥 + 𝑦 in the earlier bullet was equivalent to
minimizing max(3𝑥 + 𝑦, −3𝑥 + 𝑦) •…
373F20 – Nisarg Shah 71
373F20 – Nisarg Shah 72