Distributed domain propagation
Please always quote using this URN: urn:nbn:de:0297-zib-61380
- Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's 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 a variables domain has been reduced. This paper investigates the impact of distributed domain propagation 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.
Author: | Robert Lion GottwaldORCiD, Stephen J. Maher, Yuji ShinanoORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | domain propagation; mixed integer programming; parallelization; portfolio solvers |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Classification: | G. Mathematics of Computing |
Date of first Publication: | 2016/12/07 |
Series (Serial Number): | ZIB-Report (16-71) |
ISSN: | 1438-0064 |
Published in: | 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics, Volume 75, SEA 2017, June 21–23, 2017 - London, UK Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman (Eds.) |
DOI: | https://doi.org/10.4230/LIPIcs.SEA.2017.6 |