Average-case proximity for integer optimisation

最优化考虑整数值变量的线性和非线性优化问题。它已成功应用于制造业、交通运输、金融、电信，以及最近的数据科学和机器学习。这个为期一年的研究项目集中在整数优化理论中的一个中心问题，即邻近问题。近似问题起源于整数线性规划（ILP），整数优化的经典子领域。众所周知，线性规划（LP）问题是多项式时间可解的。相反，ILP问题是NP难的。LP解算器可以处理数百万个变量，最多可以处理数千个极限ILP解算器。在实践中，ILP问题通常通过一系列LP松弛来解决。在这样的序列中的LP松弛的最优解提供了原始ILP问题的最优解的近似。邻近问题要求估计这种近似的质量。大多数已知的接近边界适用于任意ILP问题，我们称之为最坏情况。最坏的情况有很强的理论局限性。对于某些特殊的ILP问题，我们认为这是“罕见的”，已知的最坏情况下的接近边界是接近最优的。一个“典型的”ILP问题的接近，称为平均情况下的接近，仍然基本上是未知的。研究平均情况接近度是一个非常有前途的研究方向。背包的设置证明了这一说法。背包问题是一个特殊的但基本的ILP问题，它由一个线性丢番图方程决定。例如，理论计算机科学中的经典无界子集和问题可以用背包形式表示。最近发现，平均而言，背包的邻近边界比最坏情况下的边界要好得多。这个项目的主要目标是研究平均情况下的接近性，并在一般情况下获得强估计。在这项工作中，我们将考虑几个有趣的问题，如估计接近任意点的背包多面体，这是相关的非线性整数优化。几何上，接近估计可以使用从某个多面体P的顶点到P中最近的整数点的距离来推导。因此，我们的工作也将数学优化与离散和凸几何连接起来。在计算方面，我们预计，我们的研究结果将导致开发动态规划算法，提高预期的运行时间。

Integer optimisation considers linear and non-linear optimisation problems with integer-valued variables. It has been successfully used in manufacturing industries, transportation, finance, telecommunications, and, more recently, data science and machine learning. This one-year research project focuses on a central problem in the theory of integer optimisation, the proximity problem. The proximity problem originates in integer linear programming (ILP), the classical subfield of integer optimisation. It is well-known that linear programming (LP) problems are polynomial-time solvable. In contrast, ILP problems are NP-hard. LP solvers can work with millions of variables, and thousands at best limit ILP solvers. In practice, ILP problems are often solved via a sequence of LP relaxations. An optimal solution of an LP relaxation in such a sequence provides an approximation for an optimal solution of the original ILP problem. The proximity problem asks to estimate the quality of such approximations. Most of the known proximity bounds apply to arbitrary ILP problems; we call it the worst-case scenario. The worst-case scenario has strong theoretical limitations. For certain special ILP problems, which we believe are "rare", the known worst-case proximity bounds are nearly optimal. The proximity of a "typical" ILP problem, referred to as the average-case proximity, remains essentially unknown. Investigating the average-case proximity is a very promising direction of research. The knapsack setting justifies this claim. A knapsack problem is a special yet fundamental ILP problem determined by a single linear Diophantine equation. For instance, the classical unbounded subset sum problem in theoretical computer science can be expressed in the knapsack form. It has been recently discovered that, on average, proximity bounds are drastically better for knapsacks than in the worst-case scenario. This project's main goal is to study the average-case proximity and obtain strong estimates in the general setting. In this work, we will consider several interesting questions, such as estimating proximity for arbitrary points in knapsack polyhedra which is relevant for nonlinear integer optimisation. Geometrically, proximity estimates can be derived using the distance from a vertex of a certain polyhedron P to its nearest integer point in P. Hence our work will also connect mathematical optimisation with discrete and convex geometry. On a computational side, we anticipate that our results will lead to developing dynamic programming algorithms with improved expected running time.