Valid inequalities for the k-Color Shortest Path Problem

Rafael Castro de Andrade, Emanuel Elias Silva Castelo and Rommel Dias Saraiva

European Journal of Operational Research, 2024, vol. 315, issue 2, 499-510

Abstract: Given a digraph D=(V,A) where each arc (i,j)∈A has a cost dij∈R+ and a color c(i,j), a positive integer k, and vertices s,t∈V, the k-Color Shortest Path Problem consists in finding a path from s to t of minimum cost while using at most k distinct arc colors. We propose valid inequalities for the problem that proved to strengthen the linear relaxation of an existing Integer Linear Programming formulation for the problem. One exponential set of valid inequalities defines a new formulation for the problem that is solved by using a branch-and-cut algorithm. We introduce more challenging instances for the problem and present numerical experiments for both the benchmark and the new instances. Finally, we evaluate the individual and the collective use of the valid inequalities. Computational results for the proposed ideas and for existing solution approaches for the problem showed the effectiveness of the new inequalities in handling the new instances, both in terms of execution times and improvement of the linear relaxed solutions.

Keywords: Combinatorial optimization; k-color shortest path problem; Valid inequalities (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723009487
Full text for ScienceDirect subscribers only

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:eee:ejores:v:315:y:2024:i:2:p:499-510

DOI: 10.1016/j.ejor.2023.12.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().