Resource-robust valid inequalities for set covering and set partitioning models

Ymro Hoogendoorn and Kevin Dalmeijer

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

Abstract: For a variety of routing and scheduling problems in aviation, shipping, rail, and road transportation, the state-of-the-art solution approach is to model the prob- lem as a set covering type problem and to use a branch-price-and-cut algorithm to solve it. The pricing problem typically takes the form of a Shortest Path Problem with Resource Constraints (SPPRC). In this context, valid inequalities are known to be `robust' if adding them does not complicate the pricing problem, and `non- robust' otherwise. In this paper, we introduce `resource-robust' as a new category of valid inequalities between robust and non-robust that can still be incorporated without changing the structure of the pricing problem, but only if the SPPRC includes specic resources. Elementarity-robust and ng-robust are introduced as widely applicable special cases that rely on the resources that ensure elementary routes and ng-routes, respectively, and practical considerations are discussed. The use of resource-robust valid inequalities is demonstrated with an application to the Capacitated Vehicle Routing Problem. Computational experiments show that re- placing robust valid inequalities by ng-robust valid inequalities may result in better lower bounds, a reduction in the number of nodes in the search tree, and a decrease in solution time.

Keywords: Resource-Robust; Valid Inequalities; Branch-Price-and-Cut. (search for similar items in EconPapers)
Pages: 54
Date: 2021-01-12
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/134553/EI2020-08-herziene-versie.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:134553

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 ).