CS代写 Lecture 14: Primal and Dual Methods

Lecture 14: Primal and Dual Methods
For Large Optimization Problems
ISyE 6673: Financial Optimization

Stewart School of Industrial and Systems Engineering Georgia Institute of Technology
October 19, 2022

Size of a linear program
Duality & SA
• How should we think about the size of a linear program? • Two numbers:
Problem dimension n: number of decision variables
Number of constraints m: this is actually the dimension of the dual problem!
• Both numbers affect tractability
Number of extreme points scales like 􏰀m􏰁 ∼ mm−n in the worst
The constraint matrix A is m × n. If m and n are both 100,000, the matrix might have 10 billion entries, which may not fit in memory!
Dr. ISyE 6673: Financial Optimization October 19, 2022 2 31

Duality & SA
Solving large-scale optimization problems
Today’s objective
How to solve very large linear programs efficiently!
• Too many variables: column generation • Too many constraints: cutting planes
Dr. ISyE 6673: Financial Optimization October 19, 2022 3 31

Duality & SA Column generation
Column generation
Dr. ISyE 6673: Financial Optimization October 19, 2022 4 31

The cutting stock problem
• A classic optimization problem
• You are a paper company, and you
produce rolls of paper, each of width W
• Note that it’s called “width” but when the roll is fully rolled up it’s probably the longest dimension.
• Your m customers don’t want rolls of width W . In fact, each customer i wants bi rolls of width wi
Duality & SA Column generation
Dr. ISyE 6673: Financial Optimization October 19, 2022 5 31

Duality & SA Column generation
The cutting stock problem
• A classic optimization problem
• You are a paper company, and you
produce rolls of paper, each of width W
• Note that it’s called “width” but when the roll is fully rolled up it’s probably the longest dimension.
• Your m customers don’t want rolls of width W . In fact, each customer i wants bi rolls of width wi
How do we meet customer demand?
We have to figure out how to cut the rolls!
Dr. ISyE 6673: Financial Optimization October 19, 2022 5 31

Duality & SA Column generation
• Let’s say W = 10
Dr. ISyE 6673: Financial Optimization October 19, 2022 6 31

Duality & SA Column generation
• Let’s say W = 10
• m=1,b1 =6,w1 =5: wecancutthreerollsofwidth10into two rolls of width 5 each, for a total of 6 rolls of width 5
Dr. ISyE 6673: Financial Optimization October 19, 2022 6 31

Duality & SA Column generation
• Let’s say W = 10
• m=1,b1 =6,w1 =5: wecancutthreerollsofwidth10into
two rolls of width 5 each, for a total of 6 rolls of width 5
• m=1,b1 =6,w1 =9: wecancutsixrollsofwidth10,each into one roll of width 9 and one roll of width 1. We end up with six rolls of width 9 to satisfy the customer, and six rolls of width 1 are wasted
Dr. ISyE 6673: Financial Optimization October 19, 2022 6 31

Duality & SA Column generation
• Let’s say W = 10
• m=1,b1 =6,w1 =5: wecancutthreerollsofwidth10into
two rolls of width 5 each, for a total of 6 rolls of width 5
• m=1,b1 =6,w1 =9: wecancutsixrollsofwidth10,each into one roll of width 9 and one roll of width 1. We end up with six rolls of width 9 to satisfy the customer, and six rolls of width 1 are wasted
• What about when n > 1? We need linear programming!
Dr. ISyE 6673: Financial Optimization October 19, 2022 6 31

Duality & SA Column generation
Formulating the cutting stock problem
Question: How many ways are there to cut a stock of width W? Answer: A LOT!
Dr. ISyE 6673: Financial Optimization October 19, 2022 7 31

Duality & SA Column generation
Formulating the cutting stock problem
Question: How many ways are there to cut a stock of width W? Answer: A LOT!
Assume only want integer widths, a roll of width 4 can be cut into: • 4 rolls of width 1
• 2 rolls of width 2
• 2rollsofwidth1,1rollofwidth2
• 1rollofwidth3and1rollofwidth1
• Number of possible “cutting patterns” is exponential in W!
• Even though we only care about widths wi that are actually requested by consumers, the number of possible cutting patterns could still be really large!
Dr. ISyE 6673: Financial Optimization October 19, 2022 7 31

