Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles

DOI10.1016/J.COR.2013.01.002MaRDI QIDQ336550zbMATH OpenOpenAlexFDO

Authors Mohamed Haouari, Mehdi Mrad, Nelson Maculan

Publication date 10 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2013.01.002

zbMATH Keywords

reformulation-linearization techniqueconnected subgraphsshortest paths with negative cycles

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
• Integer programming formulations for the elementary shortest path problem
• New formulations for the elementary shortest-path problem visiting a given set of nodes
• Exact methods for solving the elementary shortest and longest path problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A note on two problems in connexion with graphs
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Column Generation
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Integer Programming Formulation of Traveling Salesman Problems
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Resource constrained shortest path problems in path planning for fleet management
• Solving VRPTWs with constraint programming based column generation
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm
• The Floyd-Warshall algorithm on graphs with negative cycles
• The Steiner tree problem
• Tight compact models and comparative analysis for the prize collecting Steiner tree problem
• Vehicle routing problem with elementary shortest path based column generation

Cited in

(8)

• Theory and application of reciprocal transformation of “path problem” and “time float problem”
• Spatial optimization of multiple area land acquisition
• MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Allocating nodes to hubs for minimizing the hubs processing resources: A case study
• Tight lower bounds for the traveling salesman problem with draft limits
• Integer programming formulations for the elementary shortest path problem
• Small-\(m\) method for detecting all longest paths

This page was built for publication: Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q336550)