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.
Citation
HAW Hamburg, Department of Mechanical Engineering, Berliner Tor 21, D-20099 Hamburg, ivo.nowak@haw-hamburg.de, december/2015
Article
View Column Generation based Alternating Direction Methods for solving MINLPs