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
– Computational results
– Integer multi-commodity network flow problems
– Integer multi-commodity network flow solutions
? Branch-and-price,combination of branch-and-bound and
column generation
– 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 ? (non-negative) and ?k (unrestricted),
the optimal 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
LP Computational Experiment
? Test effect of adding most negative
reduced cost column for each
commodity vs,adding several negative
reduced cost columns for each
commodity
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Generating Several Columns Per
Commodity
? Select any basic column (fp has reduced cost
= 0) for some path p and commodity k,call it
the key(k)
? Add all simple paths representing symmetric
difference between most negative reduced
cost path and key(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Example
key(k)
p1- most negative reduced cost path for k
Add to LP:
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
LP Solution,
One Path per Commodity
p rob lem iteration s co lu m n s tim e ( sec)
1 3747 9125 240
2 3572 9414 246
3 3772 10119 268
4 3663 10101 289
5 10128 10624 325
6 8509 27041 1289
7 9625 29339 1332
8 7135 22407 842
9 9500 30132 1369
10 7498 23571 833
301 nodes,497 arcs,1320 commodities.
Times are on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
LP Solution,
All Simple Paths for Each Commodity
p rob lem itera tio n s colu m n s tim e ( sec)
1 2455 8855 162
2 2690 10519 199
3 2694 10617 224
4 2511 10496 218
5 2706 11179 234
6 4391 25183 662
7 4208 23880 607
8 3237 17587 398
9 4191 20472 501
10 3633 21926 420
301 nodes,497 arcs,1320 commodities.
Times are on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Integer Multi-Commodity
Network Flows
? Consider the modified multi-commodity
network flow problem:
– Added integrality restriction that each
commodity must be assigned to exactly
one path
? fp? (0.1),? p ? Pk
–Solution procedure,branch-and-
bound,specialized to handle large-
scale problems
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Integer Multicommodity Flows,
Problem 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,1) ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Branch-and-Bound,A Solution
Approach for Binary Integer
Programs
f1 = 1
All possible solutions at leaf
nodes of tree (2n solutions,where
n is the number of variables)
f2 = 0 f2 = 1
f1 = 0
f2 = 1 f2 = 0
f3 = 1 f3 = 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
Branch-and-Bound,A
Solution Approach for Binary
Integer Programs
? Branch-and-Bound is a smart enumeration
strategy:
– With branching,all possible solutions (e.g.,2number
of path for all commodities) are enumerated
– With bounding,only a (usually) small subset of
possible solutions are evaluated before a provably
optimal solution is found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
Bounding,The Linear
Programming (LP) Relaxation
? Consider the linear path-based MCF problem
formulation
– Objective is to minimize
? The LP relaxation replaces
fp? 0,1
with
1 ? fp ? 0
? Let zLP* represent the optimal LP solution and let zIP*
represent the optimal IP solution
zLP* ? zIP*
– LP’s provide a bound on the lowest possible value of the
optimal integer solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Branching
? Consider an IP with binary restrictions on all
variables,denoted P(1)
? Let LP(1) denote the linear programming relaxation of
P(1) and let x*(1) denote the optimal solution to LP(1)
? If there is no variable with fractional value in x*(1),
x*(1) solves (is optimal for) P(1)
? If there is at least one variable with fractional value in
x*(1),call it xl*(1),then any optimal solution for P(1)
has xl*(1)=0 or xl*(1)=1
– Left branch,xl*(1)=0
– Right branch,xl*(1)=1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
A Pictorial View
feasible IP
feasible LP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Relationship between Bound and
Tree Depth
? Let x*(1) be the optimal solution to LP(1) with at
least one fractional variable xl*(1)
? Let the optimal solution value for LP(1) be denoted
z*(1)
? Let LP(2) = LP(1) + [xl*(1) = 0 or xl*(1) = 1]
? Let the optimal solution value for LP(2) be denoted
z*(2)
? Then
z*(1)?? z*(2)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 50
Tree Pruning
x1 = 1 x1=0
x2=1 x2=1 x2=0
x3=1 x3=0
Incumbent,
Current best
feasible (IP)
solution value = zIP
If z*(LP(2))?? zIP,PRUNE (FATHOM) tree at node 2
(solutions on the LHS of tree cannot be optimal,
1/2 of the solutions (nodes) do not need to be
evaluated!)
1
5
2 3
74 6
x2=0
x3=0 x3=1
If z*(LP(2)) ?is integral,PRUNE tree at node 2
(solutions in sub-tree at node 2 cannot be better.)
If LP(2)?is infeasible,PRUNE tree at node 2
(solutions in sub-tree at node 2 cannot be feasible.)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Branch-and-Bound Algorithm
Beginning with rootnode (minimization):
? Bound,
– Solve the current LP with this and all restrictions along
the (back) path to the rootnode enforced
? Prune:
– If optimal LP value is greater than or equal to the
incumbent solution,Prune
– If LP is infeasible,Prune
– If LP is integral,Prune and update incumbent solution
? Branch:
– Set some variable to an integer value
? Repeat until all nodes pruned
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
Branch-and-Price Solution
Approach
? Branch-and-bound tailored to solve large-
scale integer programs
? Bounding
– Solve LP using column generation at each node
of the branch-and-bound tree
? Branching
– New columns might have to be generated to find
an optimal solution to the constrained problem
– Want to design the branching decision so that the
algorithm for the pricing is unchanged as the
branch-and-bound tree is processed
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Example Revisited
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 54
Branch-and-Price,Branching and
Compatibility with the Pricing Problem
? Branching decision for commodity k,fp = 1:
– No pricing problem solution is necessary
– All other variables for k are removed from the
model
? Branching decision for commodity k,fp = 0,
– The solution to the pricing problem (a shortest
path problem) CANNOT generate path p as the
shortest path,must instead find the next shortest
path
– In general,at nodes of depth l in the branch-and-
bound tree,the pricing problem must potentially
generate the kth shortest path
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
An Alternative Branching Idea,
Branch on Small Decisions
? Consider commodity k whose flow is split
? Assume k takes 2 paths,p1 and p2
? Let d be the divergence node
p1o(k)
d(k)p2
d
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
Divergence Node
? Let a1 be the arc out of d on p1 and a2 be the arc
out of d on p2
? A(d) = {a1,a2,a3,a4},A(d,a1) = {a1,a3},A(d,a2)
= {a2,a4}
d a2
a4
a1
a3
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
Branching Rule
? Create two branches,one where
? And the other with
x ijk
ij A d a?
? ?
(,)1
0
x ijk
ij A d a?
? ?
(,)2
0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Branch-and-Bound Results,
Conventional Branching Rule
? Eight telecommunications test problems
– 50 nodes,130 arcs,585 commodities
? Computational experiment on an IBM
RS6000/590
? For each of the eight test problems,run time
of 3600 seconds
– No feasible solution was found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 59
Branch-and-Bound Results,Our
New Branching Rule
proble m c olu mns nodes g a p ti me ( sec )
1 1119 139869 0.14% 3600
2 1182 138979 0.5% 3600
3 1370 126955 1.5% 3600
4 1457 128489 2.7% 3600
5 1606 121374 1.5% 3600
6 1920 102360 1.7% 3600
7 2142 96483 5.0% 3600
8 2180 96484 13.0% 3600
All test problems have 50 nodes,130 arcs,585 commodities.
Run times on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 60
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 61
Conclusions II
? Solution time is affected dramatically by
– The complexity of the pricing problem
– Exploitation of problem structure,pre-
processing,LP solver selection,etc.
? Branching strategy should preserve the
structure of the pricing problem
– Branch on,small” decisions,not the variables in
the column generation formulation
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
– Computational results
– Integer multi-commodity network flow problems
– Integer multi-commodity network flow solutions
? Branch-and-price,combination of branch-and-bound and
column generation
– 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 ? (non-negative) and ?k (unrestricted),
the optimal 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
LP Computational Experiment
? Test effect of adding most negative
reduced cost column for each
commodity vs,adding several negative
reduced cost columns for each
commodity
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 38
Generating Several Columns Per
Commodity
? Select any basic column (fp has reduced cost
= 0) for some path p and commodity k,call it
the key(k)
? Add all simple paths representing symmetric
difference between most negative reduced
cost path and key(k)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 39
Example
key(k)
p1- most negative reduced cost path for k
Add to LP:
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 40
LP Solution,
One Path per Commodity
p rob lem iteration s co lu m n s tim e ( sec)
1 3747 9125 240
2 3572 9414 246
3 3772 10119 268
4 3663 10101 289
5 10128 10624 325
6 8509 27041 1289
7 9625 29339 1332
8 7135 22407 842
9 9500 30132 1369
10 7498 23571 833
301 nodes,497 arcs,1320 commodities.
Times are on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 41
LP Solution,
All Simple Paths for Each Commodity
p rob lem itera tio n s colu m n s tim e ( sec)
1 2455 8855 162
2 2690 10519 199
3 2694 10617 224
4 2511 10496 218
5 2706 11179 234
6 4391 25183 662
7 4208 23880 607
8 3237 17587 398
9 4191 20472 501
10 3633 21926 420
301 nodes,497 arcs,1320 commodities.
Times are on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 42
Integer Multi-Commodity
Network Flows
? Consider the modified multi-commodity
network flow problem:
– Added integrality restriction that each
commodity must be assigned to exactly
one path
? fp? (0.1),? p ? Pk
–Solution procedure,branch-and-
bound,specialized to handle large-
scale problems
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 43
Integer Multicommodity Flows,
Problem 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,1) ? p?Pk,? k?K
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 44
Branch-and-Bound,A Solution
Approach for Binary Integer
Programs
f1 = 1
All possible solutions at leaf
nodes of tree (2n solutions,where
n is the number of variables)
f2 = 0 f2 = 1
f1 = 0
f2 = 1 f2 = 0
f3 = 1 f3 = 0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 45
Branch-and-Bound,A
Solution Approach for Binary
Integer Programs
? Branch-and-Bound is a smart enumeration
strategy:
– With branching,all possible solutions (e.g.,2number
of path for all commodities) are enumerated
– With bounding,only a (usually) small subset of
possible solutions are evaluated before a provably
optimal solution is found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 46
Bounding,The Linear
Programming (LP) Relaxation
? Consider the linear path-based MCF problem
formulation
– Objective is to minimize
? The LP relaxation replaces
fp? 0,1
with
1 ? fp ? 0
? Let zLP* represent the optimal LP solution and let zIP*
represent the optimal IP solution
zLP* ? zIP*
– LP’s provide a bound on the lowest possible value of the
optimal integer solution
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 47
Branching
? Consider an IP with binary restrictions on all
variables,denoted P(1)
? Let LP(1) denote the linear programming relaxation of
P(1) and let x*(1) denote the optimal solution to LP(1)
? If there is no variable with fractional value in x*(1),
x*(1) solves (is optimal for) P(1)
? If there is at least one variable with fractional value in
x*(1),call it xl*(1),then any optimal solution for P(1)
has xl*(1)=0 or xl*(1)=1
– Left branch,xl*(1)=0
– Right branch,xl*(1)=1
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 48
A Pictorial View
feasible IP
feasible LP
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 49
Relationship between Bound and
Tree Depth
? Let x*(1) be the optimal solution to LP(1) with at
least one fractional variable xl*(1)
? Let the optimal solution value for LP(1) be denoted
z*(1)
? Let LP(2) = LP(1) + [xl*(1) = 0 or xl*(1) = 1]
? Let the optimal solution value for LP(2) be denoted
z*(2)
? Then
z*(1)?? z*(2)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 50
Tree Pruning
x1 = 1 x1=0
x2=1 x2=1 x2=0
x3=1 x3=0
Incumbent,
Current best
feasible (IP)
solution value = zIP
If z*(LP(2))?? zIP,PRUNE (FATHOM) tree at node 2
(solutions on the LHS of tree cannot be optimal,
1/2 of the solutions (nodes) do not need to be
evaluated!)
1
5
2 3
74 6
x2=0
x3=0 x3=1
If z*(LP(2)) ?is integral,PRUNE tree at node 2
(solutions in sub-tree at node 2 cannot be better.)
If LP(2)?is infeasible,PRUNE tree at node 2
(solutions in sub-tree at node 2 cannot be feasible.)
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 51
Branch-and-Bound Algorithm
Beginning with rootnode (minimization):
? Bound,
– Solve the current LP with this and all restrictions along
the (back) path to the rootnode enforced
? Prune:
– If optimal LP value is greater than or equal to the
incumbent solution,Prune
– If LP is infeasible,Prune
– If LP is integral,Prune and update incumbent solution
? Branch:
– Set some variable to an integer value
? Repeat until all nodes pruned
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 52
Branch-and-Price Solution
Approach
? Branch-and-bound tailored to solve large-
scale integer programs
? Bounding
– Solve LP using column generation at each node
of the branch-and-bound tree
? Branching
– New columns might have to be generated to find
an optimal solution to the constrained problem
– Want to design the branching decision so that the
algorithm for the pricing is unchanged as the
branch-and-bound tree is processed
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 53
Example Revisited
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 54
Branch-and-Price,Branching and
Compatibility with the Pricing Problem
? Branching decision for commodity k,fp = 1:
– No pricing problem solution is necessary
– All other variables for k are removed from the
model
? Branching decision for commodity k,fp = 0,
– The solution to the pricing problem (a shortest
path problem) CANNOT generate path p as the
shortest path,must instead find the next shortest
path
– In general,at nodes of depth l in the branch-and-
bound tree,the pricing problem must potentially
generate the kth shortest path
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 55
An Alternative Branching Idea,
Branch on Small Decisions
? Consider commodity k whose flow is split
? Assume k takes 2 paths,p1 and p2
? Let d be the divergence node
p1o(k)
d(k)p2
d
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 56
Divergence Node
? Let a1 be the arc out of d on p1 and a2 be the arc
out of d on p2
? A(d) = {a1,a2,a3,a4},A(d,a1) = {a1,a3},A(d,a2)
= {a2,a4}
d a2
a4
a1
a3
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 57
Branching Rule
? Create two branches,one where
? And the other with
x ijk
ij A d a?
? ?
(,)1
0
x ijk
ij A d a?
? ?
(,)2
0
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 58
Branch-and-Bound Results,
Conventional Branching Rule
? Eight telecommunications test problems
– 50 nodes,130 arcs,585 commodities
? Computational experiment on an IBM
RS6000/590
? For each of the eight test problems,run time
of 3600 seconds
– No feasible solution was found
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 59
Branch-and-Bound Results,Our
New Branching Rule
proble m c olu mns nodes g a p ti me ( sec )
1 1119 139869 0.14% 3600
2 1182 138979 0.5% 3600
3 1370 126955 1.5% 3600
4 1457 128489 2.7% 3600
5 1606 121374 1.5% 3600
6 1920 102360 1.7% 3600
7 2142 96483 5.0% 3600
8 2180 96484 13.0% 3600
All test problems have 50 nodes,130 arcs,585 commodities.
Run times on an IBM RS6000/590.
5/14/2010 Barnhart 1.206J/16.77J/ESD.215J 60
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 61
Conclusions II
? Solution time is affected dramatically by
– The complexity of the pricing problem
– Exploitation of problem structure,pre-
processing,LP solver selection,etc.
? Branching strategy should preserve the
structure of the pricing problem
– Branch on,small” decisions,not the variables in
the column generation formulation
