Combining Surrogate Duality with Improving Sequences for Integer Programming

Recently a new technique for solving pure integer programming problems has been suggested It consists on building a sequence of Lagrangean duals that progressively reduces the duality gap and, in a finite number of steps, converges to the optimal value of the original problem. The technique has, however, a drawback: to produce a new dual, sometimes, an enumeration step is needed thus deteriorating the performance of the procedure. In this note We study the conditions under which surrogate duality can play a role in helping on this situation. By using some results connecting Lagrangean and surrogate duality in integer programming, we will be able to conclude that a combined Lagrangean-surrogate approach may be helpful in avoiding some enumeration. We give a numerical example of 2 simple problem where such an improvement occurs.N/