Yulan Bai: Compact Formulations of Network Flow Problems

The triples formulation is a compact formulation of multicommodity network flow that provides a different representation of flow than the traditional, widely used node-arc and arc-path formulations. In the literature, the triples formulation has been applied successfully to the minimum cost multicommodity flow problem with piecewise linear cost functions in complete, undirected graphs, and the maximum concurrent flow problem. In this study we show that the triples formulation of a freight logistics application known as the backhaul profit maximization problem (BPMP) can be solved significantly faster than the existing model in the literature, which is based on the node-arc model. We also demonstrate the effectiveness of applying the triples formulation to the uncapacitated, single-commodity, fixed charge network flow problem.