Compact vs. exponential-size LP relaxations
type: Item
instance of: scholarly article
title: Compact vs. exponential-size LP relaxations
zbMATH Open document ID: 1027.90059
DOI: 10.1016/S0167-6377(01)00106-7
author: Robert D. Carr
author: Giuseppe Lancia
published in: Operations Research Letters
publication date: 2002-08-28T00:00:00Z
review text: The authors illustrate by means of examples a technique for formulating compact (polynomial-size) linear programming relaxations in place of exponential-size models requiring separation algorithms. They state the equivalence of compact separation and compact optimization. They also introduce a new formulation for the traveling salesman problem whose relaxation is equivalent to subtour elimination relaxation.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 1790725
zbMATH Keywords: integer program
zbMATH Keywords: separation
zbMATH Keywords: compact optimization
zbMATH Keywords: linear programming relaxations
zbMATH Keywords: traveling salesman problem
MaRDI profile type: Publication
cites work: Q3056948
cites work: Q4371290
cites work: Exact algorithms for minimum routing cost trees
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Optimum Communication Spanning Trees
cites work: Using separation algorithms to generate mixed integer model reformulations
cites work: Q4040221
cites work: A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
cites work: Expressing combinatorial optimization problems by linear programs
description: scientific article; zbMATH DE number 1790725