Probabilistic Rounding Algorithms for Mathematical Programming

Lead Research Organisation: University of Warwick
Department Name: Computer Science

Abstract

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.

Planned Impact

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".

Publications

10 25 50
publication icon
Ward J (2016) Maximizing k -Submodular Functions and Beyond in ACM Transactions on Algorithms

publication icon
Im S (2013) Preemptive and non-preemptive generalized min sum set cover in Mathematical Programming

publication icon
Skutella M (2016) Unrelated Machine Scheduling with Stochastic Processing Times in Mathematics of Operations Research

publication icon
Mucha M (2016) No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem in Mathematics of Operations Research

publication icon
Adamczyk M (2016) Submodular Stochastic Probing on Matroids in Mathematics of Operations Research

 
Description This project focused on the advances of the area of design and analysis of algorithms for discrete optimisation problems. The central goal was to develop algorithmic and probabilistic tools to improve our understanding of the algorithmic and optimisation challenges in this area.

The general type of problems studied in this project arises naturally in Business Analytics, Management and Computer Sciences and in all Engineering subfields. While the variety of models and problems arising in this area is astonishing, the method of choice to solve such problems in practice is limited to 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.

At the same time, it was long recognised in the Theoretical Computer Science, Mathematical Programming and Operational 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 have been applying modern methods of Probability Theory, Matroid and Polyhedral Theories to explain why such algorithms perform well in practice. We also designed several new algorithmic and analytic tools for transforming solutions of relaxed practically relevant optimization problems into solutions of original hard optimization problems.
Exploitation Route It is expected that researchers and software developers working in the areas of Mathematical Programming, Approximation Algorithms, Discrete and Combinatorial Optimization will benefit from this project findings because it provides the new algorithmic tools to solve problems arising in these areas.

It is naturally recognised that solving optimisation problems (and therefore developing tools to solve them) is of extreme practical importance. Therefore the main topic of the project, 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 has a large potential to lead to the implementation of such algorithms in the software packages for integer programming solving.

Possible further application is in the use of fundamental tools in randomised algorithms and probability theory to develop new probabilistic tools for the design and analysis of algorithms to solve Mathematical Programming Problems through relax and round method. This may have a long term impact on that area.
Sectors Digital/Communication/Information Technologies (including Software)