×

Test sets of integer programs. (English) Zbl 0927.90086

Summary: 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: the Graver test set is naturally derived from a study of the integral vectors in cones; the Scarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-called reduced 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.

MSC:

90C10 Integer programming

Software:

GRIN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: Theory, algorithms, and applications. Prentice Hall, Englewood Cliffs NJ
[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 · Zbl 0923.90117
[3] Becker T, Weispfenning V (1993) Gr?bner bases: A computational approach to commutative algebra. Springer Verlag, New York · Zbl 0772.13010
[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 · Zbl 0771.13014
[6] Cook W, Fonlupt J, Schrijver A (1986) An integer analogue of Caratheodory’s theorem. J. Comb. Theory (B) 40:63-70 · Zbl 0589.52005 · doi:10.1016/0095-8956(86)90064-X
[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 · Zbl 0001.39002
[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
[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 · Zbl 0318.90024
[12] Faigle U (1987) Matroids in combinatorial optimization. In: White N Combinatorial geometries, Cambridge University Press, Cambridge · Zbl 0632.05018
[13] Frank A, Tardos E (1987) An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7:49-65 · Zbl 0641.90067 · doi:10.1007/BF02579200
[14] Gabow HN (1985) Scaling algorithms for network problems. Journal of Computer and System Sciences 31:148-168 · Zbl 0596.90095 · doi:10.1016/0022-0000(85)90039-X
[15] Giles FR, Pulleyblank WR (1979) Total dual integrality and integer polyhedra. Lineare Algebra Appl. 25:191-196 · Zbl 0413.90054 · doi:10.1016/0024-3795(79)90018-1
[16] Gordan P (1873) ?ber die Aufl?sung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6:23-28 · JFM 05.0095.01 · doi:10.1007/BF01442864
[17] Graver JE (1975) On the foundations of linear and integer programming I. Mathematical Programming 8:207-226 · Zbl 0323.90035 · doi:10.1007/BF01681344
[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
[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 · Zbl 0854.90117
[20] Gr?tschel M, Lov?sz L, Schrijver A (1988) Geometrie algorithms and combinatorial optimization. Springer-Verlag, Berlin · Zbl 0634.05001
[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
[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 · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[24] Kannan R, Lov?sz L (1988) Covering minima and lattice point free convx bodies. Ann. Math. 128:577-602 · Zbl 0659.52004 · doi:10.2307/1971436
[25] Kannan R, Lov?sz L, Scarf H (1990) The shapes of polyhedra. Math. Oper. Res. 15:364-380 · Zbl 0712.52015 · doi:10.1287/moor.15.2.364
[26] Lagarias JC (1995) Point lattices. In: Graham R, Gr?tschel M, Lov?sz L (eds.) Handbook of combinatorics, North-Holland, Amsterdam
[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
[32] Scarf HE (1981) Production sets with indivisibilities, Part I: Generalities. Econometrica 49:1-32 · Zbl 0446.90006 · doi:10.2307/1911124
[33] Scarf HE (1986) Neighborhood systems for production sets with indivisibilities. Econometrica 54:507-532 · Zbl 0605.90018 · doi:10.2307/1911306
[34] Schrijver A (1986) Theory of linear and integer programming. Wiley Chichester · Zbl 0665.90063
[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
[38] Sturmfels B, Thomas R (1994) Variation of cost functions in integer programming. Manuscript (1994), Mathematical Programming, to appear · Zbl 0888.90125
[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 · Zbl 0863.90115
[40] Thomas R (1995) A geometric Buchberger algorithm for integer programming. Math. Oper. Res. 20, 4:864-884 · Zbl 0846.90079 · doi:10.1287/moor.20.4.864
[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 · Zbl 0914.90203
[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 · Zbl 0872.90065 · doi:10.1137/S0895480195281209
[44] Welsh DJA (1976) Matroid theory. Academic Press London · Zbl 0343.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.