科技报告详细信息
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.
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
764803.pdf | 1339KB | download |