$MC^2$ Mixed Integer and Linear Programming
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912729021808640 |
|---|---|
| author | Polson, Nick Sokolov, Vadim |
| author_facet | Polson, Nick Sokolov, Vadim |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20575 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $MC^2$ Mixed Integer and Linear Programming Polson, Nick Sokolov, Vadim Computation 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. |
| title | $MC^2$ Mixed Integer and Linear Programming |
| topic | Computation |
| url | https://arxiv.org/abs/2511.20575 |