Comments on Integer Hulls of Two Linear Constraints

R. G. Jeroslow
Additional contact information
R. G. Jeroslow: University of Minnesota, Minneapolis, Minnesota

Operations Research, 1971, vol. 19, issue 4, 1061-1069

Abstract: This paper establishes an intrinsic complexity for the integer-programming problem that goes well beyond the computational complexities of linear programming. To this end, it describes a procedure with the following property: given any two independent linear constraints in two dimensions and any number N however large, the procedure determines two other linear constraints (with integer coefficients) arbitrarily “close” to the given constraints such that the two new constraints have at least N faces in their integer hull. It is possible for the integer-programming optimum to occur at any extreme point of this hull, and the number of extreme points is one less than the number of faces. In contrast, the linear-programming problem consisting of two inequalities in the plane is a triviality. The paper has an expository style and illustrates its highly geometrical arguments with figures.

Date: 1971
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.4.1061 (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:19:y:1971:i:4:p:1061-1069

Access Statistics for this article

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