International Transactions in Operational Research · 2009 · 17 citations · 4 references
Natural SciencesComputer ScienceAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationDirected Acyclic GraphsDiscrete OptimizationGraph AlgorithmsInteger ProgrammingShortest Path AlgorithmsGraph RelaxationInteger Linear ProgrammingLinear Integer OptimizationLinear Programming RelaxationsNetwork Flow ProblemsShortest Path ProblemsTraveling Salesman ProblemTraveling Salesperson Problem
Abstract In this paper, we are interested in the shortest path problem between two specified vertices in digraphs containing negative cycles. We study two integer linear formulations and their linear relaxations. A first formulation, close in spirit to a classical formulation of the traveling salesman problem, requires an exponential number of constraints. We study a second formulation that requires a polynomial number of constraints and, as confirmed by computational experiments, its linear relaxation is significantly sharper. From the second formulation we propose a family of linear relaxations with fewer variables than the classical linear one.
4
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Richard Bellman · Quarterly of Applied Mathematics · 1958 · 2.7K citations · Full text