A trust region method for the solution of the surrogate dual in integer programming

Title: A trust region method for the solution of the surrogate dual in integer programming
Creator: Boland, N.; Eberhard, A. C.; Tsoukalas, A.
Relation: Journal of Optimization Theory and Applications Vol. 167, Issue 2, p. 558-584
Publisher Link: http://dx.doi.org/10.1007/s10957-014-0681-9
Publisher: Springer
Resource Type: journal article
Date: 2015
Description: 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.
Subject: surrogate dual; integer programming; trust region methods; nonsmooth optimization
Identifier: http://hdl.handle.net/1959.13/1338172
Identifier: uon:27962
Identifier: ISSN:0022-3239
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format