Probabilistic Rounding Algorithms for 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.

The successful exploration of linear programming techniques and development of generic methods to round a fractional solution to an integral solution of the optimization problem at hand will lead to the implementation of such algorithms in the software packages for integer programming solving. So all the companies developing software packages or solving optimization problems are potential beneficiaries. Here is a partial list of such beneficiaries: CPLEX (now part of ILOG which is a part of IBM), Gurobi, IPOPT.

More generally, solving optimization problems (and therefore developing tools to solve them) is of extreme practical importance. In a developed economy most productivity gains will come from Business Analytics and Optimization. As an example IBM promised 30% profit growth till 2015 and 15% of that growth should come from Business Analytics that is the primary consumer of optimization software packages. With the recent focus of many companies on the area of Business Analytics (which e.g. includes such an important area as Supply Chain and Inventory Management) the findings in this area could have a tremendous impact on solving real life optimization problems which would lead to an overall increase in the economic efficiency and productivity. One specific example when the method of column generation and linear programming with exponential number of variables are the only available tools in practice are transportation and routing problems. Linear programming formulations with an exponential number of variables and heuristics based on such formulations played an essential role in all the projects of that flavor that I witnessed in IBM, e.g. routing of trucks for the United States Postal Sevice, routing of the inventory during the initial disaster response for the Federal Emergency Agency (FEMA, US), Transportation Scheduling for Logistics of Network-Centric Military Operations.

The essence of this project is to apply known tools of the Probability Theory (Concentration Inequalities, Markov Chain Monte Carlo Method etc) and develop new probabilistic tools for the design and analysis of algorithms to solve Mathematical Programming Problems through "relax and round" method this is a relatively recent application area for Probability Theory. As a result we expect to obtain results that are interesting for various mathematical and computer science subcommunities. In particular our initial exploration of independent randomized rounding procedures for polynomial objective functions lead to the improvements of the Kim-Vu concentration inequality. We found a way to remove the dependence on number of random variables that was an open problem mentioned in the influential book by Alon and Spencer "The Probabilistic Method".