The Bundle Method in Combinatorial Optimization

Ilse Fischer (ifischeruni-klu.ac.at)
Gerald Gruber (g.grubercti.ac.at)
Franz Rendl (franz.rendluni-klu.ac.at)
Renata Sotirov (rsotirovuni-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