Turkish Journal of Mathematics and Computer Science

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

Konular:-

Anahtar Kelimeler:Surrogate dual search,Lagrangian dual search,Duality gap,Integer programming,Minimum-cost flow problems

Özet: 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.

---