Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Author:Robert Lion GottwaldORCiD, Stephen J. Maher, Yuji ShinanoORCiD
Document Type:ZIB-Report
Tag:domain propagation; mixed integer programming; parallelization; portfolio solvers
CCS-Classification:G. Mathematics of Computing
Date of first Publication:2016/12/07
Series (Serial Number):ZIB-Report (16-71)
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.)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.