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 Airline
Schedule Planning,Multi-commodity
Flows
Outline
? Applications
? Problem Definition
? Formulations
? Solutions
? Results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Application I
? Package flow problem (express package
delivery operation)
– Shipments have specific origins and destinations
and must be routed over a transportation
network
– Each set of packages with a common origin-
destination pair is called a commodity
? Time windows (availability and delivery time)
associated with packages
– The objective might be to minimize total costs,
find a feasible flow,...
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Application II
? Passenger mix problem
– Given a fixed schedule of flights,a fixed
fleet assignment and a set of customer
demands for air travel service on this
fleeted schedule,the airline's objective is to
maximize revenues by accommodating as
many high fare passengers as possible
– For some flights,demand exceeds seat
supply and passengers must be spilled to
other itineraries of either the same or
another airline
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Application III
? Message routing problem
– In a telecommunications or computer
network,requirements exist for
transmission lines and message requests,or
commodities,
– The problem is to route the messages from
their origins to their respective destinations
at minimum cost
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
MCF Networks
? Set of nodes
– Each node associated with the supply of or
demand for commodities
? Set of arcs
– Cost per unit commodity flow
– Capacity limiting the total flow of all
commodities and/ or the flow of
individual commodities
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
MCF Commodity Definitions
? A commodity may originate at a subset of
nodes in the network and be destined for
another subset of nodes
? A commodity may originate at a single node
and be destined for a subset of the nodes
? A commodity may originate at a single node
and be destined for a single node
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
MCF Objectives
? Flow the commodities through the networks
from their respective origins to their
respective destinations at minimum cost
– Expressed as distance,money,time,etc.
? Ahuja,Magnanti and Orlin (1993)-- survey of
multi-commodity flow models and solution
procedures
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
MCF Problem Formulations --
Linear Programs
? Network flow problems
– Capacity constraints limit flow of individual
commodities
– Conservation of flow constraints ensure flow
balance for individual commodities
– Flow non-negativity constraints
? With side constraints
– Bundle constraints restrict total flow of ALL
commodities on an arc
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
MCF Constraint Matrix
Network flow
problem,
commodity k=1
Bundle constraints limiting total flow of all commodities to arc capacities
Network flow
problem,
commodity k=2
Network flow
problem,
commodity k=3
Network flow
problem,
commodity k=4
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Alternative Formulations for O-D
Commodity Case
? Node-Arc Formulation
– Decision variables,flow of commodity k on each arc ij
? Path Formulation
– Decision variables,flow of commodity k on each path for
k
?,Tree” or,Sub-network” Formulation
– Define,super commodity,set of all (O-D) commodities
with the same origin o (or destination d)
– Decision variables,quantity of the super commodity k’
assigned to each,tree” or,sub-network” for k’
? Formulations are equivalent
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Sample Network
Commodities
# o d quant
1 1 3 5
2 1 4 15
3 2 4 5
4 3 4 10
Arcs
i j cost capy
1 2 1 20
1 3 2 10
2 3 3 20
2 4 4 10
3 4 5 40
1
2
3
4
a
b
c
d
e
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Notation
Parameters
? A,set of all network arcs
? K,set of all commodities
? N,set of all network nodes
? O(k) [D(k)],origin [destination]
node for commodity k
? cijk, per unit cost of
commodity k on arc ij
? uij, total capacity on arc ij
(assume uijk is unlimited for
each k and each ij)
? dk, total quantity of
commodity k
Decision Variables
? xijk, number of units
of commodity k
assigned to arc ij
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Node-Arc Formulation
M i n i m i z e c x
ij
k
ij
k
kij
??
s ub j e c t t o
ot her w i s e
kDid
kOidxx
k
k
j
k
ji
j
k
ij
0
)( if
)( if
?
???
??? ??
, Co n s e r v a t i o n o f F l o w
x u i j A
ij
k
k
ij
? ? ? ?(,), B un dl e c o n s t r a i n t s
x i j A k K
ij
k
? ? ? ?0 (,),
, N o n n e ga t i v i t y c o n s t r a i n t s
k1 k2 k3 k4
a b c d e a b c d e a b c d e a b c d e RH S
1 1 1 = d 1
2 -1 1 1 = 0
3 -1 -1 1 = - d 1
4 -1 -1 = 0
1 1 1 = d 2
2 -1 1 1 = 0
3 -1 -1 1 = 0
4 -1 -1 = - d 2
1 1 1 = 0
2 -1 1 1 = d 3
3 -1 -1 1 = 0
4 -1 -1 = - d 3
1 1 1 = 0
2 -1 1 1 = 0
3 -1 -1 1 = d 4
4 -1 -1 = - d 4
a 1 1 1 1 ? u
a
b 1 1 1 1 ? u
b
c 1 1 1 1 ? u
c
d 1 1 1 1 ? u
d
e 1 1 1 1 ? u
e
c a
1
c b
1
c c
1
c d
1
c e
1
c a
2
c b
2
c c
2
c d
2
c e
2
c a
3
c b
3
c c
3
c d
3
c e
3
c a
4
c b
4
c c
4
c d
4
c e
4
x a
1
x b
1
x c
1
x d
1
x e
1
x a
2
x b
2
x c
2
x d
2
x e
2
x a
3
x b
3
x c
3
x d
3
x e
3
x a
4
x b
4
x c
4
x d
4
x e
4
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Additional Notation
Parameters
? Pk,set of all paths for
commodity k,for all k
? 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
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
O/D Based Path Formulation
? ?
?k Pp
ppk
k
fCd
subject to
d f u i j Ak p ijp
p P
ij
k k
?
?
?? ? ? ?(,), Bundle constraints
f k Kp
p P k?
? ? ? ?1, Flow balance constraints
f p P k Kp k? ? ? ?0,,Non-neg,constraints
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a d 1 0 d 2 d 2 0 0 0 0 < = u a ??????? ?
a ?
b 0 d 1 0 0 d 2 0 0 0 < = u b ??
b
c d 1 0 d 2 0 0 d 3 0 0 < = u c ??
c
d 0 0 0 d 2 0 0 d 3 0 < = u d ??
d
e 0 0 d 2 0 d 2 d 3 0 d 4 < = u e ??
e
k = 1 1 1 = 1 ?
?
?
k = 2 1 1 1 = 1 ?
?
?
k = 3 1 1 = 1 ?
?
?
k = 4 1 = 1 ?
?
?
C o s t,
11
dC
12
dC
23
dC 24
dC
25
dC
36
dC
37
dC
38
dC
Va ri a b l e
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
Minimize
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Additional Notation
Parameters
? S,set of source nodes
n?N for all commodities
? Qs,the set of all sub-
networks originating at s
? TCqs,total cost of sub-
network q originating at s
? ?pq, = 1 if path p is
contained in sub-network
q; and = 0 otherwise
Decision Variables
? Rqs, fraction of
total quantity of the
super commodity
originating at s
assigned to sub-
network q
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
S ub - n e t w o rk
o = 1 o = 2 o = 3 RHS D u a l
a d
1
+ d
2
d
1
+ d
2
d
1
d
2
d
2
0 0 0 0 < = u
a
?
a
?
b 0 0 d
2
d
1
d
1
d
1
+ d
2
0 0 0 < = u
b
?
b
c d
1
d
1
+ d
2
d
1
0 d
2
0 d
3
0 0 < = u
c
?
c
d d
2
0 0 d
2
0 0 0 d
3
0 < = u
d
?
d
e 0 d
2
d
2
0 d
2
d
2
d
3
0 d
4
< = u
e
?
e
o = 1 1 1 1 1 1 1 = 1 ?
?
?
o = 2 1 1 = 1 ?
?
?
o = 3 1 = 1 ?
?
?
C o s t, TC
1
1
TC
2
1
TC
3
1
TC
4
1
TC
5
1
TC
6
1
TC
1
2
TC
2
2
TC
1
3
Va ri a b l e R
1
1
R
2
1
R
3
1
R
4
1
R
5
1
R
6
1
R
1
2
R
2
2
R
1
3
Sub-network Formulation
q
s? Qq
k
qk Pp
q
pp RdC
s k
? ? ? ?
? ? ?
)( ? s
subject to
? ? ? ? ???
? ? ?s
ij
Qq
q
pq
sk Pp
p
ijk AjiuRd
s k
),()( s?????, Capacity Limits on Each Arc
R s s Sq
q Qs?
? ? ? ?1, Mass Balance Requirements
R s q Q s Sq s? ? ? ?0,,Nonnegative Path Flow Variables
Minimize
S
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Linear MCF Problem Solution
? Obvious Solution
– LP Solver
? Difficulty
– Problem Size,(|N|=|Nodes|,|C|=|Commodities|,
|A|=|Arcs|)
? Node-arc formulation:
– Constraints,|N|*|C| + |A|
– Variables,|A|*|C|
? Path formulation:
– Constraints,|A| + |C|
– Variables,|Paths for ALL commodities|
? Sub-network formulation:
– Constraints,|A|+|Origins|
– Variables,|Combinations of Paths by Origin|
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
General MCF Solution Strategy
? Try to Decompose a Hard Problem Into a Set of
Easy Problems
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
MCF Solution Procedures I
? Partitioning Methods
– Exploit Network Structure to Speed Up Simplex
Matrix Computations
? Resource-Directive Decomposition
– Repeat until Optimal:
? Allocate Arc Capacity Among Commodities
? Find Optimal Flows Given Allocation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
MCF Solution Procedures II
? Price-Directive Decomposition
– Repeat until Optimal:
? Modify Flow Cost on Arc
? Ignore Bundle Constraints,Find Optimal Flows
14-May-10 1.224J/ESD.204J 23
Revisiting the Path
Formulation
MINIMIZE ? k ?K ? p?Pk dk cp fp
subject to,?p?Pk? k ?K dk fp?ijp ? uij ? ij?A
?p?P(k) fp = 1 ? k?K
fp? 0 ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
By-products of the Simplex
Algorithm,Dual Variable Values
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
Economic Interpretation
? ij, the value of an additional unit of capacity on arc ij
? k/dk, the minimal cost to send an additional unit of
commodity k through the network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Modified Costs
Definition,Modified cost for arc ij and
commodity k = cijk+?ij
Definition,Modified cost for path p and
commodity k = ?ij?A (cijk + ?ij )?ijp
14-May-10 1.224J/ESD.204J 26
Optimality Conditions for the Path Formulation
f*p and ?*ij,?*k are optimal for all k and all ij iff:
Primal feasibility is satisfied
1,?p?Pk ? k ?K dk f*p?ijp ? uij ? ij?A
2,?p?P(k) f*p = 1 ? k?K
3,f*p ? 0 ? p?Pk,? k?K
Complementary slackness is satisfied
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
2,?*k (?p? Pk f*p – 1) = 0,? k?K
Dual feasibility is satisfied (reduced cost is non-negative
for a minimization problem)
1,(dk cp + ? ij ?A dk?ij ?ijp ) - ?k = dk (? ij ?A (cijk + ?ij)
?ijp - ?k /dk ) ? 0,? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Multi-commodity Flow
Optimality Conditions
? The price for an additional unit of capacity is 0
unless capacity is fully utilized
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
? A path p for commodity k is utilized only if its
“modified cost” (that is,?ij?A (cijk + ?*ij?ijp)) is
minimal,for all paths p?Pk
1,Reduced Costs all non-negative:
c’p = dk (? ij ?A (cijk + ?*ij) ?ijp - ?*k /dk ) ? 0,
? p? Pk,? k? K
2,f*p (?ij?A (cijk + ?*ij )?ijp - ?*k /dk ) = 0,
? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
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 29
RMP and Optimality Conditions
Consider f*p and ?*ij,?*k optimal for RMP,then
Primal feasibility is satisfied
1,?p?Pk ? k ?K dk f*p?ijp ? uij ? ij?A
2,?p?P(k) f*p = 1 ? k?K
3,f*p ? 0 ? p?Pk,? k?K
Complementary slackness is satisfied
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
2,?*k (?p? Pk f*p – 1) = 0,? k?K
Dual feasibility is guaranteed (reduced cost is non-
negative) ONLY for a path p included in RMP
1,(dk cp + ? ij ?A dk?ij ?ijp ) - ?k = dk (? ij ?A (cijk +
?ij) ?ijp - ?k /dk ) ? 0,? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
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 31
Pricing Problem
? Given ?,?the optimal (non-negative) duals for
the current restricted master problem,?the
pricing problem,for each p? Pk,k? K is
min p? Pk (dk (? ij ?A (cijk + ?ij) ?ijp - ?k /dk )
Or,equivalently:
min p? Pk ? ij ?A (cijk + ?ij) ?ijp
?A shortest path problem for commodity k (with
modified arc costs)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Example- Iteration 1
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 15 0 0 0 0 < = 2 0 ?
a
= 0 ?
b 0 5 0 0 15 0 0 0 < = 1 0 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 ?
c
= 0
d 0 0 0 15 0 0 5 0 < = 1 0 ?
d
= 0
e 0 0 15 0 15 5 0 10 < = 4 0 ?
e
= 0
k = 1 1 1 = 1 ?
?
= 1 0 ?
k = 2 1 1 1 = 1 ?
?
= 1 3 5 ?
k = 3 1 1 = 1 ?
?
= 2 0 ?
k = 4 1 = 1 ?
?
= 5 0 ?
C o s t,
20 10 135 75 105 40 20 50
Va ri a b l e
1
f
2
f
= 1
3
f = 1
4
f
5
f
6
f
7
f = 1
8
f = 1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Example- Iteration 2
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 15 0 0 0 0 < = 2 0 ?
a
= 0 ?
b 0 5 0 0 15 0 0 0 < = 1 0 ?
b
= 2
c 5 0 15 0 0 5 0 0 < = 2 0 ?
c
= 0
d 0 0 0 15 0 0 5 0 < = 1 0 ?
d
= 4
e 0 0 15 0 15 5 0 10 < = 4 0 ?
e
= 0
k = 1 1 1 = 1 ?
?
= 2 0 ?
k = 2 1 1 1 = 1 ?
?
= 1 3 5 ?
k = 3 1 1 = 1 ?
?
= 4 0 ?
k = 4 1 = 1 ?
?
= 5 0 ?
C o s t,
20 10 135 75 105 40 20 50
Va ri a b l e
1
f
2
f
= 1
3
f = 1 / 3
4
f
= 1 / 3
5
f = 1 / 3
6
f
7
f = 1
8
f = 1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
MCF Optimality Conditions
? For each p?Pk,for each k,the reduced cost c?p:
– c?p ??(dk cp + ? ij ?A dk ?ij ?ijp ) - ?k = ?ij (dkcijk + dk?ij)?ijp -
?k = ?ij (cijk + ?ij)?ijp - ?k /dk ?0?
? where ?,?? are the optimal duals for the current restricted
master problem
– c?p ??0,?for each utilized path p implies
?ij (dkcijk + dk?ij) ?ijp = ?k
or equivalently,
?ij (cijk + ?ij) ?ijp = ?k/dk
– So if,minp?P(k) c?p = ?ij (cijk + ?ij) ?ijp* - ?k/dk ?0,?the
current solution to the restricted master problem is
optimal for the original problem
– If minp?P(k) c?p = ?ij (cijk + ?ij) ?ijp* - ?k/dk <?0,?add p* to
restricted master problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Data Set? Data Set
? Constraint Matrix Size
N o d e s 807
L i n k s 1,3 6 3
c a p a c i t a t e d 292
u n c a p a c i t a t e d 1,0 7 1
O / D 1 7,5 3 9
# O r i g i n 136
I m p r o v e m e n t
r o w c o l u m n n e w _ r o w
N o d e _ A r c 1 4,1 5 5,3 3 6 2 3,9 0 5,6 5 7 -
P a t h 1 8,9 0 2 - 1 7,8 3 2
S u b - n e t w o r k 1,4 9 9 - 428
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Computational Results
? Number of Nodes,807
? Number of Links,1,363
? Number of Commodities,17,539
? Computational Result (IBM RS6000,Model
370)
– Path Model,44 minutes
– Sub-network Model,< 1 minute
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Conclusions I
? Choose your formulation carefully
– Trade-off memory requirements and solution time
– Sub-network formulation can be effective when
low level of congestion in the network
? Problem size often mandates use of combined
column and row generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Conclusions II
? Solution time is affected dramatically by
– The complexity of the pricing problem
– Exploitation of problem structure,pre-
processing,LP solver selection,etc.
Airline Schedule Planning
Cynthia Barnhart
Spring 2003
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 2
1.206J/16.77J/ESD.215J Airline
Schedule Planning,Multi-commodity
Flows
Outline
? Applications
? Problem Definition
? Formulations
? Solutions
? Results
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 3
Application I
? Package flow problem (express package
delivery operation)
– Shipments have specific origins and destinations
and must be routed over a transportation
network
– Each set of packages with a common origin-
destination pair is called a commodity
? Time windows (availability and delivery time)
associated with packages
– The objective might be to minimize total costs,
find a feasible flow,...
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 4
Application II
? Passenger mix problem
– Given a fixed schedule of flights,a fixed
fleet assignment and a set of customer
demands for air travel service on this
fleeted schedule,the airline's objective is to
maximize revenues by accommodating as
many high fare passengers as possible
– For some flights,demand exceeds seat
supply and passengers must be spilled to
other itineraries of either the same or
another airline
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 5
Application III
? Message routing problem
– In a telecommunications or computer
network,requirements exist for
transmission lines and message requests,or
commodities,
– The problem is to route the messages from
their origins to their respective destinations
at minimum cost
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 6
MCF Networks
? Set of nodes
– Each node associated with the supply of or
demand for commodities
? Set of arcs
– Cost per unit commodity flow
– Capacity limiting the total flow of all
commodities and/ or the flow of
individual commodities
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 7
MCF Commodity Definitions
? A commodity may originate at a subset of
nodes in the network and be destined for
another subset of nodes
? A commodity may originate at a single node
and be destined for a subset of the nodes
? A commodity may originate at a single node
and be destined for a single node
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 8
MCF Objectives
? Flow the commodities through the networks
from their respective origins to their
respective destinations at minimum cost
– Expressed as distance,money,time,etc.
? Ahuja,Magnanti and Orlin (1993)-- survey of
multi-commodity flow models and solution
procedures
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 9
MCF Problem Formulations --
Linear Programs
? Network flow problems
– Capacity constraints limit flow of individual
commodities
– Conservation of flow constraints ensure flow
balance for individual commodities
– Flow non-negativity constraints
? With side constraints
– Bundle constraints restrict total flow of ALL
commodities on an arc
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 10
MCF Constraint Matrix
Network flow
problem,
commodity k=1
Bundle constraints limiting total flow of all commodities to arc capacities
Network flow
problem,
commodity k=2
Network flow
problem,
commodity k=3
Network flow
problem,
commodity k=4
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 11
Alternative Formulations for O-D
Commodity Case
? Node-Arc Formulation
– Decision variables,flow of commodity k on each arc ij
? Path Formulation
– Decision variables,flow of commodity k on each path for
k
?,Tree” or,Sub-network” Formulation
– Define,super commodity,set of all (O-D) commodities
with the same origin o (or destination d)
– Decision variables,quantity of the super commodity k’
assigned to each,tree” or,sub-network” for k’
? Formulations are equivalent
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 12
Sample Network
Commodities
# o d quant
1 1 3 5
2 1 4 15
3 2 4 5
4 3 4 10
Arcs
i j cost capy
1 2 1 20
1 3 2 10
2 3 3 20
2 4 4 10
3 4 5 40
1
2
3
4
a
b
c
d
e
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 13
Notation
Parameters
? A,set of all network arcs
? K,set of all commodities
? N,set of all network nodes
? O(k) [D(k)],origin [destination]
node for commodity k
? cijk, per unit cost of
commodity k on arc ij
? uij, total capacity on arc ij
(assume uijk is unlimited for
each k and each ij)
? dk, total quantity of
commodity k
Decision Variables
? xijk, number of units
of commodity k
assigned to arc ij
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 14
Node-Arc Formulation
M i n i m i z e c x
ij
k
ij
k
kij
??
s ub j e c t t o
ot her w i s e
kDid
kOidxx
k
k
j
k
ji
j
k
ij
0
)( if
)( if
?
???
??? ??
, Co n s e r v a t i o n o f F l o w
x u i j A
ij
k
k
ij
? ? ? ?(,), B un dl e c o n s t r a i n t s
x i j A k K
ij
k
? ? ? ?0 (,),
, N o n n e ga t i v i t y c o n s t r a i n t s
k1 k2 k3 k4
a b c d e a b c d e a b c d e a b c d e RH S
1 1 1 = d 1
2 -1 1 1 = 0
3 -1 -1 1 = - d 1
4 -1 -1 = 0
1 1 1 = d 2
2 -1 1 1 = 0
3 -1 -1 1 = 0
4 -1 -1 = - d 2
1 1 1 = 0
2 -1 1 1 = d 3
3 -1 -1 1 = 0
4 -1 -1 = - d 3
1 1 1 = 0
2 -1 1 1 = 0
3 -1 -1 1 = d 4
4 -1 -1 = - d 4
a 1 1 1 1 ? u
a
b 1 1 1 1 ? u
b
c 1 1 1 1 ? u
c
d 1 1 1 1 ? u
d
e 1 1 1 1 ? u
e
c a
1
c b
1
c c
1
c d
1
c e
1
c a
2
c b
2
c c
2
c d
2
c e
2
c a
3
c b
3
c c
3
c d
3
c e
3
c a
4
c b
4
c c
4
c d
4
c e
4
x a
1
x b
1
x c
1
x d
1
x e
1
x a
2
x b
2
x c
2
x d
2
x e
2
x a
3
x b
3
x c
3
x d
3
x e
3
x a
4
x b
4
x c
4
x d
4
x e
4
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 15
Additional Notation
Parameters
? Pk,set of all paths for
commodity k,for all k
? 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
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 16
O/D Based Path Formulation
? ?
?k Pp
ppk
k
fCd
subject to
d f u i j Ak p ijp
p P
ij
k k
?
?
?? ? ? ?(,), Bundle constraints
f k Kp
p P k?
? ? ? ?1, Flow balance constraints
f p P k Kp k? ? ? ?0,,Non-neg,constraints
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a d 1 0 d 2 d 2 0 0 0 0 < = u a ??????? ?
a ?
b 0 d 1 0 0 d 2 0 0 0 < = u b ??
b
c d 1 0 d 2 0 0 d 3 0 0 < = u c ??
c
d 0 0 0 d 2 0 0 d 3 0 < = u d ??
d
e 0 0 d 2 0 d 2 d 3 0 d 4 < = u e ??
e
k = 1 1 1 = 1 ?
?
?
k = 2 1 1 1 = 1 ?
?
?
k = 3 1 1 = 1 ?
?
?
k = 4 1 = 1 ?
?
?
C o s t,
11
dC
12
dC
23
dC 24
dC
25
dC
36
dC
37
dC
38
dC
Va ri a b l e
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
Minimize
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 17
Additional Notation
Parameters
? S,set of source nodes
n?N for all commodities
? Qs,the set of all sub-
networks originating at s
? TCqs,total cost of sub-
network q originating at s
? ?pq, = 1 if path p is
contained in sub-network
q; and = 0 otherwise
Decision Variables
? Rqs, fraction of
total quantity of the
super commodity
originating at s
assigned to sub-
network q
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 18
S ub - n e t w o rk
o = 1 o = 2 o = 3 RHS D u a l
a d
1
+ d
2
d
1
+ d
2
d
1
d
2
d
2
0 0 0 0 < = u
a
?
a
?
b 0 0 d
2
d
1
d
1
d
1
+ d
2
0 0 0 < = u
b
?
b
c d
1
d
1
+ d
2
d
1
0 d
2
0 d
3
0 0 < = u
c
?
c
d d
2
0 0 d
2
0 0 0 d
3
0 < = u
d
?
d
e 0 d
2
d
2
0 d
2
d
2
d
3
0 d
4
< = u
e
?
e
o = 1 1 1 1 1 1 1 = 1 ?
?
?
o = 2 1 1 = 1 ?
?
?
o = 3 1 = 1 ?
?
?
C o s t, TC
1
1
TC
2
1
TC
3
1
TC
4
1
TC
5
1
TC
6
1
TC
1
2
TC
2
2
TC
1
3
Va ri a b l e R
1
1
R
2
1
R
3
1
R
4
1
R
5
1
R
6
1
R
1
2
R
2
2
R
1
3
Sub-network Formulation
q
s? Qq
k
qk Pp
q
pp RdC
s k
? ? ? ?
? ? ?
)( ? s
subject to
? ? ? ? ???
? ? ?s
ij
q
pq
sk Pp
p
ijk AjiuRd
s k
),()( s?????, Capacity Limits on Each Arc
R s s Sq
q Qs?
? ? ? ?1, Mass Balance Requirements
R s q Q s Sq s? ? ? ?0,,Nonnegative Path Flow Variables
Minimize
S
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 19
Linear MCF Problem Solution
? Obvious Solution
– LP Solver
? Difficulty
– Problem Size,(|N|=|Nodes|,|C|=|Commodities|,
|A|=|Arcs|)
? Node-arc formulation:
– Constraints,|N|*|C| + |A|
– Variables,|A|*|C|
? Path formulation:
– Constraints,|A| + |C|
– Variables,|Paths for ALL commodities|
? Sub-network formulation:
– Constraints,|A|+|Origins|
– Variables,|Combinations of Paths by Origin|
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 20
General MCF Solution Strategy
? Try to Decompose a Hard Problem Into a Set of
Easy Problems
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 21
MCF Solution Procedures I
? Partitioning Methods
– Exploit Network Structure to Speed Up Simplex
Matrix Computations
? Resource-Directive Decomposition
– Repeat until Optimal:
? Allocate Arc Capacity Among Commodities
? Find Optimal Flows Given Allocation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 22
MCF Solution Procedures II
? Price-Directive Decomposition
– Repeat until Optimal:
? Modify Flow Cost on Arc
? Ignore Bundle Constraints,Find Optimal Flows
14-May-10 1.224J/ESD.204J 23
Revisiting the Path
Formulation
MINIMIZE ? k ?K ? p?Pk dk cp fp
subject to,?p?Pk? k ?K dk fp?ijp ? uij ? ij?A
?p?P(k) fp = 1 ? k?K
fp? 0 ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 24
By-products of the Simplex
Algorithm,Dual Variable Values
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
Economic Interpretation
? ij, the value of an additional unit of capacity on arc ij
? k/dk, the minimal cost to send an additional unit of
commodity k through the network
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 25
Modified Costs
Definition,Modified cost for arc ij and
commodity k = cijk+?ij
Definition,Modified cost for path p and
commodity k = ?ij?A (cijk + ?ij )?ijp
14-May-10 1.224J/ESD.204J 26
Optimality Conditions for the Path Formulation
f*p and ?*ij,?*k are optimal for all k and all ij iff:
Primal feasibility is satisfied
1,?p?Pk ? k ?K dk f*p?ijp ? uij ? ij?A
2,?p?P(k) f*p = 1 ? k?K
3,f*p ? 0 ? p?Pk,? k?K
Complementary slackness is satisfied
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
2,?*k (?p? Pk f*p – 1) = 0,? k?K
Dual feasibility is satisfied (reduced cost is non-negative
for a minimization problem)
1,(dk cp + ? ij ?A dk?ij ?ijp ) - ?k = dk (? ij ?A (cijk + ?ij)
?ijp - ?k /dk ) ? 0,? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 27
Multi-commodity Flow
Optimality Conditions
? The price for an additional unit of capacity is 0
unless capacity is fully utilized
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
? A path p for commodity k is utilized only if its
“modified cost” (that is,?ij?A (cijk + ?*ij?ijp)) is
minimal,for all paths p?Pk
1,Reduced Costs all non-negative:
c’p = dk (? ij ?A (cijk + ?*ij) ?ijp - ?*k /dk ) ? 0,
? p? Pk,? k? K
2,f*p (?ij?A (cijk + ?*ij )?ijp - ?*k /dk ) = 0,
? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 28
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 29
RMP and Optimality Conditions
Consider f*p and ?*ij,?*k optimal for RMP,then
Primal feasibility is satisfied
1,?p?Pk ? k ?K dk f*p?ijp ? uij ? ij?A
2,?p?P(k) f*p = 1 ? k?K
3,f*p ? 0 ? p?Pk,? k?K
Complementary slackness is satisfied
1,?*ij(?p?Pk ? k ?K dk f*p?ijp - uij ) = 0,? ij?A
2,?*k (?p? Pk f*p – 1) = 0,? k?K
Dual feasibility is guaranteed (reduced cost is non-
negative) ONLY for a path p included in RMP
1,(dk cp + ? ij ?A dk?ij ?ijp ) - ?k = dk (? ij ?A (cijk +
?ij) ?ijp - ?k /dk ) ? 0,? p? Pk,? k? K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 30
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 31
Pricing Problem
? Given ?,?the optimal (non-negative) duals for
the current restricted master problem,?the
pricing problem,for each p? Pk,k? K is
min p? Pk (dk (? ij ?A (cijk + ?ij) ?ijp - ?k /dk )
Or,equivalently:
min p? Pk ? ij ?A (cijk + ?ij) ?ijp
?A shortest path problem for commodity k (with
modified arc costs)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 32
Example- Iteration 1
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 15 0 0 0 0 < = 2 0 ?
a
= 0 ?
b 0 5 0 0 15 0 0 0 < = 1 0 ?
b
= 0
c 5 0 15 0 0 5 0 0 < = 2 0 ?
c
= 0
d 0 0 0 15 0 0 5 0 < = 1 0 ?
d
= 0
e 0 0 15 0 15 5 0 10 < = 4 0 ?
e
= 0
k = 1 1 1 = 1 ?
?
= 1 0 ?
k = 2 1 1 1 = 1 ?
?
= 1 3 5 ?
k = 3 1 1 = 1 ?
?
= 2 0 ?
k = 4 1 = 1 ?
?
= 5 0 ?
C o s t,
20 10 135 75 105 40 20 50
Va ri a b l e
1
f
2
f
= 1
3
f = 1
4
f
5
f
6
f
7
f = 1
8
f = 1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 33
Example- Iteration 2
Pa t h
k = 1 k = 2 k = 3 k = 4 RHS D u a l
a 5 0 15 15 0 0 0 0 < = 2 0 ?
a
= 0 ?
b 0 5 0 0 15 0 0 0 < = 1 0 ?
b
= 2
c 5 0 15 0 0 5 0 0 < = 2 0 ?
c
= 0
d 0 0 0 15 0 0 5 0 < = 1 0 ?
d
= 4
e 0 0 15 0 15 5 0 10 < = 4 0 ?
e
= 0
k = 1 1 1 = 1 ?
?
= 2 0 ?
k = 2 1 1 1 = 1 ?
?
= 1 3 5 ?
k = 3 1 1 = 1 ?
?
= 4 0 ?
k = 4 1 = 1 ?
?
= 5 0 ?
C o s t,
20 10 135 75 105 40 20 50
Va ri a b l e
1
f
2
f
= 1
3
f = 1 / 3
4
f
= 1 / 3
5
f = 1 / 3
6
f
7
f = 1
8
f = 1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 34
MCF Optimality Conditions
? For each p?Pk,for each k,the reduced cost c?p:
– c?p ??(dk cp + ? ij ?A dk ?ij ?ijp ) - ?k = ?ij (dkcijk + dk?ij)?ijp -
?k = ?ij (cijk + ?ij)?ijp - ?k /dk ?0?
? where ?,?? are the optimal duals for the current restricted
master problem
– c?p ??0,?for each utilized path p implies
?ij (dkcijk + dk?ij) ?ijp = ?k
or equivalently,
?ij (cijk + ?ij) ?ijp = ?k/dk
– So if,minp?P(k) c?p = ?ij (cijk + ?ij) ?ijp* - ?k/dk ?0,?the
current solution to the restricted master problem is
optimal for the original problem
– If minp?P(k) c?p = ?ij (cijk + ?ij) ?ijp* - ?k/dk <?0,?add p* to
restricted master problem
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 35
Data Set? Data Set
? Constraint Matrix Size
N o d e s 807
L i n k s 1,3 6 3
c a p a c i t a t e d 292
u n c a p a c i t a t e d 1,0 7 1
O / D 1 7,5 3 9
# O r i g i n 136
I m p r o v e m e n t
r o w c o l u m n n e w _ r o w
N o d e _ A r c 1 4,1 5 5,3 3 6 2 3,9 0 5,6 5 7 -
P a t h 1 8,9 0 2 - 1 7,8 3 2
S u b - n e t w o r k 1,4 9 9 - 428
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 36
Computational Results
? Number of Nodes,807
? Number of Links,1,363
? Number of Commodities,17,539
? Computational Result (IBM RS6000,Model
370)
– Path Model,44 minutes
– Sub-network Model,< 1 minute
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 37
Conclusions I
? Choose your formulation carefully
– Trade-off memory requirements and solution time
– Sub-network formulation can be effective when
low level of congestion in the network
? Problem size often mandates use of combined
column and row generation
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Conclusions II
? Solution time is affected dramatically by
– The complexity of the pricing problem
– Exploitation of problem structure,pre-
processing,LP solver selection,etc.
