Document Open Access Logo

Distributed Domain Propagation

Authors Robert Lion Gottwald, Stephen J. Maher, Yuji Shinano

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.6.pdf
  • Filesize: 0.52 MB
  • 11 pages

Document Identifiers

Author Details

Robert Lion Gottwald
Stephen J. Maher
Yuji Shinano

Cite AsGet BibTex

Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano. Distributed Domain Propagation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SEA.2017.6

Abstract

Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
Keywords
  • mixed integer programming
  • parallelization
  • domain propagation
  • portfolio solvers

Metrics

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

References

  1. Tobias Achterberg. Conflict analysis in mixed integer programming. Discrete Optimization, 4(1):4-20, 2007. Mixed Integer ProgrammingIMA Special Workshop on Mixed-Integer Programming. URL: http://dx.doi.org/10.1016/j.disopt.2006.10.006.
  2. Tobias Achterberg. Scip: Solving constraint integer programs. Math. Prog. Comp., 1(1):1-41, 2009. Google Scholar
  3. Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger. Presolve reductions in mixed integer programming. Technical Report 16-44, ZIB, Takustr.7, 14195 Berlin, 2016. Google Scholar
  4. Tobias Achterberg and Roland Wunderling. Mixed Integer Programming: Analyzing 12 Years of Progress, pages 449-481. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38189-8_18.
  5. Tomáš Balyo, Peter Sanders, and Carsten Sinz. HordeSat: A Massively Parallel Portfolio SAT Solver, pages 156-172. Springer International Publishing, Cham, 2015. URL: http://dx.doi.org/10.1007/978-3-319-24318-4_12.
  6. R. E. Bixby, S. Ceria, C. M. McZeal, and M. W. P. Savelsbergh. An updated mixed integer programming library: MIPLIB 3.0. Optima, 58:12-15, 1998. Google Scholar
  7. R. Carvajal, S. Ahmed, G. Nemhauser, K. Furman, V. Goel, and Y. Shao. Using diversification, communication and parallelism to solve mixed-integer linear programs. Oper. Res. Lett., 42(2):186-189, March 2014. URL: http://dx.doi.org/10.1016/j.orl.2013.12.012.
  8. Barbara Chapman, Gabriele Jost, and Ruud Van Der Pas. Using OpenMP: portable shared memory parallel programming, volume 10. MIT press, 2008. Google Scholar
  9. FICO Xpress-Optimizer. URL: http://www.fico.com/en/Products/DMTools/xpress-overview/Pages/Xpress-Optimizer.aspx.
  10. Matteo Fischetti, Andrea Lodi, Michele Monaci, Domenico Salvagnin, and Andrea Tramontani. Improving branch-and-cut performance by random sampling. Mathematical Programming Computation, 8(1):113-132, 2016. URL: http://dx.doi.org/10.1007/s12532-015-0096-0.
  11. Gerald Gamrath. Improving strong branching by domain propagation. EURO Journal on Computational Optimization, 2(3):99-122, 2014. URL: http://dx.doi.org/10.1007/s13675-014-0021-8.
  12. Gerald Gamrath, Tobias Fischer, Tristan Gally, Ambros M. Gleixner, Gregor Hendel, Thorsten Koch, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Stefan Vigerske, Dieter Weninger, Michael Winkler, Jonas T. Witt, and Jakob Witzig. The SCIP Optimization Suite 3.2. Technical Report 15-60, ZIB, Takustr.7, 14195 Berlin, 2016. Google Scholar
  13. Robert Lion Gottwald. Experiments with a Parallel Portfolio of SCIP Solvers. Master’s thesis, Freie Universität Berlin, 2016. Google Scholar
  14. Youssef Hamadi, Saïd Jabbour, and Lakhdar Sais. Manysat: a parallel SAT solver. JSAT, 6(4):245-262, 2009. URL: http://jsat.ewi.tudelft.nl/content/volume6/JSAT6_12_Hamadi.pdf.
  15. Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E. Bixby, Emilie Danna, Gerald Gamrath, Ambros M. Gleixner, Stefan Heinz, Andrea Lodi, Hans Mittelmann, Ted Ralphs, Domenico Salvagnin, Daniel E. Steffy, and Kati Wolter. MIPLIB 2010. Math. Prog. Comp., 3:103-163, 2011. Google Scholar
  16. Stephen J. Maher, Tobias Fischer, Tristan Gally, Gerald Gamrath, Ambros Gleixner, Robert Lion Gottwald, Gregor Hendel, Thorsten Koch, Marco E. Lübbecke, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Dieter Weninger, Jonas T. Witt, and Jakob Witzig. The scip optimization suite 4.0. Technical Report 17-12, ZIB, Takustr.7, 14195 Berlin, 2017. Google Scholar
  17. Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: Engineering an Efficient SAT Solver. In Proceedings of the 38th Annual Design Automation Conference, DAC'01, pages 530-535, New York, NY, USA, 2001. ACM. URL: http://dx.doi.org/10.1145/378239.379017.
  18. Lluıs-Miquel Munguıa, Geoffrey Oxberry, and Deepak Rajan. Pips-sbb: A parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs. Technical report, Optimization Online, 2015. Google Scholar
  19. George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience, New York, NY, USA, 1988. Google Scholar
  20. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011. Google Scholar
  21. Ted Ralphs, Yuji Shinano, Timo Berthold, and Thorsten Koch. Parallel solvers for mixed integer linear programming. Technical Report 16-74, ZIB, Takustr.7, 14195 Berlin, 2016. Google Scholar
  22. T. K. Ralphs. Parallel branch and cut. In Parallel Combinatorial Optimization, pages 53-101. Wiley, 2006. Google Scholar
  23. Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, and Thorsten Koch. ParaSCIP - a parallel extension of SCIP. In Christian Bischof, Heinz-Gerd Hegering, Wolfgang E. Nagel, and Gabriel Wittum, editors, Competence in High Performance Computing 2010, pages 135-148. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-24025-6_12.
  24. Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, and Michael Winkler. Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores. In Proc. of 30th IEEE International Parallel &Distributed Processing Symposium, 2016. to appear. Google Scholar
  25. Yuji Shinano, Stefan Heinz, Stefan Vigerske, and Michael Winkler. Fiberscip - a shared memory parallelization of scip. Technical Report 13-55, ZIB, Takustr.7, 14195 Berlin, 2013. Google Scholar
  26. Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58:267-288, 1994. Google Scholar
  27. Y. Xu, T. K. Ralphs, L. Ladányi, and M. J. Saltzman. Computational experience with a software framework for parallel integer programming. The INFORMS Journal on Computing, 21:383-397, 2009. Google Scholar
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