A Generalization of a Theorem of Chvatal and Gomory.
Abstract
The author generalizes the result of Chvatal and Gomory, by providing two simple operations which, iteratively applied, yield all facets to the convex span of all feasible points to a linear problem plus an additional nonlinear constraint, when the linear constraints define a polytope. In integer programming, this additional nonlinear constraint is that the solution be integral. The extension permits restrictions of the solution to more general sets than a bounded set of integer points, and understood algorithmically, it provides a finitely convergent cutting-plane algorithm for a large class of nonlinear programming problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1974
- Accession Number
- AD0781268
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University