Duality & SA Column generation
Representing cutting patterns as vectors
• We can write pattern j as a column vector Aj of height m
Aj = (a1j,…,amj)
aij is the number of rolls of width wi produced by this pattern
• ArollofwidthW =70canbecutinto3rollsofwidthw1 =15 and 1 roll of width w2 = 17 (wasting a roll of width 8)
We can write this pattern as (3, 1)
• Alternatively the same roll can be cut into 1 roll of width
w1 =15and3rollsofwidthw2 =17(wastingarollofwidth4)
We can write this pattern as (1, 3)
Dr. ISyE 6673: Financial Optimization October 19, 2022 8 31

Duality & SA Column generation
Characterizing a feasible pattern
• A pattern represented by vector Aj is feasible if the sum of the widths don’t exceed the width of the roll
􏰃aijwi ≤W i=1
• The “waste” rj of a pattern is any remaining roll with a width that is not one of the approved customer widths wi
rj =W−􏰃aijwi ≥0
Dr. ISyE 6673: Financial Optimization October 19, 2022 9 31

Duality & SA Column generation
Formulating the cutting stock problem
• Let J designate the number of possible feasible patterns
Dr. ISyE 6673: Financial Optimization October 19, 2022 10 31

Duality & SA Column generation
Formulating the cutting stock problem
• Let J designate the number of possible feasible patterns
• Decision variable xj is the number of rolls cut with pattern j (integer, but continuous is ok for large demand)
Dr. ISyE 6673: Financial Optimization October 19, 2022 10 31

Duality & SA Column generation
Formulating the cutting stock problem
• Let J designate the number of possible feasible patterns
• Decision variable xj is the number of rolls cut with pattern j
(integer, but continuous is ok for large demand)
• We can formulate the cutting stock problem as follows:
s.t. 􏰃aijxj≥wi j=1
∀1≤i≤m ∀ j ∈ J
Dr. ISyE 6673: Financial Optimization October 19, 2022 10 31

Duality & SA Column generation
Formulating the cutting stock problem
s.t. 􏰃aijxj≥bi ∀1≤i≤m j=1
xj ≥0 ∀j∈J
• Constraints seek to meet the demand of each customer i
Dr. ISyE 6673: Financial Optimization October 19, 2022 11 31

Duality & SA Column generation
Formulating the cutting stock problem
s.t. 􏰃aijxj≥bi ∀1≤i≤m j=1
xj ≥0 ∀j∈J
• Constraints seek to meet the demand of each customer i • Objective is to minimize the total number of rolls
Dr. ISyE 6673: Financial Optimization October 19, 2022 11 31

Duality & SA Column generation
Formulating the cutting stock problem
s.t. 􏰃aijxj≥bi ∀1≤i≤m j=1
xj ≥0 ∀j∈J
• Constraints seek to meet the demand of each customer i • Objective is to minimize the total number of rolls
• Alternatively we can minimize total waste:
J min􏰃rjxj j=1
Dr. ISyE 6673: Financial Optimization October 19, 2022 11 31

Duality & SA Column generation
Formulation size
• We can write the formulation in partial vector form as
s.t. 􏰃Ajxj≥b j=1
Dr. ISyE 6673: Financial Optimization October 19, 2022 12 31

Duality & SA Column generation
Formulation size
• We can write the formulation in partial vector form as
s.t. 􏰃Ajxj≥b j=1
• Notice that the number of variables is huge!
Dr. ISyE 6673: Financial Optimization October 19, 2022 12 31

Duality & SA Column generation
Formulation size
• We can write the formulation in partial vector form as
s.t. 􏰃Ajxj≥b j=1
• Notice that the number of variables is huge!
• Another way to say it is that the matrix A has too many columns!
• An optimal BFS will have at most m nonzero variables, corresponding to a basis matrix with at most m columns of A
Dr. ISyE 6673: Financial Optimization October 19, 2022 12 31

