Yufen Shao

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

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Transportation

    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

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    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

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Parallel Algorithms Tags , ,

    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

  • Kevin C Furman
  • Vikas Goel
  • Guangye Li
  • Yufen Shao
  • Badrinarayanan Velamur Asokan
    • Categories Parallel Algorithms, Supply Chain Management, Transportation

    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

  • Kevin C Furman
  • Vikas Goel
  • Samid Hoda
  • Yufen Shao
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Transportation

    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

  • Kevin C Furman
  • Willem-Jan van Hoeve
  • Vikas Goel
  • Yufen Shao
  • Marla Slusky
    • Categories Production and Logistics, Supply Chain Management, Transportation Tags , ,

    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

  • Shabbir Ahmed
  • Rodolfo Carvajal
  • Kevin C Furman
  • George L. Nemhauser
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , , , ,

    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