Compact vs. exponential-size LP relaxations

DOI10.1016/S0167-6377(01)00106-7zbMath1027.90059MaRDI QIDQ1612003

Robert D. Carr, Giuseppe Lancia

Publication date: 28 August 2002

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

traveling salesman problemseparationinteger programlinear programming relaxationscompact optimization

Mathematics Subject Classification ID

Integer programming (90C10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ New formulations of the multiple sequence alignment problem ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ Learning to classify with missing and corrupted features ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology ⋮ An effective compact formulation of the max cut problem on sparse graphs ⋮ A branch-and-cut algorithm for multiple sequence alignment

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• Optimum Communication Spanning Trees
• Exact algorithms for minimum routing cost trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees