Mixed integer second order cone programming
Presenter
November 21, 2008
Keywords:
- Branch-and-cut, Branch-and-bound
MSC:
- 90C57
Abstract
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.