EPSRC Reference: 
EP/J021814/1 
Title: 
Probabilistic Rounding Algorithms for Mathematical Programming 
Principal Investigator: 
Czumaj, Professor A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Warwick 
Scheme: 
Standard Research 
Starts: 
01 November 2012 
Ends: 
31 October 2015 
Value (£): 
360,972

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 

Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
04 Jul 2012

Mathematics Prioritisation Panel Meeting July 2012

Announced


Summary on Grant Application Form 
This proposal falls into the general area of design and analysis of algorithms for discrete optimization problems. Such problems arise in Business Analytics, Management and Computer Sciences and in all Engineering subfields. The variety of models and problems arising in this area is astonishing. Nevertheless the method of choice to solve such problems in practice is some combination of mathematical programming solver (CPLEX, Gurobi, IPOPT) of a relaxed problem where some of the problem constraints (like integrality of decision variables) are relaxed or dropped and some rounding algorithm that converts a relaxed solution into a solution of the original problem. In many cases such practical algorithms work in multiple stages by slowly transforming the relaxed solution into an unrelaxed one while constantly monitoring the quality of the current solution.
On the other hand it was long recognized in the Theoretical Computer Science, Mathematical Programming and Operations Research communities that understanding the performance of various methods to transform an optimal or nearoptimal solution of an "easy" optimization problem into a high quality solution of a "hard" optimization problem is the key to understanding the performance of practical heuristics and design new algorithms to solve hard optimization problems. Such methods are usually called rounding algorithms since they usually transform a fractional solution into an integral one. In this project we would like to apply the modern methods of Probability Theory, Matroid and Polyhedral Theories to explain why such algorithms perform well in practice. We also would like to design new algorithms for transforming solutions of relaxed practically relevant optimization problems into solutions of original hard optimization problems. Along the way we would like to design new concentration inequalities of random processes associated with our probabilistic rounding algorithms. Such concentration inequalities are useful in explaining the quality of randomized rounding procedures and can lead to design of new rounding algorithms.

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.warwick.ac.uk 