Complexity certification of B&B-based MILP and MIQP solvers
||Complexity certification of B&B-based MILP and MIQP solvers|
||Shamisa Shoja <email@example.com>|
||2023-06-21 – 2024-07-01|
In this project, the intention is to scale up the complexity certification method presented in the Licentiate's thesis (https://liu.diva-portal.org/smash/record.jsf?pid=diva2%3A1759253&dswid=-9344) by the PI. For a set of parameters in a parametric mixed-integer linear and quadratic programs (MILPs/MIQPs), this certification method determines the worst-case computational complexity (e.g., the number of nodes or flops) which branch-and-bound (B&B) methods needs to compute a solution. Such worst-case complexity bounds are important to ensure that embedded MILP/MIQP solvers can operate with limited hardware, especially for safety-critical systems (e.g., in real-time hybrid model predictive control applications).
The computations performed by the algorithm can be applied to different subsets of parameters independently, since the computations performed for a set of parameters does not affect the computations performed for another set of parameters. This data parallelism can, hence, be exploited to handle larger problems by letting different workers apply the algorithm on different sets of parameter (domain decomposition). We therefore believe that the algorithm is highly suited for HPC. Moreover, using HPC makes it possible to certify the computational complexity for larger problems which arise in practice.