Mixed integer second order cone programming

Friday, November 21, 2008 - 10:30am - 11:15am
EE/CS 3-180
Sarah Drewes (TU Darmstadt)
We present two algorithms to solve mixed integer second-order cone programming problems: a branch-and-cut method and an outer approximation based branch-and-bound approach. We use different techniques for the generation of linear and convex quadratic cuts and investigate their impact on the branch-and-cut procedure. The presented outer approximation based branch-and-bound algorithm is an extension of the well-known outer approximation based branch-and-bound approach for continuous differentiable problems to subdifferentiable constraint functions. Convergence can be guaranteed, since the subgradients, that satisfy the KKT conditions, can be identified using the dual solution of the occurring second order cone problems. Computational results for test problems and real world applications are given.
MSC Code: