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
hdl.handle.net/1765/127709
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