We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual’s value is proposed, in which numerical experiments prove to be advantageous. A proof of convergence is given and numerical tests show that the method performance is better than a state of the art subgradient solver. Incorporation of the surrogate dual value as a cut added to the integer program is shown to greatly reduce solution times of a standard commercial solver on a specific class of problems.

Surrogate dual · Integer programming · Trust regions methods · Nonsmooth optimization
Journal of Optimization Theory and Applications
Department of Technology and Operations Management

Boland, N., Eberhard, A, & Tsoukalas, A.T. (2014). A trust region method for the solution of the surrogate dual in integer programming. Journal of Optimization Theory and Applications, 167, 558–584. Retrieved from http://hdl.handle.net/1765/131542