A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming

N. Boland (), A. C. Eberhard () and A. Tsoukalas ()
Additional contact information
N. Boland: University of Newcastle
A. C. Eberhard: RMIT
A. Tsoukalas: RMIT

Journal of Optimization Theory and Applications, 2015, vol. 167, issue 2, No 8, 558-584

Abstract: Abstract 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; Primary 90C11; 90C25; Secondary 90C08 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-014-0681-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:167:y:2015:i:2:d:10.1007_s10957-014-0681-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-014-0681-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().