Combining Exact and Heuristic Approaches for the Fixed Charge Network Flow Problem
Mike, Hewitt, George Nemhauser, and Martin Savelsbergh
School of Industrial and Systems Engineering
Georgia Institute of Technology
Abstract
Many local search algorithms for hard combinatorial optimization problems only consider neighborhoods
that can be searched in polynomial-time. However, with current technology, it is now possible to search
neighborhoods efficiently by solving small to medium sized integer programs. To demonstrate the
viability of this approach to obtaining provably good solutions quickly to large instances of NP-hard
problems, we have focused on a local search algorithm for the Fixed Charge Network Flow (FCNF) Problem
using neighborhoods that involve solving carefully chosen integer programs. The motivation for our
approach has been to answer the question “If I need a provably good solution to a large instance of the
FCNF and only have, say, 15 minutes of computing time, what should I do?” To obtain good primal
solutions, we have considered neighborhoods that involve a subset of commodities, nodes, or arcs, and we
have developed methods to choose the specific neighborhood. We've experimented with simple methods that
choose randomly to methods that rely on mathematical programming concepts, such as complementary
slackness. To obtain tight lower bounds, we have developed a lagrangean dual decomposition scheme that
involves solving integer programs as subproblems, in contrast to schemes that use easy to solve
subproblems that yield weak bounds. Using CPLEX as our benchmark and a set of randomly generated
instances of varying sizes, we have seen that our heuristic consistently produces better solutions in the
given time frame. In fact, our solutions are often 10-15% better than what CPLEX produces in 15 minutes
to 24 hours, and sometimes CPLEX can not even find a feasible solution. Parallelizing our local search
yields further improvements.