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

下一代混合整数线性规划 (MILP) 算法

• 批准号: EP/V00252X/1
• 负责人: Sebastian Ordyniak
• 金额: $ 27.51万
• 依托单位: University of Leeds
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV00252X%2F1
• 关键词: Next; Generation; Algorithms; Mixed; Integer

(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.

（数值）优化问题是人工智能（AI），机器学习（ML）和计算机科学（CS）中许多现代应用的核心。至关重要的是，这些问题中的许多都可以自然地转化为少数非常强大的框架。其中最突出的框架之一是混合整数线性规划（MILP），它已经发展成为广泛的行业和研究领域的商业和学术应用的宝贵工具。例如，根据HG insights（https：//discovery.hgdata.com/），IBM的MILP套件，其中包含MILP求解器CPLEX，被美国2953家公司使用，其中超过1000家公司的收入超过10亿美元。事实上，如此多的数值优化问题可以自然地转化为（不同的片段/类）MILP，这使得MILP对于数值优化问题的理论和实践分析和解决方案非常宝贵。事实上，MILP长期以来一直是AI，ML和TCS研究人员算法工具箱的重要组成部分，因为翻译成MILP通常是分析其数值优化问题复杂性的唯一方法。此外，学术界和商业界的MILP求解器都有着惊人的效率，这意味着将MILP转换成MILP通常是解决许多实际优化问题的最简单、最有效的方法，有时甚至是唯一已知的方法。MILP的参数化复杂度（PC）仍然只是在它的婴儿期。这与相关的非数值决策问题，如布尔可满足性（SAT）和约束满足（CSP）的情况形成鲜明对比，其中PC的引入导致了对这些问题的复杂性的几乎全面的理解。我们对MILP的PC缺乏了解主要有两个原因。首先，MILP是一个非常具有挑战性的计算问题，需要非常不同的工具和算法技术，而非数值问题，如SAT和CSP，一直是PC和TCS的传统焦点。第二，所需的工具，以充分定义的听话的类MILP最近才被开发的PC community.This situation has，然而，最近开始改变与我的合作者和我奠定了基础，对PC的研究MILP的开拓分析MILP在图形表示的约束矩阵。我们最初的研究，只集中在分解方法和参数，已经拿起了几个领先的研究小组，并导致了新的算法技术的MILP的发展。值得注意的是，所获得的结果也导致了新的算法的发展和各种算法的突破，用于诸如调度、弦学和社会选择以及旅行推销员问题等领域的组合问题。该项目的总体目标是全面了解MILP实例的哪些结构和数值特性对计算硬度或易处理性。为了实现这一目标，我们将开发新的方法来测量MILP实例的结构和数值特性，在所谓的参数方面，然后，我们将使用PC的框架分析这些参数对MILP复杂性的影响。该项目的主要成果将是新颖的和非常一般的易处理的类以及新颖的MILP算法上界和下界技术，这将具有深远的意义。达到广泛的优化问题的后果，并可能也会影响学术和商业MILP求解器的未来发展。

项目成果

Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach

解决简单时态问题中的不一致：参数化方法

• 发表时间: 2022
• 期刊: Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
• 作者: Dabrowski K.K.

Parameterized Algorithms for MILPs with Small Treedepth

• DOI: 10.1609/aaai.v35i14.17454
• 发表时间: 2019-12
• 作者: Cornelius Brand;Martin Kouteck'y;S. Ordyniak

Solving infinite-domain CSPs using the patchwork property

使用拼凑属性求解无限域 CSP

• DOI: 10.1016/j.artint.2023.103880
• 发表时间: 2023
• 期刊: Artificial Intelligence
• 影响因子: 14.4
• 作者: Dabrowski K

Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers

计算机科学中的图论概念 - 第 48 届国际研讨会，WG 2022，德国蒂宾根，2022 年 6 月 22-24 日，修订后的精选论文

• DOI: 10.1007/978-3-031-15914-5_15
• 发表时间: 2022
• 作者: Eiben E

Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

2023 年年度 ACM-SIAM 离散算法研讨会 (SODA) 论文集

• DOI: 10.1137/1.9781611977554.ch42
• 发表时间: 2023
• 作者: Thiery T