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

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

0.00 Avg rating0 Votes
Article ID: iaor20104219
Volume: 22
Issue: 2
Start Page Number: 314
End Page Number: 325
Publication Date: Mar 2010
Journal: INFORMS Journal on Computing
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.