O/D Based Path Formulation Minimize subject to ∑dkfn V(i,j)∈A Bundle constrants Vk K Flow balance constraints Non-neg constraints Path k=1 k=2 k=3 k=4 RHS Dual 0 < ua abcde d 0 0 000d 0000 < uc 0 000—1 0 d00d 0 k=1 k=2 k=3 =1 Cost Variable 2/21/2021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 16 O/D Based Path Formulation k p P k p p k d C f subject to d k f p ij u i j A p p P ij k k ( , ) : Bundle constraints f p k K p P k = 1 : Flow balance constraints f p p P k K k 0 , : Non-neg. constraints Path k=1 k=2 k=3 k=4 RHS Dual a d1 0 d2 d2 0 0 0 0 <= ua −a b 0 d1 0 0 d2 0 0 0 <= ub −b c d1 0 d2 0 0 d3 0 0 <= uc −c d 0 0 0 d2 0 0 d3 0 <= ud −d e 0 0 d2 0 d2 d3 0 d4 <= ue −e k=1 1 1 = 1 k=2 1 1 1 = 1 k=3 1 1 = 1 k=4 1 = 1 Cost. C1 d1 C2 d1 C3 d2 C4 d2 C5 d2 C6 d3 C7 d3 C8 d3 Variable 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f Minimize
Additional notation Parameters Decision variables S: set of source nodes nen for all commodities Rs: fraction of ·O: the set of all sub total quantity of the networks originating at s super commodity TC S: total cost of sub originating at s network q originating at s q 1 if path p is assigned to sub contained in sub-network network q: and =0 otherwise q 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 17 Additional Notation Parameters • S: set of source nodes nN for all commodities • Qs : the set of all subnetworks originating at s • TCq s : total cost of subnetwork q originating at s • p q : = 1 if path p is contained in sub-network q; and = 0 otherwise Decision Variables • Rq s : fraction of total quantity of the super commodity originating at s assigned to subnetwork q
Sub-network formulation Sa∈O3k abject te ∑∑(∑∑4)R;日≤4nY(i,j)∈A Capacity Limits on Each Arc ∈Qk ∑R Mass balance requirements R20q∈Q,s∈S Nonnegative path flow variables Sub-network o=2 0=3 RHS Dual d1+ d2 d1+ d2 d d2 0 0 b d1d1+d20 < 0 0 e 0 0 <=u 1 Cost TC: TC TO Variable RI R2 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 18 Sub- network o=1 o=2 o=3 RHS Dual a d1+ d2 d1+ d2 d1 d2 d2 0 0 0 0 <= ua a b 0 0 d2 d1 d1 d1+ d2 0 0 0 <= ub b c d1 d1+ d2 d1 0 d2 0 d3 0 0 <= uc c d d2 0 0 d2 0 0 0 d3 0 <= ud d e 0 d2 d2 0 d2 d2 d3 0 d4 <= ue e o=1 1 1 1 1 1 1 = 1 o=2 1 1 = 1 o=3 1 = 1 Cost. T C1 1 TC2 1 TC3 1 TC4 1 T C5 1 T C6 1 T C1 2 T C2 2 T C1 3 Variable R1 1 R2 1 R3 1 R4 1 R5 1 R6 1 R1 2 R2 2 R1 3 Sub-network Formulation q s q Q k k q p P q C p p d R s k ( ) s subject to s ij q Q q q p k s p P p dk ij R u i j A s k ( ) ( , ) s : Capacity Limits on Each Arc R s s S q q Q s =1 : Mass Balance Requirements R s q Q s S q s 0 , : Nonnegative Path Flow Variables Minimize S
Linear mcf problem solution Obvious solution LP Solver Difficulty Problem Size:(N =Nodes,C=Commodities I A=Arcs D) Node-arc formulation: Constraints: NC+A Variables: A*C Path formulat Constraints:A|+C Variables: Paths for ALL commodities Sub-network formulation Constraints: A|+ Origins I Variables: Combinations of Paths by Origin 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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|
General MCF Solution Strategy Try to Decompose a hard Problem Into a Set of Easy Problems 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 20 General MCF Solution Strategy • Try to Decompose a Hard Problem Into a Set of Easy Problems