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

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.