Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem

We develop a solution approach for the fixed-charge network flow (FCNF) problem that produces provably high-quality solutions quickly. The solution approach combines mathematical programming algorithms with heuristic search techniques. To obtain high-quality solutions, it relies on neighborhood sear...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2010-03, Vol.22 (2), p.314-325
Main Authors: Hewitt, Mike, Nemhauser, George L, Savelsbergh, Martin W.P
Format: Article
Language:English
Subjects:
Algorithms
Computer networks
fixed-charge network flow
Heuristic
Heuristic programming
Information networks
Integer programming
Linear programming
local search
Mathematical optimization
Mathematical programming
Methods
multicommodity
Network flow problem
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We develop a solution approach for the fixed-charge network flow (FCNF) problem that produces provably high-quality solutions quickly. The solution approach combines mathematical programming algorithms with heuristic search techniques. To obtain high-quality solutions, it relies on neighborhood search with neighborhoods that involve solving carefully chosen integer programs derived from the arc-based formulation of FCNF. To obtain lower bounds, the linear programming relaxation of the path-based formulation of FCNF is used and strengthened with cuts discovered during the neighborhood search. The solution approach incorporates randomization to diversify the search and learning to intensify the search. Computational experiments demonstrate the efficacy of the proposed approach.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1090.0348