Polyhedral Outer-Approximations for MISOCP: Geometry and Cutting Planes

Abstract

Mixed-integer second-order cone programs are commonly solved by polyhedral outer approximation (OA), which iteratively strengthens a linear relaxation of the conic feasible region through cutting planes. We study how such approximations can be constructed more efficiently. First, we analyze the marginal contribution of a newly generated cut relative to cuts already present in the relaxation. Using violation- and volume-based measures, we show that this contribution decreases at least as fast as linearly as the new supporting direction approaches an existing one. Motivated by this geometric analysis, we develop a cut-generation strategy that balances separation depth with angular novelty and admits closed-form constructions. Second, we introduce a progressive-integrality OA framework that proceeds from an LP relaxation through partially integral relaxations before reaching the full MILP, thereby using inexpensive early iterations to strengthen the approximation before later mixed-integer solves. Computational experiments on CBLIB instances and large-scale AC unit-commitment models demonstrate complementary benefits from the proposed cut strategy and progressive integrality, substantially reducing the computational effort of outer approximation.