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.

Additional Metadata
Keywords Path programming, Partial path relaxation, Shortest path problem with resource constraints, Column Generation
Persistent URL hdl.handle.net/1765/129423
Citation
Dollevoet, T.A.B, Pecin, D., & Spliet, R. (2020). The Path Programming Problem and a Partial Path Relaxation. Retrieved from http://hdl.handle.net/1765/129423