A Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913787140898816 |
|---|---|
| author | Shoja, Shamisa Arnström, Daniel Axehill, Daniel |
| author_facet | Shoja, Shamisa Arnström, Daniel Axehill, Daniel |
| contents | In model predictive control (MPC) for hybrid systems, solving optimization problems efficiently and with guarantees on worst-case computational complexity is critical to satisfy the real-time constraints in these applications. These optimization problems often take the form of mixed-integer linear programs (MILPs) or mixed-integer quadratic programs (MIQPs) that depend on system parameters. A common approach for solving such problems is the branch-and-bound (B&B) method. This paper extends existing complexity certification methods by presenting a unified complexity-certification framework for B&B-based MILP and MIQP solvers, specifically for the family of multi-parametric MILP and MIQP problems that arise in, e.g., hybrid MPC applications. The framework provides guarantees on worst-case computational measures, including the maximum number of iterations or relaxations B&B algorithms require to reach optimality. It systematically accounts for different branching and node selection strategies, as well as heuristics integrated into B&B, ensuring a comprehensive certification framework. By offering theoretical guarantees and practical insights for solver customization, the proposed framework enhances the reliability of B&B for real-time application. The usefulness of the proposed framework is demonstrated through numerical experiments on both random MILPs and MIQPs, as well as on MIQPs arising from a hybrid MPC problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16235 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming Shoja, Shamisa Arnström, Daniel Axehill, Daniel Systems and Control In model predictive control (MPC) for hybrid systems, solving optimization problems efficiently and with guarantees on worst-case computational complexity is critical to satisfy the real-time constraints in these applications. These optimization problems often take the form of mixed-integer linear programs (MILPs) or mixed-integer quadratic programs (MIQPs) that depend on system parameters. A common approach for solving such problems is the branch-and-bound (B&B) method. This paper extends existing complexity certification methods by presenting a unified complexity-certification framework for B&B-based MILP and MIQP solvers, specifically for the family of multi-parametric MILP and MIQP problems that arise in, e.g., hybrid MPC applications. The framework provides guarantees on worst-case computational measures, including the maximum number of iterations or relaxations B&B algorithms require to reach optimality. It systematically accounts for different branching and node selection strategies, as well as heuristics integrated into B&B, ensuring a comprehensive certification framework. By offering theoretical guarantees and practical insights for solver customization, the proposed framework enhances the reliability of B&B for real-time application. The usefulness of the proposed framework is demonstrated through numerical experiments on both random MILPs and MIQPs, as well as on MIQPs arising from a hybrid MPC problem. |
| title | A Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2503.16235 |