A Connection Between Cutting Plane Theory and the Geometry of Numbers

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 Chvatal and split cuts.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2002
Accession Number
AD1021089

Entities

People

  • Gérard Cornuéjols
  • Yanjun Li

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Geometry

Readers

  • East Asian Political and Security Studies within the Soviet Union
  • Manufacturing Engineering.
  • Operations Research