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.

Path programming, Partial path relaxation, Shortest path problem with resource constraints, Column Generation
Econometric Institute Research Papers
Erasmus School of Economics

Dollevoet, T.A.B, 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