Abstract
In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrixA. If the matrix satisfies some mild conditions, and isgeneric, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular row ofA as the objective function, and using the remaining rows to impose constraints on the integer variables.
Similar content being viewed by others
References
I. Bárány, R. Howe and H. Scarf, The complex of maximal lattice free simplices,Mathematical Programming 66 (3) (1994).
I. Bárány and H. Scarf, Matrices with identical sets of neighbors, Cowles Foundation Discussion Paper No. 1127, 1996; submitted toMathematics of Operations Research
I. Bárány, H. Scarf and D. Shallcross, The topological structure of maximal lattice free convex bodies: The general case, Cowles Foundation Discussion Paper No. 1087 (1994); also in:Mathematical Programming, to appear.
P. Conti and C. Traverso, Buchberger algorithm and integer programming, in:Proc. AAECC-9, New Orleans, Lecture Notes in Computer Science, Vol. 539 (Springer, Berlin, 1991) 130–139.
D. Cox, J. Little and D. O’Shea,Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (Springer, New York, 1992).
J.E. Graver, On the foundations of linear and integer linear programming,Mathematical Programming 8 (1975).
R. Kannan, Lattice translates of a polytope and the Frobenius problem,Combinatorica 12 (1992) 2.
H. Scarf, Production sets with indivisibilities, Part I: Generalities,Econometrica 4 (1981) 1.
H. Scarf (with the assistance of T. Hansen),The Computation of Economic Equilibria, Cowles Foundation Monograph, No. 23. (Yale University Press, New Haven, 1973).
H. Scarf, Production sets with indivisibilities, Part II: The case of two activities,Econometrica 49 (1981) 2.
H. Scarf, Integral polyhedra in three space,Mathematics of Operations Research 10 (1985) 3.
H. Scarf, Neighborhood systems for production sets with indivisibilities,Econometrica 54 (1986) 3.
B. Sturmfels and R.R. Thomas, Variation of cost functions in integer programming, 1994; also in:Mathematical Programming, to appear.
B. Sturmfels, R. Weismantel and G.M. Ziegler, Gröbner bases of lattices, corner polyhedra, and integer programming,Contributions to Algebra and Geometry 36 (1995) 2.
R. Thomas, A geometric Buchberger algorithm for integer programming,Mathematics of Operations Research 20 (1994) 4.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Scarf, H.E. Test sets for integer programs. Mathematical Programming 79, 355–368 (1997). https://doi.org/10.1007/BF02614324
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02614324