Engineering Commons^™

Compact Formulation Of Multicommodity Network Flows With Applications To The Backhaul Profit Maximization Problem And Fixed Charge Network Flow Problem, Yulan Bai

Operations Research and Engineering Management Theses and Dissertations

The triples formulation is a compact formulation of multicommodity network flow problems that provides a different representation of flow than the traditional and widely used node-arc and arc-path approaches. In the literature, the triples formulation has been applied successfully to the maximum concurrent flow problem and to a network optimization problem with piecewise linear convex costs. This dissertation applies the triples formulation to the backhaul profit maximization problem (BPMP) and the fixed charge network flow problem (FCNF). It is shown that the triples representation of multicommodity flow significantly reduces the number of variables and constraints in the mixed integer programming …