Optimization Online


Parallel Solvers for Mixed Integer Linear Optimization

Ted K. Ralphs(ted***at***lehigh.edu)
Yuji Shinano(shinano***at***zib.de)
Timo Berthold(timoberthold***at***fico.com)
Thorsten Koch(koch***at***zib.de)

Abstract: In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development of parallel MILP solvers has been underway since the 1990s, the impact of improvements in sequential solution algorithms has been much greater than that which came from the application of parallel computing technologies. As a result, parallelization efforts have met with only relatively modest success. In addition, improvements to the underlying sequential solution technologies have actually been somewhat detrimental with respect to the goal of creating scalable parallel algorithms. This has made efforts at parallelization an even greater challenge in recent years. With the pervasiveness of multi-core CPUs, current state-of-the-art MILP solvers have now all been parallelized and research on parallelization is once again gaining traction. We summarize the current state-of-the-art and describe how existing parallel MILP solvers can be classified according to various properties of the underlying algorithm.

Keywords: parallel algorithm, branch and cut, branch and bound, mixed integer linear optimization

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

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

Citation: COR@L Technical Report 16T-014-R3 (ISE, Lehigh University) and Zuse Institute Berlin (ZIB) Technical Report 16-74.

Download: [PDF]

Entry Submitted: 05/04/2017
Entry Accepted: 05/04/2017
Entry Last Modified: 05/04/2017

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