Skip to main content
SpringerLink
Log in

Test sets of integer programs

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: Theory, algorithms, and applications. Prentice Hall, Englewood Cliffs NJ

    Google Scholar 

  2. Bárány I, Howe R, Scarf H (1993) The complex of maximal lattice free simplices, Proc. of the IPCO conference Erice, Italy, pp. 1–10

  3. Becker T, Weispfenning V (1993) Gröbner bases: A computational approach to commutative algebra. Springer Verlag, New York

    Google Scholar 

  4. Buchberger B (1985) Gröbner bases: An algorithmic method in polynomial ideal theory. In: Bose NK (ed.) Multidimensional systems theory, D. Reidel Publications, pp. 184–232

  5. Conti P, Traverso C (1991) Buchberger algorithm and integer programming. Proceedings AAECC-9 (New Orleans), Springer LNCS 539, pp. 130–139

  6. Cook W, Fonlupt J, Schrijver A (1986) An integer analogue of Caratheodory's theorem. J. Comb. Theory (B) 40:63–70

    Google Scholar 

  7. Cornuejols G, Urbaniak R, Weismantel R, Wolsey L (1997) Decomposition of integer programs and of generating sets. LNCS 1284, Burkard R, Woeginger G (eds.), Springer, pp. 92–103

  8. van der Corput JG (1931) Über Systeme von linear-homogenen Gleichungen und Ungleichungen. Proceedings Koninklijke Akademie van Wetenschappen te Amsterdam 34:368–371

    Google Scholar 

  9. Cox DA, Little JB, O'Shea D (1992) Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra. Springer-Verlag, New York

    Google Scholar 

  10. Diaconis P, Graham RL, Sturmfels B (1995) Primitive partition identities. Working Paper

  11. Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery 19:248–264

    Google Scholar 

  12. Faigle U (1987) Matroids in combinatorial optimization. In: White N Combinatorial geometries, Cambridge University Press, Cambridge

    Google Scholar 

  13. Frank A, Tardos E (1987) An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7:49–65

    Google Scholar 

  14. Gabow HN (1985) Scaling algorithms for network problems. Journal of Computer and System Sciences 31:148–168

    Google Scholar 

  15. Giles FR, Pulleyblank WR (1979) Total dual integrality and integer polyhedra. Lineare Algebra Appl. 25:191–196

    Google Scholar 

  16. Gordan P (1873) Über die Auflösung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6:23–28

    Google Scholar 

  17. Graver JE (1975) On the foundations of linear and integer programming I. Mathematical Programming 8:207–226

    Google Scholar 

  18. Gritzmann P, Wills JM (1993) Lattice points. In: Gruber PM, Wills JM (eds.) Handbook of convex geometry, Volume B, North-Holland, Amsterdam, pp. 765–798

    Google Scholar 

  19. Grötschel M, Lovász L (1995) Combinatorial optimization. In: Graham R, Grötschel M, Lovász L (eds.) Handbook of combinatorics, North-Holland, Amsterdam

    Google Scholar 

  20. Grötschel M, Lovász L, Schrijver A (1988) Geometrie algorithms and combinatorial optimization. Springer-Verlag, Berlin

    Google Scholar 

  21. Hosten S, Sturmfels B (1995) GRIN: An implementation of Gröbner bases for integer programming. In: Balas E, Clausen J (eds.) Integer programming and combinatorial optimization, Lecture notes in Computer Science 920, Springer-Verlag, Berlin, pp. 267–276

    Google Scholar 

  22. Henk M, Weismantel R (1996) On Hubert bases of polyhedral cones. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Preprint SC 96-12

  23. Kannan R (1987) Minkowski's convex body theorem and integer programming. Math. Oper. Res. 12:415–440

    Google Scholar 

  24. Kannan R, Lovász L (1988) Covering minima and lattice point free convx bodies. Ann. Math. 128:577–602

    Google Scholar 

  25. Kannan R, Lovász L, Scarf H (1990) The shapes of polyhedra. Math. Oper. Res. 15:364–380

    Google Scholar 

  26. Lagarias JC (1995) Point lattices. In: Graham R, Grötschel M, Lovász L (eds.) Handbook of combinatorics, North-Holland, Amsterdam

    Google Scholar 

  27. Liu J (1991) Hubert bases with the carathéodory property. PhD. Dissertation, Cornell University

  28. Lovász L (1989) Geometry of numbers and integer programming. In: hi M, Tanabe K (eds.) Proc. of the 13th International Symposium on Mathematical Programming, Mathematical Programming: 177–201

  29. Moulinet C, Pottier L Gröbner bases of toric ideals: Properties, algorithms and applications. Preprint INRIA Sophia Antipolis

  30. Pottier L (1991) Minimal solutions of linear diophantine systems: bounds and algorithms. Proceedings RTA (Como), Springer Verlag, LNCS 488

  31. Röck H (1980) Scaling techniques for minimal cost network flows. Discrete Structures and Algorithms, Carl Hanser, München, pp. 181–191

    Google Scholar 

  32. Scarf HE (1981) Production sets with indivisibilities, Part I: Generalities. Econometrica 49:1–32

    Google Scholar 

  33. Scarf HE (1986) Neighborhood systems for production sets with indivisibilities. Econometrica 54:507–532

    Google Scholar 

  34. Schrijver A (1986) Theory of linear and integer programming. Wiley Chichester

    Google Scholar 

  35. Schulz A, Weismantel R, Ziegler G (1995) 0/1 integer programming: Optimization and augmentation are equivalent. In: Spirakis P (ed.) Proceedings of the European Symposium on Algorithms, Lecture Notes in Computer Science, Springer-Verlag

  36. Sebö A (1990) Hubert bases, Caratheodory's Theorem and combinatorial optimization. In: Proc. of the IPCO conference, Waterloo, Canada, pp. 431–455

  37. Sturmfels B (1996) Gröbner bases and convex polytopes. American Mathematical Society, Providence

    Google Scholar 

  38. Sturmfels B, Thomas R (1994) Variation of cost functions in integer programming. Manuscript (1994), Mathematical Programming, to appear

  39. Sturmfels B, Weismantel R, Ziegler G (1995) Gröbner bases of lattices, corner polyhedra and integer programming. Beitr" age zur Geometrie und Algebra 36:281–298

    Google Scholar 

  40. Thomas R (1995) A geometric Buchberger algorithm for integer programming. Math. Oper. Res. 20, 4:864–884

    Google Scholar 

  41. Thomas R (1994) Gröbner basis methods for integer programming. PhD. Dissertation, Cornell University

  42. Thomas R, Weismantel R (1995) Truncated Gröbner bases for integer programming. Applicable Algebra in Engineering, Communication and Computing 8, 4:241–257

    Google Scholar 

  43. Urbaniak R, Weismantel R, Ziegler G (1994) A variant of Buchberger's algorighm for integer programming. SIAM Journal on Discrete Mathematics 1, 10:96–108

    Google Scholar 

  44. Welsh DJA (1976) Matroid theory. Academic Press London

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Konrad-Zuse-Zentrum für Informationstechnik, Takustraße 7, D-14195, Berlin, Germany

    Robert Weismantel

Authors
  1. Robert Weismantel
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by a “Gerhard-Hess-Forschungsförderpreis” of the German Science Foundation (DFG).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Weismantel, R. Test sets of integer programs. Mathematical Methods of Operations Research 47, 1–37 (1998). https://doi.org/10.1007/BF01193834

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01193834

Key words

Search

Navigation