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.

Knowledge:

The project will greatly increase our understanding about the complexity of MILP and related numerical optimization as well as combinatorial decision problems. The obtained algorithmic techniques (both upper bound and lower bound techniques) will provide novel insights that will guide and inspire future research on the subject. The obtained tractable classes for MILP (as well the complementary complexity lower bounds) will become an important part of the algorithmic toolbox of researchers in PC, AI, ML, and CS in general allowing them to analyse the complexity of computational problems in their area of expertise. For instance, many of the most important open problems in social choice and scheduling, are directly related to the complexity of certain classes of MILP (see, e.g., the recent survey articles titled "Parameterized complexity of machine scheduling: 15 open problems" and "Parameterized Algorithmics for computational social choice: Nine research challenges"). Moreover, already the initial results obtained by the PI and the Project Partner (PP) have allowed the PC community to deal with problems in stringology and social choice, scheduling, and the travelling salesman problem that were previously out-of-reach for a PC analysis. This has recently led to a significant amount of attention from the PC community, who invited the PI and the PP to give talks on the subject at recent Shonnan (No. 144) and Dagstuhl (No.19041) seminars.

We will also develop novel ways to measure the structure of input instances that will be applicable to the PC analysis of a wide range of computational problems beyond MILP and will therefore allow PC to venture into novel application areas.

Finally, an important aspect of the project is to build a bridge between researchers working on the theoretical foundations of MILP and MILP solver experts. This will be largely beneficial for both communities. First, researchers working on the theoretical foundations of MILP can draw inspiration from the approaches and techniques responsible for the surprising efficiency of MILP solvers in practice. Second, MILP solver experts can work closely with theoreticians to find the best ways how to incorporate the ideas behind the very powerful and general theoretical techniques into their solvers.

Economy, Society, and People:

MILP solvers have become a huge commercial success being used as an analysis tool for a wide range of industries such as technology, manufacturing, finance, business services, transportation, and retail. In the US alone CPLEX, a MILP solver which is part of the IBM ILOG Suite developed by IBM, is used by over 2900 companies of which more than 1000 have revenues above 1 billion USD. Therefore any improvement to the efficiency of MILP solvers can have a large impact on the economy. In particular, any such improvement will not only reduce the time required to obtain high quality solutions but also increase the quality of the obtained solutions. This will allow those companies to provide higher quality products and services to their customers, while at the same time reducing costs and environmental impact. This in turn will have a large impact on the society and people by increasing the quality of life and decreasing the impact on the environment.