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

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. … Read more

Alternating Criteria Search: A Parallel Large Neighborhood Search Algorithm for Mixed Integer Programs

We present a parallel large neighborhood search framework for finding high quality primal solutions for generic Mixed Integer Programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary … Read more

A Parallel Local Search Framework for the Fixed-Charge Multicommodity Network Flow Problem

We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multi-commodity Network Flow problem (FCMNF). The approach proceeds by improving a given feasible solution by solving restricted instances of the problem where flows of certain commodities are fixed to those in the solution while the other commodities are locally … Read more

Parallel Large-Neighborhood Search Techniques for LNG Inventory Routing

Liquefied natural gas (LNG) is estimated to account for a growing portion of the world natural gas trade. For profitable operation of a capital intensive LNG project, it is necessary to optimally design various aspects of the supply chain associated with it. Of particular interest is optimization of ship schedules and the inventories on the … Read more

Bound Improvement for LNG Inventory Routing

Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. In this paper, we develop methods for improving both lower and upper bounds for a previously stated form of an LNG inventory routing problem. A Dantzig-Wolfe-based decomposition approach is developed for LNG inventory routing problem (LNG-IRP) attempting to overcome poor lower … Read more

Constraint Programming for LNG Ship Scheduling and Inventory Management

We propose a constraint programming approach for the optimization of inventory routing in the liquefied natural gas industry. We present two constraint programming models that rely on a disjunctive scheduling representation of the problem. We also propose an iterative search heuristic to generate good feasible solutions for these models. Computational results on a set of … Read more

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

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 … Read more