The path programming problem and a partial path relaxation
We introduce the class of path programming problems, which can be used to model many known optimization problems. A path programming problem can be formulated as a binary programming problem, for which the pricing problem can be modeled as a shortest path problem with resource constraints when column generation is used to solve its linear programming relaxation. Many optimization problems found in the literature belong to this class. We provide a framework for obtaining a partial path relaxation of a path programming problem. Like traditional path relaxations, the partial path relaxation allows the computational complexity of the pricing problem to be reduced, at the expense of a weaker linear programming bound. We demonstrate the versatility of this framework by providing different examples of partial path relaxations for a crew scheduling problem and vehicle routing problem.
|, , ,
|Econometric Institute Research Papers
|Erasmus School of Economics
Dollevoet, T., Pecin, D., & Spliet, R. (2020, June). The path programming problem and a partial path relaxation. Econometric Institute Research Papers. Retrieved from http://hdl.handle.net/1765/127709