An efficient Lagrangean relaxation scheme for linear and integer equal flow problems

Abstract

The equal flow problem is a minimal cost network flow problem with side constraints which state that the amounts of flows on certain pairs of arcs shall coincide. We present a heuristic algorithm for linear as well as integer equal flow problems; it uses Lagrangean dualization with respect to the equal flow side constraints and subgradient optimization to solve the Lagrangean dual problem, which provides lower bounds on the optimal value of the original problem. Embedded in the subgradient procedure is a simple computation which, in the limit, will produce optimal values of the equal flow variables of the linear problem. A heuristic procedure for finding feasible solutions to the equal flow problem, and upper bounds on its optimal value, is obtained by fixing the equal flow variables to the near-optimal values that are available in each iteration and solving the resulting minimal cost network flow problems, which involve the ordinary variables only. The algorithm has been implemented for solving equal flow transportation and transshipment problems, and the computational results indicate that it is highly efficient. © 1998 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint.