A trust region method for the solution of the surrogate dual in integer programming
Journal of Optimization Theory and Applications , Volume 167 p. 558- 584
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.
|Keywords||Surrogate dual · Integer programming · Trust regions methods · Nonsmooth optimization|
|Journal||Journal of Optimization Theory and Applications|
|Organisation||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