Polyhedral Outer Approximation for MISOCP: Geometry and Progressive Integrality
Abstract
Polyhedral outer approximation (OA) is widely used to solve mixed-integer second-order cone programs (MISOCPs) by iteratively strengthening polyhedral relaxations of conic constraints. However, the accumulation of cutting planes can increase the difficulty of solving the resulting mixed-integer linear programs (MILPs), while repeatedly solving these MILPs can be computationally expensive. To address these challenges, we investigate the geometry of supporting cuts and the computational role of integrality in OA. First, we establish theoretical bounds showing that the marginal contribution of a new supporting cut decreases at least linearly as its supporting direction approaches an existing one. Motivated by this analysis, we develop a closed-form cut-generation strategy that balances separation depth and directional diversity. Second, we propose a progressive-integrality OA framework that strengthens the polyhedral approximation through linear programs and partially integral relaxations before solving full MILPs. We theoretically characterize the transfer of cut-induced bound improvements across integrality levels and provide a branch-and-bound interpretation of the framework. Computational experiments on CBLIB instances and large-scale AC unit-commitment models demonstrate substantial improvements over classical OA and direct MISOCP solution, with runtime reductions of up to 62\% relative to classical OA on the reported power-system instances.
Related
- Polyhedral Geometry of Time-to-First-Spike Neural Networks
- DC decompositions and cutting-plane approximation: geometry and complexity
- The geometry of monarch matrix approximation
- Learning Representations through Token Prediction: Geometry, Approximation, and Downstream Guarantees
- Boundary Geometry Determines Optimal Shallow ReLU Approximation under Weighted Coefficient Constraints
BibTeX
@misc{dai2026polyhedral,
title = {{Polyhedral Outer Approximation for MISOCP: Geometry and Progressive Integrality}},
author = {Yongzheng Dai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.10055},
eprint = {2608.10055},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.10055},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polyhedral Outer Approximation for MISOCP: Geometry and Progressive Integrality
AU - Yongzheng Dai
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2608.10055
UR - https://arxiv.org/abs/2608.10055
AB - Polyhedral outer approximation (OA) is widely used to solve mixed-integer second-order cone programs (MISOCPs) by iteratively strengthening polyhedral relaxations of conic constraints. However, the accumulation of cutting planes can increase the difficulty of solving the resulting mixed-integer linear programs (MILPs), while repeatedly solving these MILPs can be computationally expensive. To address these challenges, we investigate the geometry of supporting cuts and the computational role of integrality in OA. First, we establish theoretical bounds showing that the marginal contribution of a new supporting cut decreases at least linearly as its supporting direction approaches an existing one. Motivated by this analysis, we develop a closed-form cut-generation strategy that balances separation depth and directional diversity. Second, we propose a progressive-integrality OA framework that strengthens the polyhedral approximation through linear programs and partially integral relaxations before solving full MILPs. We theoretically characterize the transfer of cut-induced bound improvements across integrality levels and provide a branch-and-bound interpretation of the framework. Computational experiments on CBLIB instances and large-scale AC unit-commitment models demonstrate substantial improvements over classical OA and direct MISOCP solution, with runtime reductions of up to 62\% relative to classical OA on the reported power-system instances.
ER -