Next Generation of Algorithms for Mixed Integer Linear Programming (MILP)

点击翻译按钮获取中文摘要

(Numerical) optimization problems lie at the heart of many modern applications in artificial intelligence (AI), machine learning (ML), and computer science (CS) in general. Crucially many of these problems can be naturally translated into only a handful of very powerful frameworks. One of the most prominent such frameworks is mixed integer linear programming (MILP), which has long developed into an invaluable tool for commercial and academic applications across a wide range of industries and research areas. For instance, according to HG insights (https://discovery.hgdata.com/), the IBM ILOG Suite, which contains the MILP solver CPLEX, is used by 2953 companies in the USA of which more than 1000 have revenues above 1b USD.The fact that so many numerical optimization problems can be naturally translated into (different fragments/classes of) MILP has made MILP invaluable for the theoretical and practical analysis and solution of numerical optimization problems. Indeed, MILP has long become an important part of the algorithmic toolbox for researchers in AI, ML, and TCS, since a translation into MILP is often the only way to analyse the complexity of their numerical optimization problems. Moreover, the wide availability of surprisingly efficient academic and commercial MILP solvers means that a translation into MILP is often the easiest, most efficient, and sometimes even the only known way to solve many real-world optimization problems in practice.Despite all this, our understanding of the fine-grained complexity, a.k.a. the parameterized complexity (PC), of MILP is still only in its infancy. This is in stark contrast to the situation for related non-numerical decision problems such as Boolean satisfiability (SAT) and constraint satisfaction (CSP), where the introduction of PC has led to an almost comprehensive understanding of the complexity of these problems under a wide variety of restrictions. There are two main reasons for the lack of our understanding of the PC of MILP. First MILP is an extremely challenging computational problem requiring very different tools and algorithmic techniques, than non-numerical problems such as SAT and CSP that have been the traditional focus of PC and TCS. Second the tools required for the adequate definition of tractable classes for MILP have only recently been developed by the PC community.This situation has, however, recently started to change with my collaborators and me laying the foundations towards the study of the PC of MILP by pioneering the analysis of MILP in terms of graphical representations of the constraint matrix. Our initial study, which focuses solely on decompositional methods and parameters, has already been picked up by several leading research groups and led to the development of novel algorithmic techniques for MILP. Notably, the obtained results have also resulted in the development of novel algorithms and various algorithmic breakthroughs for combinatorial problems in areas such as scheduling, stringology and social choice, and the travelling salesman problem.Building upon these promising initial results, the overarching vision of this project is to obtain a comprehensive understanding about which structural and numerical properties of MILP instances are responsible for computational hardness or tractability. Towards this aim we will develop novel ways to measure the structural and numerical properties of MILP instances, in terms of so called parameters, and we will then analyse the impact of these parameters on the complexity of MILP using the framework of PC.The main outcomes of this project will be novel and very general tractable classes as well as novel algorithmic upper bound and lower bound techniques for MILP that will have far-reaching consequences for a wide range of optimization problems and will potentially also influence the future development of academic and commercial MILP solvers.