Parallel Domain-Decomposition Algorithms for Complexity Certification of Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
When implementing model predictive control (MPC) for hybrid systems with a linear or a quadratic performance measure, a mixed-integer linear program (MILP) or a mixed-integer quadratic program (MIQP) needs to be solved, respectively, at each sampling instant. Recent work has introduced the possibility to certify the computational complexity of branch-and-bound (B&B) algorithms when solving MILP and MIQP problems formulated as multi-parametric MILPs (mp-MILPs) and mp-MIQPs. Such a framework allows for computing the worst-case computational complexity of standard B&B-based MILP and MIQP solvers, quantified by metrics such as the total number of LP/QP iterations and B&B nodes. These results are highly relevant for real-time hybrid MPC applications. In this paper, we extend this framework by developing parallel, domain-decomposition versions of the previously proposed algorithm, allowing it to scale to larger problem sizes and enable the use of high-performance computing (HPC) resources. Furthermore, to reduce peak memory consumption, we introduce two novel modifications to the existing (serial) complexity certification framework, integrating them into the proposed parallel algorithms. Numerical experiments show that the parallel algorithms significantly reduce computation time while maintaining the correctness of the original framework.
Code (0)
등록된 구현이 없습니다.
Tasks
Model Predictive ControlSimilar Papers 제목 키워드 기반
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
We study $\textit{sparse singular value certificates}$ for random rectangular matrices. If $M$ is an $n \times d$ matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can cer…
A massively parallel multi-level approach to a domain decomposition method for the optical flow estimation with varying illumination
We consider a variational method to solve the optical flow problem with varying illumination. We apply an adaptive control of the regularization parameter which allows us to preserve the edges and fine features of the co…
Optical Flow EstimationParallel and Streaming Algorithms for K-Core Decomposition
The $k$-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate $k$-…
Breaking Boundaries: Distributed Domain Decomposition with Scalable Physics-Informed Neural PDE Solvers
Mosaic Flow is a novel domain decomposition method designed to scale physics-informed neural PDE solvers to large domains. Its unique approach leverages pre-trained networks on small domains to solve partial differential…
scientific discoveryA Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
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 applica…
Model Predictive Control