Integer programming formulations for the elementary shortest path problem

Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this paper, several integer programming formulations for the ESPP are compared. We present analytical results based on a polyhedral study of the formulations, and computational experiments where we compare their linear programming relaxation bounds and their behavior within a branch-and-cut framework. The computational results show that a formulation with dynamically generated cutset inequalities is the most effective.

Citation

Taccari, Leonardo. "Integer programming formulations for the elementary shortest path problem." European Journal of Operational Research (2016). http://dx.doi.org/10.1016/j.ejor.2016.01.003

Article

Download

View Integer programming formulations for the elementary shortest path problem