Funding: NWO Open Competition Domain Science - M-1
Running Period: 2021-2025
Staff: Dr. Matthias Walter
Ph.D. student: Rolf van der Hulst
ABSTRACT
The solution of large-scale practical mixed-integer optimization problems (MIPs) often requires an expert to supplement the solver software with algorithms that supply additional problem information such as heuristics, cutting planes or model reformulations in order to reduce the running time by several orders of magnitude.
The goal of this project is to make solver software smarter in the sense that it will understand the meaning of some of the MIP’s decision variables and constraints as well as their interplay within certain substructures of the problem. By applying this knowledge, the additional problem information can be inferred by the software. Hence, the ordinary user can readily take advantage of many successful MIP solution techniques that were previously only available to experts, which will drastically reduce running times.
To this end, relevant substructures of the MIP must be identified, which is not only a complex task for a human, but also poses a challenging mathematical problem. The innovative idea of this proposal is that this task can be split into two steps. Firstly, network matrices and their transposes, which are part of many problem substructures, will be identified. Secondly, these matrices are utilized in order to identify exploitable substructures while demanding less algorithmic effort and in shorter times.
In a first project phase, new algorithms for finding large network submatrices will be developed. In the second phase, detection algorithms for important substructures will be devised, which makes additional problem information available and admits a significant speed-up of the solver software.