A connection between cutting plane theory and the geometry of numbers |
| |
| Authors: | Gérard Cornuéjols Yanjun Li |
| |
| Institution: | (1) Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, USA, US |
| |
| Abstract: | In this paper, we relate several questions about cutting planes to a fundamental problem in the geometry of numbers, namely,
the closest vector problem. Using this connection we show that the dominance, membership and validity problems are NP-complete
for Chvátal and split cuts.
Received: August 28, 2001 / Accepted: March 2002?Published online May 8, 2002 |
| |
| Keywords: | : closest vector problem – dominance problem – membership problem – validity problem – Chvátal cut – split cut – disjunctive cut – Gomory cut |
| 本文献已被 SpringerLink 等数据库收录！ |
|
