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, which numerical experiments prove to be advantageous. A proof of convergence is given and numerical tests show that the method’s performance is superior to a state-of-the-art subgradient solver.
Citation
Submitted to JOTA