Alternative Formulations for o-D Commodity case Node-Arc Formulation Decision variables: flow of commodity k on each arc ii 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 as signed to each“ tree or“sub- network>, for k Formulations are equivalent 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
Sample network a 4 b 3 Arcs Commodities 11 cost capy # quant 20 11 132 10 21415 20 324 10 434 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
Notation Parameters Decision variables A: set of all network arcs number of units K: set of all commodities of commodity k N: set of all network nodes O(k)D(k]: origin [ destination assigned to arc 1j node for commodity k k per unit cost of commodity k on arc ij total capacity on arc 1 assume u. k is unlimited for each k and each ij dk: total quantity of commodity k 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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 • cij k : per unit cost of commodity k on arc ij • uij : total capacity on arc ij (assume uij k is unlimited for each k and each ij) • dk : total quantity of commodity k Decision Variables • xij k : number of units of commodity k assigned to arc ij
Node- Arc Formulation Minimize ∑∑cx subject to fi∈O(k) lkfi∈D(k) Conservation of Flow 0 other ∑x≤nY(,∈ Bundle constraints x≥0V(,j)∈A,k∈K Nonnegativity constraint ■RHs 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 14 Node-Arc Formulation Minimize c x ij k ij k ij k subject to otherwise d i D k x x d i O k k k j k j i j k i j 0 if ( ) if ( ) = = − − = : Conservation of Flow xij u i j A k k ij ( , ) : Bundle constraints xij i j A k K k 0 ( , ) , : Nonnegativity constraints k1 k2 k3 k4 a b c d e a b c d e a b c d e a b c d e RHS 1 1 1 = d1 2 -1 1 1 = 0 3 -1 -1 1 = -d1 4 -1 -1 = 0 1 1 1 = d2 2 -1 1 1 = 0 3 -1 -1 1 = 0 4 -1 -1 = -d2 1 1 1 = 0 2 -1 1 1 = d3 3 -1 -1 1 = 0 4 -1 -1 = -d3 1 1 1 = 0 2 -1 1 1 = 0 3 -1 -1 1 = d4 4 -1 -1 = -d4 a 1 1 1 1 ua b 1 1 1 1 ub c 1 1 1 1 uc d 1 1 1 1 ud e 1 1 1 1 ue ca 1 cb 1 cc 1 cd 1 ce 1 ca 2 cb 2 cc 2 cd 2 ce 2 ca 3 cb 3 cc 3 cd 3 ce 3 ca 4 cb 4 cc 4 cd 4 ce 4 xa 1 xb 1 xc 1 xd 1 xe 1 xa 2 xb 2 xc 2 xd 2 xe 2 xa 3 xb 3 xc 3 xd 3 xe 3 xa 4 xb 4 xc 4 xd 4 xe 4
Additional notation Parameters Decision variables ph: set of all paths for f: fraction of total commodity k, for all k p: per unit cost of quantity of commodity k on path p commoditv k aSSigned to pa 1l∈p 8i P: =1 if path p contains arc ij; and =0 otherwise 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 15 Additional Notation Parameters • P k : set of all paths for commodity k, for all k • cp : per unit cost of commodity k on path p = ij p cij k • ij p : = 1 if path p contains arc ij; and = 0 otherwise Decision Variables • fp : fraction of total quantity of commodity k assigned to path p