Optimization Online


Rapid prototyping of parallel primal heuristics for domain specific MIPs: Application to maritime inventory routing

Lluis-Miquel Munguia(lluis.munguia***at***gatech.edu)
Shabbir Ahmed(shabbir.ahmed***at***isye.gatech.edu )
David A. Bader(bader***at***cc.gatech.edu )
George L. Nemhauser(george.nemhauser***at***isye.gatech.edu )
Yufen Shao(yufen.shao***at***exxonmobil.com )
Dimitri J. Papageorgiou(dimitri.j.papageorgiou***at***exxonmobil.com)

Abstract: Parallel Alternating Criteria Search (PACS) relies on the combination of computer parallelism and Large Neighborhood Searches to attempt to deliver high quality solutions to any generic Mixed-Integer Program (MIP) quickly. While general-purpose primal heuristics are widely used due to their universal application, they are usually outperformed by domain-specific heuristics when optimizing a particular problem class. In this paper, we focus on the fast development of domain-specific parallel primal heuristics. Our approach entails specializing PACS to better adapt to the target problem structure. We showcase its application to two classes of the Maritime Inventory Routing Problem, an important application of MIPs to real world problems. We computationally compare the proposed modified framework with state-of-the art specialized algorithms and MIP solvers. Results show the effectiveness of our approach, and how the modular nature of PACS can provide an excellent platform for the rapid prototyping of parallel domain-specific heuristics.

Keywords: Parallel Computing; Primal Heuristics; Discrete Optimization; Maritime Inventory Routing; Large Neighborhood Search

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

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

Category 3: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 09/24/2018
Entry Accepted: 09/24/2018
Entry Last Modified: 09/24/2018

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