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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
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 rocedures 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
MCF Problem formulations Linear programs Network flow problems Capacity constraints limit flow of individua 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 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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
MCF COnstraint matrix Network flc problem commodity k=1 Network flow problem, commodity k=2 Network flow problem commodity k=3 Network flow ommodity k=4 Bundle constraints limiting total flow of all commodities to arc capacities 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 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