  


Integer programming formulations for the elementary shortest path problem
Leonardo Taccari (leonardo.taccaripolimi.it) Abstract: Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimumcost 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 NPhard. 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 branchandcut 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  