Document Open Access Logo

An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

Authors Boro Sofranac, Ambros Gleixner, Sebastian Pokutta

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.52.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Boro Sofranac
  • Zuse Institute Berlin, Germany
  • TU Berlin, Germany
Ambros Gleixner
  • Zuse Institute Berlin, Germany
  • HTW Berlin, Germany
Sebastian Pokutta
  • Zuse Institute Berlin, Germany
  • TU Berlin, Germany

Funding

This research was partially conducted within the Research Campus MODAL funded by the German Federal Ministry of Education and Research (BMBF grant numbers 05M14ZAM, 05M20ZBM) as well as the DFG Cluster of Excellence MATH+ (EXC-2046/1, project id 390685689) funded by the Deutsche Forschungsgemeinschaft (DFG).

Cite AsGet BibTex

Boro Sofranac, Ambros Gleixner, and Sebastian Pokutta. An Algorithm-Independent Measure of Progress for Linear Constraint Propagation. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.52

Abstract

Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure - independently of the algorithmic design - the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Mixed discrete-continuous optimization
Keywords
  • Bounds Propagation
  • Mixed Integer Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Tobias Achterberg. Constraint Integer Programming. PhD thesis, TU Berlin, 2009. Google Scholar
  2. Tobias Achterberg. SCIP: solving constraint integer programs. Mathematical Programming Computation, 1(1):1-41, January 2009. URL: https://doi.org/10.1007/s12532-008-0001-1.
  3. Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2):473-506, 2020. URL: https://doi.org/10.1287/ijoc.2018.0857.
  4. Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress. In Michael Jünger and Gerhard Reinelt, editors, Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, pages 449-481. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-38189-8_18.
  5. Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger, Thomas Kasper, and Kurt Mehlhorn. Scil - symbolic constraints in integer linear programming. In Rolf Möhring and Rajeev Raman, editors, Algorithms - ESA 2002, pages 75-87, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. Google Scholar
  6. IonuŢ Aron, John N. Hooker, and Tallys H. Yunes. Simpl: A system for integrating optimization techniques. In Jean-Charles Régin and Michel Rueher, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 21-36, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  7. Pietro Belotti, Sonia Cafieri, Jon Lee, and Leo Liberti. Feasibility-based bounds tightening via fixed points. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications, Proc. of COCOA 2010, pages 65-76, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-17458-2_7.
  8. Alexander Bockmayr and Thomas Kasper. Branch and infer: A unifying framework for integer and finite domain constraint programming. INFORMS Journal on Computing, 10(3):287-300, 1998. URL: https://doi.org/10.1287/ijoc.10.3.287.
  9. Lucas Bordeaux, George Katsirelos, Nina Narodytska, and Moshe Y. Vardi. The complexity of integer bound propagation. J. Artif. Int. Res., 40(1):657–676, 2011. Google Scholar
  10. C. W. Choi, W. Harvey, J. H. M. Lee, and P. J. Stuckey. Finite domain bounds consistency revisited. In Abdul Sattar and Byeong-ho Kang, editors, AI 2006: Advances in Artificial Intelligence, pages 49-58, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  11. B. Fornberg. Generation of finite difference formulas on arbitrarily spaced grids. Mathematics of Computation, 51:699-706, 1988. Google Scholar
  12. Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL: http://www.optimization-online.org/DB_HTML/2020/03/7705.html.
  13. Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Technical report, Optimization Online, 2019. URL: http://www.optimization-online.org/DB_HTML/2019/07/7285.html.
  14. Warwick Harvey and Peter J. Stuckey. Improving linear constraint propagation by changing constraint representation. Constraints, 8(2):173-207, 2003. URL: https://doi.org/10.1023/a:1022323717928.
  15. Thorsten Koch, Alexander Martin, and Marc E. Pfetsch. Progress in academic computational integer programming. In Michael Jünger and Gerhard Reinelt, editors, Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, pages 483-506. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-38189-8_19.
  16. A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28(3):497-520, 1960. URL: http://www.jstor.org/stable/1910129.
  17. Olivier Lhomme. Consistency techniques for numeric csps. In Proceedings of the 13th International Joint Conference on Artifical Intelligence - Volume 1, IJCAI'93, page 232–238, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc. Google Scholar
  18. Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99-118, 1977. URL: https://doi.org/10.1016/0004-3702(77)90007-8.
  19. Kimbal Marriott and Peter Stuckey. Programming with Constraints: An Introduction. The MIT Press, February 1998. URL: https://doi.org/10.7551/mitpress/5625.001.0001.
  20. Roger Mohr and Gérald Masini. Good old discrete relaxation. In Proceedings of the 8th European Conference on Artificial Intelligence, ECAI'88, page 651–656, USA, 1988. Pitman Publishing, Inc. Google Scholar
  21. George Nemhauser and Laurence Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, Inc., 1988. URL: https://doi.org/10.1002/9781118627372.
  22. Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri. Numerical mathematics, volume 37. Springer, 2007. Google Scholar
  23. Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of Constraint Programming. Elsevier Science Inc., USA, 2006. Google Scholar
  24. Martin W. P. Savelsbergh. Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6:445-454, 1994. Google Scholar
  25. Christian Schulte and Peter J. Stuckey. Efficient constraint propagation engines. ACM Trans. Program. Lang. Syst., 31(1), 2008. URL: https://doi.org/10.1145/1452044.1452046.
  26. Boro Sofranac, Ambros Gleixner, and Sebastian Pokutta. Accelerating domain propagation: An efficient gpu-parallel algorithm over sparse matrices. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pages 1-11, 2020. URL: https://doi.org/10.1109/IA351965.2020.00007.
  27. Pascal Van Hentenryck, Vijay Saraswat, and Yves Deville. Design, implementation, and evaluation of the constraint language cc(fd). The Journal of Logic Programming, 37(1):139-164, 1998. URL: https://doi.org/10.1016/S0743-1066(98)10006-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact