Optimization Online


The Bundle Method in Combinatorial Optimization

Ilse Fischer (ifischer***at***uni-klu.ac.at)
Gerald Gruber (g.gruber***at***cti.ac.at)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)
Renata Sotirov (rsotirov***at***uni-klu.ac.at)

Abstract: We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods.

Keywords: Bundle Method, Max-Cut, Interior Point Methods

Category 1: Combinatorial Optimization

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Research Report, Univ. Klagenfurt, 2003

Download: [Compressed Postscript]

Entry Submitted: 09/17/2003
Entry Accepted: 09/18/2003
Entry Last Modified: 09/17/2003

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