Template-Type: ReDIF-Paper 1.0
Author-Name: Dollevoet, T.A.B.
Author-Name-Last: Dollevoet
Author-Name-First: Twan
Author-Name: Pecin, D.
Author-Name-Last: Pecin
Author-Name-First: Diego
Author-Name: Spliet, R.
Author-Name-Last: Spliet
Author-Name-First: Remy
Title: The path programming problem and a partial path relaxation
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.
Length: 29
Creation-Date: 2020-06-01
File-URL: https://repub.eur.nl/pub/127709/EI-2020-04_DollevoetPecinSpliet.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI-2020-04
Keywords: Path programming, Partial path relaxation, Shortest path problem with resource constraints, Column Generation
Handle: RePEc:ems:eureir:127709