Optimization Online


Column Generation based Alternating Direction Methods for solving MINLPs

Ivo Nowak (ivo.nowak***at***haw-hamburg.de)

Abstract: Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization algorithm), for globally solving quasi-separable nonconvex MINLPs, which is not based on the branch-and-bound approach. The basic idea of ADGO is to restrict the feasible set by an upper bound of the objective function and to check via a (column generation based) globally convergent alternating direction method if the resulting MINLP is feasible or not. Convergence of ADGO to a global solution is shown by using the fact that the duality gap of a general nonconvex projection problem is zero (in contrast to the Lagrangian dual of a general nonconvex program). Furthermore, we describe how ADGO can be accelerated by an inexact sub-problem solver, and discuss modifications to solve large-scale quasi-separable network and black-box optimization problems. Since solving the sub-problems of ADGO is not much more difficult than solving traditional pricing problems, we expect that the computational cost of ADGO is similar to a traditional column generation method.

Keywords: global optimization, alternating direction method, column generation, branch-and-cut, mixed-integer nonlinear programming, network optimization, surrogate optimization

Category 1: Global Optimization (Theory )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: HAW Hamburg, Department of Mechanical Engineering, Berliner Tor 21, D-20099 Hamburg, ivo.nowak@haw-hamburg.de, december/2015

Download: [PDF]

Entry Submitted: 12/05/2015
Entry Accepted: 12/05/2015
Entry Last Modified: 09/09/2016

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