Duality & SA Column generation
Formulation size
• We can write the formulation in partial vector form as
s.t. 􏰃Ajxj≥b j=1
• Notice that the number of variables is huge!
• Another way to say it is that the matrix A has too many columns!
• An optimal BFS will have at most m nonzero variables, corresponding to a basis matrix with at most m columns of A
• Why should we have a formulation with J ≫ m variables if we will only need m nonzero variables at optimality?
Dr. ISyE 6673: Financial Optimization October 19, 2022 12 31

Duality & SA Column generation
Idea: Restrict the set of patterns
• We can restrict ourselves to a subset of patterns J ⊆ {1,…,J} min 􏰃xj
s.t. 􏰃Ajxj≥b
Dr. ISyE 6673: Financial Optimization October 19, 2022 13 31

Duality & SA Column generation
Idea: Restrict the set of patterns
• We can restrict ourselves to a subset of patterns J ⊆ {1,…,J} min 􏰃xj
s.t. 􏰃Ajxj≥b
• If J contains the m optimal patterns then the optimal solution of the restricted problem is optimal for the full problem
Dr. ISyE 6673: Financial Optimization October 19, 2022 13 31

Duality & SA Column generation
Idea: Restrict the set of patterns
• We can restrict ourselves to a subset of patterns J ⊆ {1,…,J} min 􏰃xj
s.t. 􏰃Ajxj≥b
• If J contains the m optimal patterns then the optimal solution of the restricted problem is optimal for the full problem
• If J is missing at least one optimal pattern, the optimal solution of the restricted problem is suboptimal in the full problem
Dr. ISyE 6673: Financial Optimization October 19, 2022 13 31

Duality & SA Column generation
Solving the restricted problem
• The restricted problem is a lot more tractable (fewer decision variables) but it may produce suboptimal solutions
• Can we even tell if the solution we obtain is optimal in the full problem?
Recall the simplex method!
A basic feasible solution is optimal if all of the associated reduced costs are non-negative!
• How can we check if the reduced costs of the nonbasic variables are non-negative?
Dr. ISyE 6673: Financial Optimization October 19, 2022 14 31

Duality & SA Column generation
Basic variables and reduced costs
• Say we solve the restricted problem with the simplex method and obtain an optimal BFS, there are three kinds of variables:
Basic variables j ∈ {B(1),…,B(m)} ⊆ J
Non-basic variables j ∈ J \{B(1), . . . , B(m)}
Variables that are not even defined in the restricted problem (j ∈/ J ); these are also non-basic by default
• Computing reduced costs:
The basic variables have reduced cost 0 by definition
Dr. ISyE 6673: Financial Optimization October 19, 2022 15 31

Duality & SA Column generation
Basic variables and reduced costs
• Say we solve the restricted problem with the simplex method and obtain an optimal BFS, there are three kinds of variables:
Basic variables j ∈ {B(1),…,B(m)} ⊆ J
Non-basic variables j ∈ J \{B(1), . . . , B(m)}
Variables that are not even defined in the restricted problem (j ∈/ J ); these are also non-basic by default
• Computing reduced costs:
The basic variables have reduced cost 0 by definition
The non-basic variables have non-negative reduced cost because the solution is optimal in the restricted problem
Dr. ISyE 6673: Financial Optimization October 19, 2022 15 31

Duality & SA Column generation
Basic variables and reduced costs
• Say we solve the restricted problem with the simplex method and obtain an optimal BFS, there are three kinds of variables:
Basic variables j ∈ {B(1),…,B(m)} ⊆ J
Non-basic variables j ∈ J \{B(1), . . . , B(m)}
Variables that are not even defined in the restricted problem (j ∈/ J ); these are also non-basic by default
• Computing reduced costs:
The basic variables have reduced cost 0 by definition
The non-basic variables have non-negative reduced cost because the solution is optimal in the restricted problem
The undefined variables have unknown reduced costs
Dr. ISyE 6673: Financial Optimization October 19, 2022 15 31

Duality & SA Column generation
Basic variables and reduced costs
• Say we solve the restricted problem with the simplex method and obtain an optimal BFS, there are three kinds of variables:
Basic variables j ∈ {B(1),…,B(m)} ⊆ J
Non-basic variables j ∈ J \{B(1), . . . , B(m)}
Variables that are not even defined in the restricted problem (j ∈/ J ); these are also non-basic by default
• Computing reduced costs:
The basic variables have reduced cost 0 by definition
The non-basic variables have non-negative reduced cost because the solution is optimal in the restricted problem
The undefined variables have unknown reduced costs
• However, we know the formula for reduced costs!
Dr. ISyE 6673: Financial Optimization October 19, 2022 15 31

