EPSRC Reference: 
EP/Y032551/1 
Title: 
Averagecase proximity for integer optimisation 
Principal Investigator: 
Aliev, Professor I 
Other Investigators: 

Researcher CoInvestigators: 

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 
Nonlinear Systems Mathematics 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Integer optimisation considers linear and nonlinear optimisation problems with integervalued variables. It has been successfully used in manufacturing industries, transportation, finance, telecommunications, and, more recently, data science and machine learning. This oneyear 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 wellknown that linear programming (LP) problems are polynomialtime solvable. In contrast, ILP problems are NPhard. 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 worstcase scenario. The worstcase scenario has strong theoretical limitations. For certain special ILP problems, which we believe are "rare", the known worstcase proximity bounds are nearly optimal. The proximity of a "typical" ILP problem, referred to as the averagecase proximity, remains essentially unknown.
Investigating the averagecase 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 worstcase scenario.
This project's main goal is to study the averagecase 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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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 