Average-case proximity for integer optimisation

整数优化的平均情况接近度

• 批准号: EP/Y032551/1
• 负责人: Iskander Aliev
• 金额: $ 7.97万
• 依托单位: CARDIFF UNIVERSITY
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY032551%2F1
• 关键词: Average; case; proximity; integer; optimisation

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.

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