Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem

Title: Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem
Creator: Hewitt, Mike; Nemhauser, George L.; Savelsbergh, Martin W. P.
Relation: INFORMS Journal on Computing Vol. 22, Issue 2, p. 314-325
Publisher Link: http://dx.doi.org/10.1287/ijoc.1090.0348
Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
Resource Type: journal article
Date: 2010
Description: 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.
Subject: local search; integer programming; fixed-charge network flow; multicommodity
Identifier: http://hdl.handle.net/1959.13/937699
Identifier: uon:12603
Identifier: ISSN:1091-9856
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format