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.