Optimization Online


Using diversification, communication and parallelism to solve mixed-integer linear programs

Rodolfo Carvajal(rocarvaj***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
George Nemhauser(george.nemhauser***at***isye.gatech.edu)
Kevin Furman(kevin.c.furman***at***exxonmobil.com)
Vikas Goel(vikas.goel***at***exxonmobil.com)
Yufen Shao(yufen.shao***at***exxonmobil.com)

Abstract: Performance variability of modern mixed-integer programming solvers and possible ways of exploiting this phenomenon present an interesting opportunity in the development of algorithms to solve mixed-integer linear programs (MILPs). We propose a framework using multiple branch-and-bound trees to solve MILPs while allowing them to share information in a parallel execution. We present computational results on instances from MIPLIB 2010 illustrating the benefits of this framework.

Keywords: Integer programming, branch-and-bound, diversification, communication, parallelism, performance variability

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

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

Category 3: Optimization Software and Modeling Systems

Citation: Submitted to Elsevier, May 2013.

Download: [PDF]

Entry Submitted: 05/30/2013
Entry Accepted: 05/30/2013
Entry Last Modified: 05/30/2013

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