Juliane Dunkel

A Refined Gomory-Chvátal Closure for Polytopes in the Unit Cube

  • Juliane Dunkel
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches

    We introduce a natural strengthening of Gomory-Chvátal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it … Read more

    The Gomory-Chvatal closure of a non-rational polytope is a rational polytope

  • Juliane Dunkel
  • Andreas S. Schulz
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , ,

    The question as to whether the Gomory-Chvatal closure of a non-rational polytope is a polytope has been a longstanding open problem in integer programming. In this paper, we answer this question in the affirmative, by combining ideas from polyhedral theory and the geometry of numbers. ArticleDownload View PDF