$MC^2$ Mixed Integer and Linear Programming
By: Nick Polson, Vadim Sokolov
Potential Business Impact:
Solves hard math problems using a new computer trick.
In this paper, we design $MC^2$ algorithms for Mixed Integer and Linear Programming. By expressing a constrained optimisation as one of simulation from a Boltzmann distribution, we reformulate integer and linear programming as Monte Carlo optimisation problems. The key insight is that solving these optimisation problems requires the ability to simulate from truncated distributions, namely multivariate exponentials and Gaussians. Efficient simulation can be achieved using the algorithms of Kent and Davis. We demonstrate our methodology on portfolio optimisation and the classical farmer problem from stochastic programming. Finally, we conclude with directions for future research.
Similar Papers
Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints
Data Structures and Algorithms
Solves hard math problems faster for businesses.
Machine Learning Algorithms for Improving Exact Classical Solvers in Mixed Integer Continuous Optimization
Optimization and Control
Teaches computers to solve hard problems faster.
Improvement of Optimization using Learning Based Models in Mixed Integer Linear Programming Tasks
Machine Learning (CS)
Helps computers solve tough planning problems faster.