EPSRC logo

Details of Grant 

EPSRC Reference: EP/Y032551/1
Title: Average-case proximity for integer optimisation
Principal Investigator: Aliev, Professor I
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Sch of Mathematics
Organisation: Cardiff University
Scheme: Standard Research - NR1
Starts: 01 June 2024 Ends: 31 May 2025 Value (£): 62,529
EPSRC Research Topic Classifications:
Algebra & Geometry Mathematical Aspects of OR
Non-linear Systems Mathematics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
20 Nov 2023 EPSRC Mathematical Sciences Small Grants and Prioritisation Panel November 2023 Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.cf.ac.uk