Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.04273 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909825726676992 |
|---|---|
| author | Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel |
| author_facet | Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel |
| contents | On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04273 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Influence branching for learning to solve mixed-integer programs online Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel Machine Learning On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available. |
| title | Influence branching for learning to solve mixed-integer programs online |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.04273 |