Comments on Integer Hulls of Two Linear Constraints
- 1 August 1971
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 19 (4) , 1061-1069
- https://doi.org/10.1287/opre.19.4.1061
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.Keywords
This publication has 0 references indexed in Scilit: