1.206J/16.77J/ESD.215J
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J
Multi-commodity Network Flows,
A Keypath Formulation
? Outline
– Path formulation for multi-commodity
flow problems revisited
– Keypath formulation
– Example
– Keypath solution algorithm
? Column generation
? Row generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Path Notation
Sets
A,set of all network arcs
K,set of all commodities
N,set of all network nodes
Parameters
uij, total capacity on arc ij
dk, total quantity of
commodity k
Pk,set of all paths for
commodity k,for all k
Parameters (cont.)
cp, per unit cost of
commodity k on path p =
?ij ?p cijk
?ijp, = 1 if path p contains
arc ij; and = 0 otherwise
Decision Variables
fp,fraction of total quantity
of commodity k assigned to
path p
14-May-10 1.224J/ESD.204J 4
The Path Formulation Revisited
MINIMIZE ? k ?K ? p?Pk dk cp fp
subject to,?p?Pk ? k ?K dk fp?ijp ? uij ? ij?A
?p?Pk fp = 1 ? k?K
fp ? 0 ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
The Keypath Concept
? The path formulation for MCF problems can be
recast equivalently as follows:
– Assign all flow of commodity k to a selected path p,
called the keypath,for each commodity k?K
? Often the keypath is the minimum cost path for k
? The resulting flow assignment is often infeasible
– One or more arc capacity constraints are violated
? If the resulting flows are feasible and the keypaths are
minimum cost,the flow assignment is optimal
– Solve a linear programming formulation to minimize
the cost of adjusting flows to achieve feasibility
? Flow adjustments involve removing flow of k from its
keypath p and placing it on alternative path p’?Pk,for each
k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Additional Keypath Notation
Parameters
p(k), keypath for commodity k
Qij, total initial (flow assigned to keypaths) on arc ij
= ? k ?K dk?ijp(k)
crp(k), = cr – cp(k) = ? ij ?A cij?ijr - ? ij ?A cij?ijp(k);
change in cost when one unit of commodity k is
shifted from keypath p(k) to path r (Note,typically
non-negative if p(k) has minimum cost)
Decision Variables
frp(k),fraction of total quantity of commodity k
removed from keypath p(k) to path r
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
The Keypath Formulation
? ?
KkPrf
Kkf
AijQu
fdfd
fdc
kr
kp
Pr
r
kp
ijij
Kk Pr
r
kpk
r
ij
Kk Pr
r
kpk
kp
ij
Kk Pr
r
kpk
r
kp
k
kk
k
?????
???
????
??
?
? ?? ?
? ?
?
? ?? ?
? ?
0
1
:s,t,
M i n
)(
)(
)()(
)(
)()(
??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Associated Dual Variables
Duals
- ?ij, the dual variable associated with the bundle
constraint for arc ij (? is non-negative)
- ?k,the dual variable associated with the commodity
constraints (? is non-negative)
Economic Interpretation
? ij, the value of an additional unit of capacity on arc ij
? k/dk, the minimal cost to remove an additional unit
of commodity k from its keypath and place on
another path
14-May-10 1.224J/ESD.204J 9
Optimality Conditions for the Path
Formulation
f*p and ?*ij,?*k are optimal for all k and all ij
if:
1,Primal feasibility is satisfied
2,Complementary slackness is satisfied
3,Dual feasibility is satisfied (reduced cost is
non-negative for a minimization problem)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Modified Costs
Definition,Reduced cost for path r,commodity k
= ?ij?A cijk dk ?ijr - ?ij?A cijk dk ?ijp(k) + ?ij?A ?ijdk?ijr
- ?ij?A ?ij dk ?ijp(k) + ?k
= ?ij?A (cijk + ?ij )?ijr –
?ij?A (cijk + ?ij)?ijp(k) + ?k /dk
Definition,Let modified cost for arc ij and
commodity k = cijk + ?ij
?Reduced cost is non-negative for all commodity k
variables if the modified cost of path r equals or
exceeds the modified cost of p(k) less ?k/dk
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Column Generation- A Price
Directive Decomposition
Millions/Billions of Variables
Never Considered
Restricted Master
Problem (RMP)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
LP Solution,Column Generation
? Step 1,Solve Restricted Master Problem (RMP) with
subset of all variables (columns)
? Step 2,Solve Pricing Problem to determine if any
variables when added to the RMP can improve the
objective function value (that is,if any variables
have negative reduced cost)
? Step 3,If variables are identified in Step 2,add
them to the RMP and return to Step 1; otherwise
STOP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Pricing Problem
? Given ? and ?k,the optimal (non-negative) duals for the
current restricted master problem and the keypath p(k),
the pricing problem,for each k? K is
min r? Pk (dk (?ij?A (cijk + ?ij )?ijr – ?ij?A (cijk + ?ij) ?ijp(k)
+ ?k /dk )
Or,letting C = ?ij?A (cijk + ?ij) ?ijp(k) - ?k /dk equivalently:
min r? Pk ? ij ?A (cijk + ?ij) ?ijr - C
? A shortest path problem for commodity k (with
modified arc costs),If min r? Pk ? ij ?A (cijk + ?ij) ?ijr - C ?
0,then the original problem is solved,else add column
corresponding to xp(k)r to the master problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Example- Iteration 1
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 - 15 15 - 15 0 - 15 0 0 0 < = 2 0 - 15 ?
a
= 0
b - 5 5 - 5 0 0 15 0 0 0 < = 1 0 - 5 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 - 0 ?
c
= 0
d 0 0 0 - 15 15 - 15 0 - 15 0 - 5 5 - 5 0 < = 1 0 - 20 ?
d
= 2
e 0 0 15 0 15 5 0 10 - 10 < = 4 0 - 10 ?
e
= 0
k = 1 1 1 - 1 < = 1 ?
?
k = 2 1 1 - 1 1 < = 1 ?
?
k = 3 1 1 - 1 < = 1 ?
?
k = 4 1 - 1 < = 1 ?
?
C o s t,
20 - 10 10 - 10 16 5 - 75 75 - 75 13 5 - 75 40 - 30 30 - 30 50 - 50
Va ri a b l e
1
2
f
=0
2
2
f
**
3
4
f
4
4
f
**
5
4
f
=0
6
7
f =2
7
7
f **
8
8
f **
Let p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 8 (** denotes keypath)
NOTE,Gray columns not included in keypath
formulation; purple elements are initial keypath matrix
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Example- Iteration 2
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 - 15 15 - 15 0 - 15 0 0 0 < = 2 0 - 15 ?
a
= 0
b - 5 5 - 5 0 0 15 0 0 0 < = 1 0 - 5 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 - 0 ?
c
= 0
d 0 0 0 - 15 15 - 15 0 - 15 0 - 5 5 - 5 0 < = 1 0 - 20 ?
d
= 4
e 0 0 15 0 15 5 0 10 - 10 < = 4 0 - 10 ?
e
= 0
k = 1 1 1 - 1 < = 1 ?
?
k = 2 1 1 - 1 1 < = 1 ?
?
k = 3 1 1 - 1 < = 1 ?
?
= 1 0
k = 4 1 - 1 < = 1 ?
?
C o s t,
20 - 10 10 - 10 165 - 75 75 - 75 135 - 75 40 - 30 30 - 30 50 - 50
Va ri a b l e
1
2
f
=0
2
2
f
**
3
4
f
4
4
f
**
5
4
f
= 1 / 3
6
7
f =1
7
7
f **
8
8
f **
2nd iteration,no columns price out,one constraint for
commodity 3 is violated and added; and the problem is
resolved– feasibility and optimality achieved
Let p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 8 (** denotes keypath)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Column Generation
A n y
N e w C o lu mn s?
S T O P
(L P O p t ima l)
S o lv e
R e s t ri c t e d Ma s t e r P r o b le m
(R MP )
S o lv e
P ri c in g P r o b le m
U p d a t e R MP w it h
N e w C o lu mn s
No
Y e s
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Row Generation
A n y
N e w C o n s t ra in t s?
S T O P
(L P O p t ima l)
S o lv e
R e la x e d P ro b le m ( R P )
S o lv e
S e p a ra t io n P ro b le m
U p d a t e R P w it h
N e w C o n s t ra in t s
No
Y e s
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Column
and Row
Generation
A n y
N e w C o l u m n s?
S o l v e
R e s t r i c t e d M a s t e r P r o b l e m
( R M P )
S o l v e
P r i c i n g P r o b l e m
U p d a t e R M P w i t h
N e w C o l u m n s
S e t O P T _ C u t = N O
No
Y e s
A n y
N e w C o n s t r a i n t s?
S o l v e
R e l a x e d P r o b l e m ( R P )
S o l v e
S e p a r a t i o n P r o b l e m
No
S e t
O P T _ C o l = N O
O P T _ C u t = N O
U p d a t e R P w i t h
N e w C o n s t r a i n t s
S e t O P T _ C o l = N O
S e t
O P T _ C o l = Y E S
O P T _ C o l = Y E S
O P T _ C u t = Y E S
Y e s
S e t
O P T _ C u t = Y E S
O P T _ C o l = Y E S
O P T _ C u t = Y E S
Y e s
No
Y e s
No
S T O P
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Column and Row Generation,
Constraint Matrix
O r i g i n a l R M P 1
2
3
4
5
6
7
8
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
The Benefit of the Keypath
Concept
? We are now minimizing the objective
function and most of the objective
coefficients are __________,Therefore,this
will guide the decision variables to values of
__________.
? How does this help?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Solution Procedure
? Use Both Column Generation and Row Generation
? Actual flow of problem
– Step 1- Define RMP for Iteration 1,Set k =1,Denote an
initial subset of columns (A1) which is to be used,
– Step 2- Solve RMP for Iteration k,Solve a problem with
the subset of columns Ak.
– Step 3- Generate Rows,Determine if any constraints are
violated and express them explicitly in the constraint
matrix.
– Step 4- Generate Columns,Price some of the remaining
columns,and add a group (A*) that have a reduced cost
less than zero,i.e.,Ak+1=[Ak |A*]
– Step 5- Test Optimality,If no columns or rows are added,
terminate,Otherwise,k =k+1,go to Step 2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Conclusions
? Variable redefinition
– Allows relaxation of constraints and subsequent
(limited) cut generation
– Does not alter the pricing problem solution
? Shortest paths with modified costs
– Allows problems with many commodities,as well
as a large underlying network,to be solved with
limited memory requirements
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J
Multi-commodity Network Flows,
A Keypath Formulation
? Outline
– Path formulation for multi-commodity
flow problems revisited
– Keypath formulation
– Example
– Keypath solution algorithm
? Column generation
? Row generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Path Notation
Sets
A,set of all network arcs
K,set of all commodities
N,set of all network nodes
Parameters
uij, total capacity on arc ij
dk, total quantity of
commodity k
Pk,set of all paths for
commodity k,for all k
Parameters (cont.)
cp, per unit cost of
commodity k on path p =
?ij ?p cijk
?ijp, = 1 if path p contains
arc ij; and = 0 otherwise
Decision Variables
fp,fraction of total quantity
of commodity k assigned to
path p
14-May-10 1.224J/ESD.204J 4
The Path Formulation Revisited
MINIMIZE ? k ?K ? p?Pk dk cp fp
subject to,?p?Pk ? k ?K dk fp?ijp ? uij ? ij?A
?p?Pk fp = 1 ? k?K
fp ? 0 ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
The Keypath Concept
? The path formulation for MCF problems can be
recast equivalently as follows:
– Assign all flow of commodity k to a selected path p,
called the keypath,for each commodity k?K
? Often the keypath is the minimum cost path for k
? The resulting flow assignment is often infeasible
– One or more arc capacity constraints are violated
? If the resulting flows are feasible and the keypaths are
minimum cost,the flow assignment is optimal
– Solve a linear programming formulation to minimize
the cost of adjusting flows to achieve feasibility
? Flow adjustments involve removing flow of k from its
keypath p and placing it on alternative path p’?Pk,for each
k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
Additional Keypath Notation
Parameters
p(k), keypath for commodity k
Qij, total initial (flow assigned to keypaths) on arc ij
= ? k ?K dk?ijp(k)
crp(k), = cr – cp(k) = ? ij ?A cij?ijr - ? ij ?A cij?ijp(k);
change in cost when one unit of commodity k is
shifted from keypath p(k) to path r (Note,typically
non-negative if p(k) has minimum cost)
Decision Variables
frp(k),fraction of total quantity of commodity k
removed from keypath p(k) to path r
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
The Keypath Formulation
? ?
KkPrf
Kkf
AijQu
fdfd
fdc
kr
kp
Pr
r
kp
ijij
Kk Pr
r
kpk
r
ij
Kk Pr
r
kpk
kp
ij
Kk Pr
r
kpk
r
kp
k
kk
k
?????
???
????
??
?
? ?? ?
? ?
?
? ?? ?
? ?
0
1
:s,t,
M i n
)(
)(
)()(
)(
)()(
??
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
Associated Dual Variables
Duals
- ?ij, the dual variable associated with the bundle
constraint for arc ij (? is non-negative)
- ?k,the dual variable associated with the commodity
constraints (? is non-negative)
Economic Interpretation
? ij, the value of an additional unit of capacity on arc ij
? k/dk, the minimal cost to remove an additional unit
of commodity k from its keypath and place on
another path
14-May-10 1.224J/ESD.204J 9
Optimality Conditions for the Path
Formulation
f*p and ?*ij,?*k are optimal for all k and all ij
if:
1,Primal feasibility is satisfied
2,Complementary slackness is satisfied
3,Dual feasibility is satisfied (reduced cost is
non-negative for a minimization problem)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
Modified Costs
Definition,Reduced cost for path r,commodity k
= ?ij?A cijk dk ?ijr - ?ij?A cijk dk ?ijp(k) + ?ij?A ?ijdk?ijr
- ?ij?A ?ij dk ?ijp(k) + ?k
= ?ij?A (cijk + ?ij )?ijr –
?ij?A (cijk + ?ij)?ijp(k) + ?k /dk
Definition,Let modified cost for arc ij and
commodity k = cijk + ?ij
?Reduced cost is non-negative for all commodity k
variables if the modified cost of path r equals or
exceeds the modified cost of p(k) less ?k/dk
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Column Generation- A Price
Directive Decomposition
Millions/Billions of Variables
Never Considered
Restricted Master
Problem (RMP)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
LP Solution,Column Generation
? Step 1,Solve Restricted Master Problem (RMP) with
subset of all variables (columns)
? Step 2,Solve Pricing Problem to determine if any
variables when added to the RMP can improve the
objective function value (that is,if any variables
have negative reduced cost)
? Step 3,If variables are identified in Step 2,add
them to the RMP and return to Step 1; otherwise
STOP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Pricing Problem
? Given ? and ?k,the optimal (non-negative) duals for the
current restricted master problem and the keypath p(k),
the pricing problem,for each k? K is
min r? Pk (dk (?ij?A (cijk + ?ij )?ijr – ?ij?A (cijk + ?ij) ?ijp(k)
+ ?k /dk )
Or,letting C = ?ij?A (cijk + ?ij) ?ijp(k) - ?k /dk equivalently:
min r? Pk ? ij ?A (cijk + ?ij) ?ijr - C
? A shortest path problem for commodity k (with
modified arc costs),If min r? Pk ? ij ?A (cijk + ?ij) ?ijr - C ?
0,then the original problem is solved,else add column
corresponding to xp(k)r to the master problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Example- Iteration 1
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 - 15 15 - 15 0 - 15 0 0 0 < = 2 0 - 15 ?
a
= 0
b - 5 5 - 5 0 0 15 0 0 0 < = 1 0 - 5 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 - 0 ?
c
= 0
d 0 0 0 - 15 15 - 15 0 - 15 0 - 5 5 - 5 0 < = 1 0 - 20 ?
d
= 2
e 0 0 15 0 15 5 0 10 - 10 < = 4 0 - 10 ?
e
= 0
k = 1 1 1 - 1 < = 1 ?
?
k = 2 1 1 - 1 1 < = 1 ?
?
k = 3 1 1 - 1 < = 1 ?
?
k = 4 1 - 1 < = 1 ?
?
C o s t,
20 - 10 10 - 10 16 5 - 75 75 - 75 13 5 - 75 40 - 30 30 - 30 50 - 50
Va ri a b l e
1
2
f
=0
2
2
f
**
3
4
f
4
4
f
**
5
4
f
=0
6
7
f =2
7
7
f **
8
8
f **
Let p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 8 (** denotes keypath)
NOTE,Gray columns not included in keypath
formulation; purple elements are initial keypath matrix
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Example- Iteration 2
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 - 15 15 - 15 0 - 15 0 0 0 < = 2 0 - 15 ?
a
= 0
b - 5 5 - 5 0 0 15 0 0 0 < = 1 0 - 5 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 - 0 ?
c
= 0
d 0 0 0 - 15 15 - 15 0 - 15 0 - 5 5 - 5 0 < = 1 0 - 20 ?
d
= 4
e 0 0 15 0 15 5 0 10 - 10 < = 4 0 - 10 ?
e
= 0
k = 1 1 1 - 1 < = 1 ?
?
k = 2 1 1 - 1 1 < = 1 ?
?
k = 3 1 1 - 1 < = 1 ?
?
= 1 0
k = 4 1 - 1 < = 1 ?
?
C o s t,
20 - 10 10 - 10 165 - 75 75 - 75 135 - 75 40 - 30 30 - 30 50 - 50
Va ri a b l e
1
2
f
=0
2
2
f
**
3
4
f
4
4
f
**
5
4
f
= 1 / 3
6
7
f =1
7
7
f **
8
8
f **
2nd iteration,no columns price out,one constraint for
commodity 3 is violated and added; and the problem is
resolved– feasibility and optimality achieved
Let p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 8 (** denotes keypath)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
Column Generation
A n y
N e w C o lu mn s?
S T O P
(L P O p t ima l)
S o lv e
R e s t ri c t e d Ma s t e r P r o b le m
(R MP )
S o lv e
P ri c in g P r o b le m
U p d a t e R MP w it h
N e w C o lu mn s
No
Y e s
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Row Generation
A n y
N e w C o n s t ra in t s?
S T O P
(L P O p t ima l)
S o lv e
R e la x e d P ro b le m ( R P )
S o lv e
S e p a ra t io n P ro b le m
U p d a t e R P w it h
N e w C o n s t ra in t s
No
Y e s
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
Column
and Row
Generation
A n y
N e w C o l u m n s?
S o l v e
R e s t r i c t e d M a s t e r P r o b l e m
( R M P )
S o l v e
P r i c i n g P r o b l e m
U p d a t e R M P w i t h
N e w C o l u m n s
S e t O P T _ C u t = N O
No
Y e s
A n y
N e w C o n s t r a i n t s?
S o l v e
R e l a x e d P r o b l e m ( R P )
S o l v e
S e p a r a t i o n P r o b l e m
No
S e t
O P T _ C o l = N O
O P T _ C u t = N O
U p d a t e R P w i t h
N e w C o n s t r a i n t s
S e t O P T _ C o l = N O
S e t
O P T _ C o l = Y E S
O P T _ C o l = Y E S
O P T _ C u t = Y E S
Y e s
S e t
O P T _ C u t = Y E S
O P T _ C o l = Y E S
O P T _ C u t = Y E S
Y e s
No
Y e s
No
S T O P
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Column and Row Generation,
Constraint Matrix
O r i g i n a l R M P 1
2
3
4
5
6
7
8
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
The Benefit of the Keypath
Concept
? We are now minimizing the objective
function and most of the objective
coefficients are __________,Therefore,this
will guide the decision variables to values of
__________.
? How does this help?
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
Solution Procedure
? Use Both Column Generation and Row Generation
? Actual flow of problem
– Step 1- Define RMP for Iteration 1,Set k =1,Denote an
initial subset of columns (A1) which is to be used,
– Step 2- Solve RMP for Iteration k,Solve a problem with
the subset of columns Ak.
– Step 3- Generate Rows,Determine if any constraints are
violated and express them explicitly in the constraint
matrix.
– Step 4- Generate Columns,Price some of the remaining
columns,and add a group (A*) that have a reduced cost
less than zero,i.e.,Ak+1=[Ak |A*]
– Step 5- Test Optimality,If no columns or rows are added,
terminate,Otherwise,k =k+1,go to Step 2
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
Conclusions
? Variable redefinition
– Allows relaxation of constraints and subsequent
(limited) cut generation
– Does not alter the pricing problem solution
? Shortest paths with modified costs
– Allows problems with many commodities,as well
as a large underlying network,to be solved with
limited memory requirements
