Optimization Online


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

N Boland(Natashia.Boland***at***newcastle.edu.au)
A Eberhard(andy.eberhard***at***rmit.edu.au)
A Tsoukalas(maurostsouk***at***googlemail.com)

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, 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.

Keywords: Surrogate Dual, Integer Programming, Trust Region

Category 1: Combinatorial Optimization (Other )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Submitted to JOTA

Download: [PDF]

Entry Submitted: 02/25/2014
Entry Accepted: 02/25/2014
Entry Last Modified: 02/25/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society