权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Probabilistic Rounding Algorithms for Mathematical Programming

数学规划的概率舍入算法

基本信息

批准号：
EP/J021814/1
负责人：
Maxim Sviridenko
金额：
$ 45.99万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2012
资助国家：
英国
起止时间：
2012 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FJ021814%2F1
关键词：
Probabilistic Rounding Algorithms Mathematical Programming

项目摘要

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.

该提案属于离散优化问题算法设计和分析的一般领域。此类问题出现在商业分析、管理和计算机科学以及所有工程子领域中。该领域出现的模型和问题的多样性令人震惊。然而，在实践中解决此类问题的选择方法是松弛问题的数学规划求解器（CPLEX、Gurobi、IPOPT）的某种组合，其中一些问题约束（例如决策变量的完整性）被松弛或丢弃，以及一些将松弛解转换为原始问题的解的舍入算法。在许多情况下，此类实用算法会在多个阶段中工作，慢慢地将松弛解转换为非松弛解，同时不断监控当前解的质量。另一方面，理论计算机科学、数学编程和运筹学界长期以来认识到，了解将“简单”优化问题的最优或接近最优解转换为“困难”优化问题的高质量解的各种方法的性能是理解“难”优化问题的关键。实用启发式的性能并设计新算法来解决困难的优化问题。此类方法通常称为舍入算法，因为它们通常将分数解转换为积分解。在这个项目中，我们希望应用概率论、拟阵和多面体理论的现代方法来解释为什么此类算法在实践中表现良好。我们还想设计新的算法，将宽松的实际相关优化问题的解转换为原始硬优化问题的解。在此过程中，我们希望设计与我们的概率舍入算法相关的新的随机过程集中不等式。这种浓度不等式有助于解释随机舍入过程的质量，并且可以导致新舍入算法的设计。