Title:	Complexity certification of B&B-based MILP and MIQP solvers
DNr:	LiU-compute-2023-22
Project Type:	LiU Compute
Principal Investigator:	Shamisa Shoja <shamisa.shoja@liu.se>
Affiliation:	Linköpings universitet
Duration:	2023-06-21 – 2025-07-01
Classification:	20202
Keywords:

Abstract

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.