On Surrogate Dual Search Method for Minimum-Cost Flow Problems

Abstract

In this paper, we study on surrogate dual formulations which generate relaxations by assemblingmultiple constraints into a single surrogate constraint. Similar to the Lagrangian dual search methods for integerprogramming, the conventional surrogate dual method utilizes an auxiliary linear programming problem for updating the multiplier vector. The technique enlarges the feasible region of the original (primal) problem and providesa lower bound for the optimal objective value. This bound is tighter than the Lagrangian lower bound. In case thereexists a duality gap, the conventional surrogate dual search method fails to find the optimal solutions of the primalproblem. In order to eliminate this issue, nonlinear p−norm surrogate constraint methods can be used. To illustratehow we choose the initial multiplier vector or the parameter p, we argue on minimum-cost flow problems, in whichwe find the feasible flow from the source nodes to the sink nodes with minimum cost. Some integer programmingproblems, such as transportation problems, transshipment problems, assignment problems, shortest path problems(with or without time windows), and maximal flow problems can be seen those type of problems. Furthermore, weconsider arrangements to solve those network problems which cannot be solved with the conventional surrogatedual method.