The Gomory-Chvátal closure : polyhedrality, complexity, and extensions
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/68570 |
| _version_ | 1811087609335644160 |
|---|---|
| author | Dunkel, Juliane |
| author2 | Massachusetts Institute of Technology. Operations Research Center. |
| author_facet | Massachusetts Institute of Technology. Operations Research Center. Dunkel, Juliane |
| author_sort | Dunkel, Juliane |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. |
| first_indexed | 2024-09-23T13:49:11Z |
| format | Thesis |
| id | mit-1721.1/68570 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:49:11Z |
| publishDate | 2012 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/685702019-04-12T15:19:20Z The Gomory-Chvátal closure : polyhedrality, complexity, and extensions Dunkel, Juliane Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. Vita. Cataloged from PDF version of thesis. Includes bibliographical references (p. 163-166). In this thesis, we examine theoretical aspects of the Gomory-Chvátal closure of polyhedra. A Gomory-Chvátal cutting plane for a polyhedron P is derived from any rational inequality that is valid for P by shifting the boundary of the associated half-space towards the polyhedron until it intersects an integer point. The Gomory-ChvAital closure of P is the intersection of all half-spaces defined by its Gomory-Chvátal cuts. While it is was known that the separation problem for the Gomory-Chvátal closure of a rational polyhedron is NP-hard, we show that this remains true for the family of Gomory-Chvátal cuts for which all coefficients are either 0 or 1. Several combinatorially derived cutting planes belong to this class. Furthermore, as the hyperplanes associated with these cuts have very dense and symmetric lattices of integer points, these cutting planes are in some- sense the "simplest" cuts in the set of all Gomory-Chvátal cuts. In the second part of this thesis, we answer a question raised by Schrijver (1980) and show that the Gomory-Chvátal closure of any non-rational polytope is a polytope. Schrijver (1980) had established the polyhedrality of the Gomory-Chvdtal closure for rational polyhedra. In essence, his proof relies on the fact that the set of integer points in a rational polyhedral cone is generated by a finite subset of these points. This is not true for non-rational polyhedral cones. Hence, we develop a completely different proof technique to show that the Gomory-Chvátal closure of a non-rational polytope can be described by a finite set of Gomory-Chvátal cuts. Our proof is geometrically motivated and applies classic results from polyhedral theory and the geometry of numbers. Last, we introduce a natural modification of Gomory-Chvaital cutting planes for the important class of 0/1 integer programming problems. If the hyperplane associated with a Gomory-Chvátal cut for a polytope P C [0, 1]' does not contain any 0/1 point, shifting the hyperplane further towards P until it intersects a 0/1 point guarantees that the resulting half-space contains all feasible solutions. We formalize this observation and introduce the class of M-cuts that arises by strengthening the family of Gomory- Chvátal cuts in this way. We study the polyhedral properties of the resulting closure, its complexity, and the associated cutting plane procedure. by Juliane Dunkel Ph.D. 2012-01-13T18:44:28Z 2012-01-13T18:44:28Z 2011 2011 Thesis http://hdl.handle.net/1721.1/68570 767524210 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 166 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Dunkel, Juliane The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title | The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title_full | The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title_fullStr | The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title_full_unstemmed | The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title_short | The Gomory-Chvátal closure : polyhedrality, complexity, and extensions |
| title_sort | gomory chvatal closure polyhedrality complexity and extensions |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/68570 |
| work_keys_str_mv | AT dunkeljuliane thegomorychvatalclosurepolyhedralitycomplexityandextensions AT dunkeljuliane gomorychvatalclosurepolyhedralitycomplexityandextensions |