On Surrogate Dual Search Method for Minimum-Cost Flow Problems

Authors : Hande AKDEMİR, Ayşe SAKALLIOĞLU

Pages : 107-116

View : 44 | Download : 13

Publication Date : 2018-12-29

Article Type : Conference Paper

Abstract :In this paper, we study on surrogate dual formulations which generate relaxations by assembling multiple constraints into a single surrogate constraint. Similar to the Lagrangian dual search methods for integer programming, 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 insert ignore into journalissuearticles values(primal); problem and provides a lower bound for the optimal objective value. This bound is tighter than the Lagrangian lower bound. In case there exists a duality gap, the conventional surrogate dual search method fails to find the optimal solutions of the primal problem. In order to eliminate this issue, nonlinear $p-$norm surrogate constraint methods can be used. To illustrate how we choose the initial multiplier vector or the parameter $p$, we argue on minimum-cost flow problems, in which we find the feasible flow from the source nodes to the sink nodes with minimum cost. Some integer programming problems, such as transportation problems, transshipment problems, assignment problems, shortest path problems insert ignore into journalissuearticles values(with or without time windows);, and maximal flow problems can be seen those type of problems. Furthermore, we consider arrangements to solve those network problems which cannot be solved with the conventional surrogate dual method.
Keywords : Surrogate dual search, Lagrangian dual search, Duality gap, Integer programming, Minimum cost flow problems

ORIGINAL ARTICLE URL