Optimization Online


On the Rational Polytopes with Chvatal Rank 1

Gerard Cornuejols(gc0v***at***andrew.cmu.edu)
Dabeen Lee(dabeenl***at***andrew.cmu.edu)
Yanjun Li(li14***at***purdue.edu)

Abstract: We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the problem, and we give several special classes where this is indeed the case. We show that any compact convex set whose Chvatal closure is empty has an integer width of at most n, and we give an example showing that this bound is tight within an additive constant of 1. This determines the time complexity of a Lenstra-type algorithm. However, the promise that a polytope has Chvatal rank 1 seems hard to verify. We prove that deciding emptiness of the Chvatal closure of a rational polytope given by its linear description is NP-complete, even when the polytope is contained in the unit hypercube or is a rational simplex and it does not contain any integer point.

Keywords: Integer programming, Chvatal closure, Chvatal cuts

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Mathematical Programming A

Download: [PDF]

Entry Submitted: 08/07/2018
Entry Accepted: 08/07/2018
Entry Last Modified: 08/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society