×

zbMATH — the first resource for mathematics

Subgradient based outer approximation for mixed integer second order cone programming. (English) Zbl 1242.90130
Lee, Jon (ed.) et al., Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17–21, 2008. New York, NY: Springer (ISBN 978-1-4614-1926-6/hbk; 978-1-4614-1927-3/ebook). The IMA Volumes in Mathematics and its Applications 154, 41-59 (2012).
Summary: This paper deals with outer approximation based approaches to solve mixed integer second order cone programs. Thereby the outer approximation is based on subgradients of the second order cone constraints. Using strong duality of the subproblems that are solved during the algorithm, we are able to determine subgradients satisfying the KKT optimality conditions. This enables us to extend convergence results valid for continuously differentiable mixed integer nonlinear problems to subdifferentiable constraint functions. Furthermore, we present a version of the branch-and-bound based outer approximation that converges when relaxing the convergence assumption that every SOCP satisfies the Slater constraint qualification. We give numerical results for some application problems showing the performance of our approach.
For the entire collection see [Zbl 1230.90005].

MSC:
90C11 Mixed integer programming
90C25 Convex programming
Software:
filterSQP; Bonmin
PDF BibTeX XML Cite
Full Text: DOI