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.