Optimization Online


Integer programming formulations for the elementary shortest path problem

Leonardo Taccari (leonardo.taccari***at***polimi.it)

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

Keywords: Integer programming, elementary shortest path, longest path, subtour elimination constraints

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Network Optimization

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

Download: [PDF]

Entry Submitted: 09/26/2014
Entry Accepted: 09/26/2014
Entry Last Modified: 02/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society