- Turkish Journal of Mathematics and Computer Science
- Vol: 10 Special Issue
- On Surrogate Dual Search Method for Minimum-Cost Flow Problems
On Surrogate Dual Search Method for Minimum-Cost Flow Problems
Authors : Hande AKDEMİR, Ayşe SAKALLIOĞLU
Pages : 107-116
View : 5 | Download : 4
Publication Date : 2018-12-29
Article Type : Other
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 (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 (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