On the Rational Polytopes with Chvatal Rank 1

• 成果类型: Article
• 署名作者: Cornuejols, Gerard; Lee, Dabeen; Li, Yanjun
• 署名单位: Carnegie Mellon University; Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1317-x
• 发表日期: 2020
• 页码: 21-46
• 关键词: nonsymmetric convex-bodies; gomory closure; membership problem; complexity; algorithm; THEOREM

摘要

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 boolean AND\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cap $$\end{document} 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.