Optimization Online


Distributed domain propagation

Robert Lion Gottwald Gottwald(robert.gottwald***at***zib.de)
Stephen J. Maher(maher***at***zib.de)
Yuji Shinano(shinano***at***zib.de)

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 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.

Keywords: domain propagation; mixed integer programming; parallelization; portfolio solvers

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: ZIB-Report 16-71

Download: [PDF]

Entry Submitted: 12/07/2016
Entry Accepted: 12/07/2016
Entry Last Modified: 12/07/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society