- 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
- Hits: 844
- Visitors: 939
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|