Enumerative Cuts: I

Claude-Alain Burdet
Additional contact information
Claude-Alain Burdet: Carnegie-Mellon University, Pittsburgh, Pennsylvania

Operations Research, 1973, vol. 21, issue 1, 61-89

Abstract: This paper presents new types of cutting-plane algorithms for integer-constrained optimization problems. The underlying idea of the method of enumerative cuts is to make use of an enumeration procedure in order to construct cutting planes that can be made arbitrarily deep. In recent publications, Balas and Young have established in somewhat different contexts that valid cutting planes can be generated from the intersection of (basic) rays with adequately constructed hyperspheres. This paper introduces a family of polyhedra to replace the sphere; these polyhedra are not tangential to the hypersphere and produce cutting planes with particular characteristics that are discussed. Constructive procedures are sketched for generating step-by-step cutting planes that become deeper and deeper at every step, until the deepest cut is obtained. This construction often relies on a partial enumeration scheme of the set of integer solutions.

Date: 1973
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.1.61 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:21:y:1973:i:1:p:61-89

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().