Optimization Online


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

Lluí­s-Miquel Munguía (lluis.munguia***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
David A. Bader (bader***at***cc.gatech.edu)
George L. Nemhauser (george.nemhauser***at***isye.gatech.edu)
Vikas Goel (vikas.goel***at***exxonmobil.com)
Yufen Shao (yufen.shao***at***exxonmobil.com)

Abstract: 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 optimized. We derive multiple independent local search neighborhoods from an arc-based mixed integer programming (MIP) formulation of the problem which are explored in parallel. Our parallel implementation takes advantage of the hybrid memory architecture in modern platforms and the effectiveness of MIP solvers in solving small problems instances. Computational experiments on FCMNF instances from the literature demonstrate the competitiveness of our approach against state of the art MIP solvers and other heuristic methods.

Keywords: local search heuristic, parallel computing,multi commodity flow

Category 1: Applications -- OR and Management Sciences

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

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

Citation: Submitted for publication

Download: [PDF]

Entry Submitted: 06/26/2014
Entry Accepted: 06/26/2014
Entry Last Modified: 08/02/2016

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