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.002zbMath1348.05138OpenAlexW2100195928MaRDI QIDQ336550

Mehdi Mrad, Mohamed Haouari, Nelson F. 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) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

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

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• 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
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• Solving VRPTWs with constraint programming based column generation
• Resource constrained shortest path problems in path planning for fleet management
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Tight compact models and comparative analysis for the prize collecting Steiner tree problem
• Vehicle routing problem with elementary shortest path based column generation
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Integer Programming Formulation of Traveling Salesman Problems
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Column Generation
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs