Optimization Online


Lagrangian Smoothing Heuristic for Max-Cut

HernŠn Alperin (alpe***at***mathematik.hu-berlin.de)
Ivo Nowak (ivo***at***mathematik.hu-berlin.de)

Abstract: 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 gradient algorithm. Starting points are drawn using several sampling techniques that use randomization and eigenvectors. The proposed method turns out to be competitive with the most recent ones. The idea presented here is generic and can be generalized, to all problems where convex Lagrangian relaxation can be applied. Furthermore, to the best of our knowledge, this is the first time that a Lagrangian heuristic is combined with pathfollowing techniques.

Keywords: semidefinite programming, quadratic programming, combinatorial optimization, non-convex programming, approximation methods and heuristics, pathfollowing, homotopy

Category 1: Combinatorial Optimization

Citation: technical report NR-2002-6, May 2002. Institut fŁr Mathematik, Humboldt Universitšt zu Berlin, Germany.

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 07/15/2002
Entry Accepted: 07/15/2002
Entry Last Modified: 07/16/2002

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 Programming Society