Abstract
The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.
Similar content being viewed by others
References
K. Aardal, R.E. Bixby, C.A.J. Hurkens, A.K. Lenstra, and J.W. Smeltink, 1998a, “Market split and basis reduction: Towards a solution of the Cornu´ejols-Dawande instances,” in Integer Programming and Combinatorial Optimization, 7th International IPCO Conference,R.E. Burkard, G. Cornuéjols, and G.J. Woeginger (Eds.), Springer Lecture Notes in Computer Science, 1610,Springer-Verlag: Heidelberg,1999, pp.1–16.
K. Aardal, C.A.J. Hurkens, and A.K. Lenstra, 1998b, “Solving a linear diophantine equation with lower and upper bounds on the variables,” in Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, R.E. Bixby, E.A. Boyd, and R.Z. Ríos-Mercado (Eds.), Springer Lecture Notes in Computer Science, 1412, Springer-Verlag: Heidelberg, 1998, pp. 229–242.
R.E. Bixby, S. Ceria, C.M. McZeal, and M.W.P. Savelsbergh, “An updated mixed integer programming library: MIPLIB 3.0,” Optima, vol. 58, 12–15, 1998. Problems available at http://www.caam.rice.edu/~bixby/ miplib/miplib.html
H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag: Berlin,1996.
G. Cornuéjols and M. Dawande, “AClass of Hard Small 0-1 Programs,” in IntegerProgramming and Combinatorial Optimization. 6th International IPCO Conference, Houston, Texas, June 1998,R.E. Bixby, E. Boyd, and R. Ríos-Mercado (Eds.), Springer Lecture Notes in Computer Science 1412. 1998, Springer-Verlag: Heidelberg, 1998, pp. 284–293.
M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.P. Schnorr, and J. Stern: “Improved low-density subset sum algorithms,” Computational Complexity, vol. 2, pp. 111–128, 1992.
M.J. Coster, B.A. LaMacchia, A.M. Odlyzko, and C.P. Schnorr, “An improved low-density subset sum algorithm,” in Proceedings EUROCRYPT’ 91, Brighton, May 1991,Springer Lecture Notes in Computer Science 547, Springer-Verlag: Heidelberg,1991, pp.54–67.
R.R. Coveyou and R.D. MacPherson, “Fourier analysis of uniform random number generators,”J. Assoc. Comp. Mach., vol. 14, 100–119, 1967.
U. Dieter, “How to calculate shortest vectors in a lattice,” Math. Comp., vol. 29, no. 131,827–833,1975.
U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,” Mathematics of Computation, vol. 44, 463–471,1985.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,W.H. Freeman and Company: New York, 1979.
Joux and J. Stern, “Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems,” in Proceedings of Fundamentals of Computation Theory’ 91, Springer Lecture Notes in Computer Science 529, Springer-Verlag: Heidelberg, 1991, pp.258–264.
M. Kaib and H. Ritter, “Block reduction for arbitrary norms,” Technical Report, Universität Frankfurt, 1995.
R. Kannan, “Minkowski's convex body theorem and integer programming,” Math. Operations Research, vol.12, 415–440,1987.
D.E. Knuth, The Art of Computer Programming, vol.2, Seminumerical Algorithms, Addison-Wesley: Reading, Mass, 1969.
J.C. Lagarias and A.M. Odlyzko, “Solving low-density subset sum problems,” J. Assoc. Comp. Mach., vol. 32, 229–246,1985.
A.K. Lenstra, H.W. Lenstra Jr., and L. Lovász, “Factoring polynomials with rational coefficients,” Math. Ann., vol. 261, 515–534, 1982.
H. Ritter, “Aufz¨ahlung von kurzen Gittervektoren in allgemeiner Norm,” Ph.D. Thesis, Universität Frankfurt, 1997.
A. Wassermann, “Finding simple t-designs with enumeration techniques,” J. Combinatorial Designs, vol.6,79–90, 1998.
H.P. Williams, Model Building in Mathematical Programming, Wiley: Chichester, 1978.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wassermann, A. Attacking the Market Split Problem with Lattice Point Enumeration. Journal of Combinatorial Optimization 6, 5–16 (2002). https://doi.org/10.1023/A:1013355015853
Issue Date:
DOI: https://doi.org/10.1023/A:1013355015853