  


On the Rational Polytopes with Chvatal Rank 1
Gerard Cornuejols(gc0vandrew.cmu.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 ∩ coNP, an indication that it is probably not NPcomplete. 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 Lenstratype 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 NPcomplete, 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  