[en] The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer k, we prove that there exists a constant c(n,k), depending only on the dimension n and on the number k, such that if a bounded polyhedron {x in R^n : Ax <= b} contains exactly k integer points, then there exists a subset of the rows, of cardinality no more than c(n,k), defining a polyhedron that contains exactly the same k integer points.
In this case c(n,0)=2^n as in the original case of Doignon-Bell-Scarf for infeasible systems of inequalities.
We work on both upper and lower bounds for the constant c(n,k) and discuss some consequences, including a Clarkson-style algorithm to find the l-th best solution of an integer program with respect to the ordering induced by the objective function.
Disciplines :
Mathematics
Author, co-author :
Aliev, Iskander; Cardiff University > Mathematics Department
Bassett, Robert; University of California, Davis - UC Davis > Department of Mathematics
De Loera, Jesus; University of California, Davis - UC Davis > Department of Mathematics
Louveaux, Quentin ; Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
I. Aliev, J. A. De Loera and Q. Louveaux: Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem, in: Proceedings of Integer Programming and Combinatorial Optimization, 17th International IPCO Conference, Bonn Germany, June, 2014.
N. Amenta: Helly-type theorems and generalized linear programming, Discrete and Computational Geometry 12 (1994), 241–261.
G. Averkov and R. Weismantel: Transversal numbers over subsets of linear spaces, Adv. Geom. 12 (2012), 19–28.
K. Andersen, Q. Louveaux and R. Weismantel: Certificates of linear mixed integer infeasibility, Operations Research Letters 36 (2008), 734–738.
K. Andersen, Q. Louveaux and R. Weismantel: An analysis of mixed integer linear sets based on lattice point free convex sets, Math of Operations Research 35 (2010), 233–256.
K. Andersen, Q. Louveaux, R. Weismantel and L. Wolsey: Inequalities from two rows of the simplex tableau, in: M. Fischetti & D. P., Williamson (Eds.) Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, Lecture Notes in Computer Science 4513, 1-15.
I. Bárány, M. Katchalski and J. Pach: Quantitative Helly-type theorems, Proc. Amer. Math. Soc. 86 (1982), 109–114.
I. Bárány, M. Katchalski and J. Pach: Helly’s theorem with volumes, Amer. Math. Monthly 91 (1984), 362–365.
A. Barvinok and J. Pommersheim: An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics, Math. Sci. res. Inst. Publ., 38, Cambridge Univ. Press, Cambridge, (1999), 91–147.
D. E. Bell: A theorem concerning the integer lattice, Studies in Applied Mathematics 56 (1977), 187–188.
V. Borozan and G. Cornuéjols: Minimal valid inequalities for integer constraints, Math. Oper. Res. 34 (2009), 538–546.
K. L. Clarkson: Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM 42 (1995), 488–499.
M. Conforti, G. Cornuéjols and G. Zambelli: Corner polyhedron and intersection cuts, Surveys in Operations Research and Management Science 16 (2011), 105–120.
L. Danzer, B. Grünbaum and V. Klee: Helly’s theorem and its relatives, in: 1963 Proc. Sympos. Pure Math., Vol. VII pp. 101-180 Amer. Math. Soc., Providence, R.I.
J. A. De Loera, R. Hemmecke and M. Köppe: Algebraic and geometric ideas in the theory of discrete optimization, MOS-SIAM Series on Optimization, 14. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013.
S. Dey and L. Wolsey: Constrained infinite group relaxations of MIPs, SIAM J. Optim. 20 (2010), 2890–2912.
J-P. Doignon: Convexity in cristallographical lattices, Journal of Geometry 3 (1973), 71–85.
J. Eckhoff: Helly, Radon, and Carathéodory type theorems, in: Handbook of convex geometry, Vol. A, B, 389-448, North-Holland, Amsterdam, 1993.
F. Eisenbrand: Fast integer programming in fixed dimension, Algorithms-ESA (2003), 196–207.
B. Gärtner, J. Matoušek, L. Rüst and P Škovroň: Violator spaces: structure and algorithms, Discrete Applied Mathematics 156 (2008), 2124–2141.
H. W. Hamacher and M. Queyranne: K best solutions to combinatorial optimization problems, Ann. Oper. Res. 4 (1985), 123–143.
A.J. Hoffman: Binding constraints and Helly numbers, in: Proceedings of Second International Conference on Combinatorial Mathematics (New York, 1978), 284–288, Ann. New York Acad. Sci., 319, New York Acad. Sci., New York, 1979.
J. C. Lagarias and G. M. Ziegler: Bounds for lattice polytopes containing a fixed number of interior points in a sublattice, Canad. J. Math. 43 (1991), 1022–1035.
E. L. Lawler: A procedure for computing the K-best solutions to discrete optimization problems and its application to the shortest path problem, Management Sci. 18 (1971/72), 401–405.
O. Pikhurko: Lattice points in lattice polytopes, Mathematika 48 (2003), 15–24.
H. E. Scarf: An observation on the structure of production sets with indivisibilities, Proceedings of the National Academy of Sciences 74.9 (1977), 3637–3641.
A. Schrijver: Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1986.
M. Sharir and E. Welzl: A combinatorial bound for linear programming and related problems, in: Proceedings of 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 577, Springer-Verlag, (1992), 567–579.
R. Wenger: Helly-type theorems and geometric transversals, in: Handbook of discrete and computational geometry, Handbook of discrete and computational geometry. Second edition. Edited by Jacob E. Goodman and Joseph O’Rourke. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
