Generalized Networks: The Theory of Preprocessing and an Empirical Analysis
Jeffery L. Kennington, Karen R. Lewis
INFORMS Journal on Computing · 2004 · Volume 16 · Issue 2
Abstract
The idea of preprocessing a linear program with the goal of eliminating constraints or columns is well established. The default setting for CPLEX is to apply preprocessing prior to application of any of its four solvers. In this investigation, a set of preprocessing procedures is developed for the special case of a generalized network flow problem. Some procedures involve adding or replacing arcs to eliminate a node. These procedures all produce an optimal basic feasible solution and optimal dual solution to the original problem. In an empirical analysis, our generalized network preprocessor ran approximately seven times faster than the CPLEX 6.5.3 preprocessor, resulting in an overall solution time reduction of over 20%.
Keywords
generalized networks, network flow algorithms, network flow theory, preprocessing, presolve
Enable JavaScript for citation tools and additional paper interactions.