Subject Area
Industrial/Manufacturing Engineering
Abstract
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 formulations of the BPMP and FCNF. For the BPMP, this results in significantly faster solution times. For dense problem instances, the triples-based formulation of FCNF is found to produce better solutions than the node-arc formulation early in the branch-and-bound process. This observation leads to an effective hybrid method which combines the respective advantages of the smaller size of the triples formulation and the stronger linear programming relaxation of the node-arc formulation. In addition to empirical studies, the dissertation presents new theoretical results supporting the equivalence of the triples formulation to the node-arc and arc-path formulations.
The dissertation also proposes a multi-criteria Composite Index Method (CIM) to compare the performance of alternative integer programming formulations of an optimization problem. Using the CIM, the decision maker assigns weights to problem instance sizes and multiple performance measures based on their relative importance for the given application. The weighting scheme is used to produce a single number that measures the relative improvement of one alternative over the other and provides a method to select the most effective approach when neither one dominates the other when tested on different sizes of problem instances. The dissertation demonstrates a successful application of the CIM to evaluate a series of eleven techniques for improving the node-arc and triples formulations of the BPMP previously proposed in the literature.
Degree Date
Fall 12-17-2022
Document Type
Dissertation
Degree Name
Ph.D.
Department
Operations Research and Engineering Management
Advisor
Eli Olinick
Number of Pages
172
Format
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License
Recommended Citation
Bai, Yulan, "Compact Formulation Of Multicommodity Network Flows With Applications To The Backhaul Profit Maximization Problem And Fixed Charge Network Flow Problem" (2022). Operations Research and Engineering Management Theses and Dissertations. 15.
https://scholar.smu.edu/engineering_managment_etds/15
