Surrogate constraint applications to network models in operations research

The relaxation by aggregation of multiple constraints into a single surrogate constraint is called surrogate relaxation. 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 provides a lower bound for the optimal objective value of the minimization problem and enlarges the feasible region. This bound is tighter than the Lagrangian lower bound, therefore it can give a better approximation. In some 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 surrogate constraint methods can be used. In this study, relaxation strategies and choosing the appropriate parameters are discussed on minimum-cost flow problems which are to find the feasible flows from the source nodes to the sink nodes with minimum cost. In addition, a heuristic that reduces the number of constraints, and uses multiple surrogate constraints, and is based on bisection algorithms, is developed.