This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Hewitt, M. Articles by Savelsbergh, M. W. P.

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

Milton H. Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Milton H. Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Milton H. Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
mhewitt{at}isye.gatech.edu
george.nemhauser{at}isye.gatech.edu
mwps{at}isye.gatech.edu

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.

Key words: local search; integer programming; fixed-charge network flow; multicommodity
History: received August 2008; revised March 2009; accepted May 2009.