Duality & SA Column generation
Computing reduced costs
Definition reminder: reduced cost
For a non-basic variable with index j ∈/ J ,
̄c j = c j − c ⊺B B − 1 A j
Dr. ISyE 6673: Financial Optimization October 19, 2022 16 31

Duality & SA Column generation
Computing reduced costs
Definition reminder: reduced cost
For a non-basic variable with index j ∈/ J ,
̄c j = c j − c ⊺B B − 1 A j
• We can use this definition to compute the reduced cost of patterns that were not included in the restricted problem
• Problem: Checking that every single reduced cost is negative might still take a long time if we do them one by one!
Dr. ISyE 6673: Financial Optimization October 19, 2022 16 31

Duality & SA Column generation
Finding the most negative reduced cost
• Consider the following optimization problem:
z∗ =min ̄cj j ∈/J
Dr. ISyE 6673: Financial Optimization October 19, 2022 17 31

Duality & SA Column generation
Finding the most negative reduced cost
• Consider the following optimization problem: z∗ =min ̄cj
• If z∗ ≥ 0, then all the reduced costs are non-negative and the
solution is optimal in the full problem
• If z∗ < 0, then we’ve found a column/pattern with negative reduced cost! Dr. ISyE 6673: Financial Optimization October 19, 2022 17 31 Duality & SA Column generation Finding the most negative reduced cost • Consider the following optimization problem: z∗ =min ̄cj • If z∗ ≥ 0, then all the reduced costs are non-negative and the solution is optimal in the full problem • If z∗ < 0, then we’ve found a column/pattern with negative reduced cost! How do we solve this subproblem? Dr. ISyE 6673: Financial Optimization October 19, 2022 17 31 Duality & SA Column generation Solving the subproblem • Recall that we can describe a feasible pattern a as follows: 􏰃aiwi ≤W i=1 • We can simpliy the expression of the reduced cost of pattern a since every pattern has cost 1 ̄c = 1 − c ⊺B B − 1 a = 1 − p ⊺ a = 1 − 􏰃 p i a i , where pi is the dual optimal solution in the restricted problem • Minimizing ̄c is equivalent to maximizing 􏰂i=1 piai Dr. ISyE 6673: Financial Optimization October 19, 2022 18 31 Duality & SA Column generation Solving the subproblem • So we can write the subproblem as follows: m z∗=max 􏰃piai s.t. 􏰃aiwi≤W i=1 Dr. ISyE 6673: Financial Optimization October 19, 2022 19 31 Duality & SA Column generation Solving the subproblem • So we can write the subproblem as follows: m z∗=max 􏰃piai s.t. 􏰃aiwi≤W i=1 • z∗ > 1 ⇒ found pattern with negative reduced cost
Dr. ISyE 6673: Financial Optimization October 19, 2022 19 31

Duality & SA Column generation
Solving the subproblem
• So we can write the subproblem as follows:
m z∗=max 􏰃piai
s.t. 􏰃aiwi≤W i=1
• z∗ > 1 ⇒ found pattern with negative reduced cost
• We need to keep the integer variables because ai is the number of rolls of width wi to include in the pattern: not easily rounded
Dr. ISyE 6673: Financial Optimization October 19, 2022 19 31

Duality & SA Column generation
Solving the subproblem
• So we can write the subproblem as follows:
m z∗=max 􏰃piai
s.t. 􏰃aiwi≤W i=1
• z∗ > 1 ⇒ found pattern with negative reduced cost
• We need to keep the integer variables because ai is the number of rolls of width wi to include in the pattern: not easily rounded
• This problem is called the knapsack problem
Dr. ISyE 6673: Financial Optimization October 19, 2022 19 31

Duality & SA Column generation
Knapsack problem
• A classic combinatorial optimization problem
Dr. ISyE 6673: Financial Optimization October 19, 2022 20 31

Duality & SA Column generation
Knapsack problem
• A classic combinatorial

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts