Average-case proximity for 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.