Ivo Nowak – Optimization Online

Column Generation based Alternating Direction Methods for solving MINLPs

Published: 2015/12/05, Updated: 2016/09/09

(Mixed) Integer Nonlinear Programming, Global Optimization Theory, Parallel Algorithms alternating direction method, branch-and-cut, column generation, global optimization, mixed-integer nonlinear programming, network optimization, surrogate optimization

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 … Read more

Lagrangian Smoothing Heuristic for Max-Cut

Published: 2002/07/15, Updated: 2002/07/16

Hernán Alperin

Ivo Nowak

Combinatorial Optimization approximation methods and heuristics, combinatorial optimization, homotopy, nonconvex optimization, pathfollowing, quadratic programming, semidefinite programming

This paper presents smoothing heuristics for an NP-hard combinatorial problem based on Lagrangian relaxation. We formulate the Lagrangian dual for this nonconvex quadratic problem and propose eigenvalue nonsmooth unconstrained optimization to solve the dual problem with bundle or subgradient methods. Derived heuristics are considered to obtain good primal solutions through pathfollowing methods using a projected … Read more