Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/J021814/1 - Probabilistic Rounding Algorithms for Mathematical Programming

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPJ0218141.png

Professor M Sviridenko EP/J021814/1 - Probabilistic Rounding Algorithms for Mathematical Programming

Principal Investigator - Computer Science, University of Warwick

Scheme

Standard Research

Research Areas

Maths of Computing Maths of Computing

Logic and Combinatorics Logic and Combinatorics

Collaborators

IBM Watson Research Centre IBM Watson Research Centre

IBM Almaden Research Center IBM Almaden Research Center

Start Date

11/2012

End Date

10/2015

Value

£360,972

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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 near-optimal 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.

Structured Data / Microdata


Grant Event Details:
Name: Probabilistic Rounding Algorithms for Mathematical Programming - EP/J021814/1
Start Date: 2012-11-01T00:00:00+00:00
End Date: 2015-10-31T00:00:00+00:00

Organization: University of Warwick

Description: 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 probl ...