@misc{HelmbergRendl, author = {Helmberg, Christoph and Rendl, Franz}, title = {A Spectral Bundle Method for Semidefinite Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3067}, number = {SC-97-37}, abstract = {A central drawback of interior point methods for semidefinite programs is their lack of ability to exploit problem structure in cost and coefficient matrices. This restricts applicability to problems of small dimension. Typically semidefinite relaxations arising in combinatorial applications have sparse and well structured cost and coefficient matrices of huge order. We present a method that allows to compute acceptable approximations to the optimal solution of large problems within reasonable time. Semidefinite programming problems with constant trace on the primal feasible set are equivalent to eigenvalue optimization problems. These are convex nonsmooth programming problems and can be solved by bundle methods. We propose to replace the traditional polyhedral cutting plane model constructed by means of subgradient information by a semidefinite model that is tailored for eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficacy of the approach on combinatorial examples.}, language = {en} } @misc{HelmbergRendl, author = {Helmberg, Christoph and Rendl, Franz}, title = {Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cuttings Planes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2012}, number = {SC-95-35}, abstract = {We present computational experiments for solving quadratic \$(0,1)\$ problems. Our approach combines a semidefinite relaxation with a cutting plane technique, and is applied in a Branch and Bound setting. Our experiments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 binary variables, in a routine manner.}, language = {en} } @misc{HelmbergRendlWeismantel, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2031}, number = {SC-95-37}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} } @misc{HelmbergRendlWeismantel, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {A Semidefinite Programming Approach to the Quadratic Knapsack Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2211}, number = {SC-96-10}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} }