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

  • Export Bibtex
Metadaten
Author:Robert Lion Gottwald, Stephen J. Maher, Yuji Shinano
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

$Rev: 13581 $