Probabilistic Rounding Algorithms for Mathematical Programming

这个建议福尔斯属于一般领域的设计和分析算法的离散优化问题。这些问题出现在商业分析，管理和计算机科学以及所有工程子领域。这一领域出现的各种模式和问题令人吃惊。然而，在实践中解决这些问题的选择方法是放松问题的数学规划求解器（CPLEX，Guesthouse，IPOPT）的某种组合，其中一些问题约束（如决策变量的完整性）被放松或丢弃，以及将放松的解决方案转换为原始问题的解决方案的某种舍入算法。在许多情况下，这种实用算法在多个阶段中工作，通过缓慢地将松弛解转化为非松弛解，同时不断地监视当前解的质量。另一方面，它在理论计算机科学中长期被认可，数学规划和运筹学界认为，理解各种方法的性能，把一个最优或接近最优的解转化为一个“容易”的解，将优化问题转化为“硬”优化问题的高质量解是理解实际优化性能和设计新算法解决硬优化问题的关键。这种方法通常被称为舍入算法，因为它们通常将分数解转换为整数解。在这个项目中，我们想应用概率论，拟阵和多面体理论的现代方法来解释为什么这样的算法在实践中表现良好。我们还想设计新的算法，将放松的实际相关的优化问题的解决方案转化为原来的硬优化问题的解决方案。沿着的方式，我们想设计新的随机过程的浓度不等式与我们的概率舍入算法。这样的浓度不等式是有用的，在解释随机舍入程序的质量，并可能导致新的舍入算法的设计。

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.