Compact vs. Exponential-Size LP Relaxations

Carr, R.D. ; Lancia, G.

Sandia National Laboratories

关键词: Calculation Methods;    Optimization;    Algorithms;    Relaxation;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/764803
RP-ID  :  SAND2000-2170
RP-ID  :  AC04-94AL85000
RP-ID  :  764803

美国|英语

来源: UNT Digital Library

【 摘 要 】

In this paper we introduce by means of examples a new technique for formulating compact (i.e. polynomial-size) LP relaxations in place of exponential-size models requiring separation algorithms. In the same vein as a celebrated theorem by Groetschel, Lovasz and Schrijver, we state the equivalence of compact separation and compact optimization. Among the examples used to illustrate our technique, we introduce a new formulation for the Traveling Salesman Problem, whose relaxation we show equivalent to the subtour elimination relaxation.