Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 4
Zurück zur Trefferliste

Distributed domain propagation

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Robert Lion GottwaldORCiD, Stephen J. Maher, Yuji ShinanoORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:domain propagation; mixed integer programming; parallelization; portfolio solvers
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Klassifikation:G. Mathematics of Computing
Datum der Erstveröffentlichung:07.12.2016
Schriftenreihe (Bandnummer):ZIB-Report (16-71)
ISSN:1438-0064
Verlagspublikation: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.