The path programming problem and a partial path relaxation

Twan Dollevoet, Diego Pecin and Remy Spliet

No EI-2020-04, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: 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.

Keywords: Path programming; Partial path relaxation; Shortest path problem with resource constraints; Column Generation (search for similar items in EconPapers)
Pages: 29
Date: 2020-06-01
New Economics Papers: this item is included in nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/127709/EI-2020-04_DollevoetPecinSpliet.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:127709

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).