A Unified Early Termination Technique for Primal-Dual Algorithms in Mixed Integer Conic Programming

Yuwen Chen, Catherine Ning and Paul Goulart

@article{CNG:2023,
  author = {Chen, Yuwen and Ning, Catherine and Goulart, Paul},
  title = {A Unified Early Termination Technique for Primal-Dual Algorithms in Mixed Integer Conic Programming},
  journal = {IEEE Control Systems Letters},
  year = {2023},
  volume = {7},
  pages = {2803-2808},
  url = {https://ieeexplore.ieee.org/abstract/document/10160117},
  doi = {10.1109/LCSYS.2023.3289062}
}

We propose an early termination technique for mixed integer conic programming within branch-and-bound based solvers. Our approach generalizes previous early termination results for ADMM-based solvers to a broader class of primal-dual algorithms, including both operator splitting and interior point methods. The complexity for checking early termination is O(n) for each termination check assuming a bounded problem domain. We show that this domain restriction can be relaxed for problems whose data satisfies a simple rank condition, in which case each check requires an O(n^2) solve using a linear system that is factored only once at the root node. We further show how this approach can be used in hybrid model predictive control problems with bounded inputs. Numerical results show that our method leads to a moderate reduction in the computational time required for branch-and-bound conic solvers with interior-point based subsolvers.