Linear Decision Tree Policies for Integer Linear Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915978040836096 |
|---|---|
| author | Guyard, Théo Oliveira, Cleber Schiffer, Maximilian Uchoa, Eduardo Vidal, Thibaut |
| author_facet | Guyard, Théo Oliveira, Cleber Schiffer, Maximilian Uchoa, Eduardo Vidal, Thibaut |
| contents | We study optimal decision policies for integer linear programs with a fixed feasible set and varying cost vectors, represented as linear decision trees. Once synthesized for a given feasible set, they return an optimal solution for any queried cost vector through a sequence of linear tests. We show that there exists a policy performing this operation in a polynomial number of arithmetic operations in the worst case. Along with this theoretical guarantee, we develop a practical construction framework to synthesize policies within a specific subclass of linear decision trees. Our computational experiments show that, although policy synthesis can be time-intensive, it allows retrieving optimal solutions orders of magnitude faster than classical and specialized solution methods on repeated queries. Overall, this paradigm provides a new perspective on the complexity of integer linear programs and offers an offline--online approach for solving them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02582 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear Decision Tree Policies for Integer Linear Programs Guyard, Théo Oliveira, Cleber Schiffer, Maximilian Uchoa, Eduardo Vidal, Thibaut Optimization and Control 90C10, 90C57, 90C60 We study optimal decision policies for integer linear programs with a fixed feasible set and varying cost vectors, represented as linear decision trees. Once synthesized for a given feasible set, they return an optimal solution for any queried cost vector through a sequence of linear tests. We show that there exists a policy performing this operation in a polynomial number of arithmetic operations in the worst case. Along with this theoretical guarantee, we develop a practical construction framework to synthesize policies within a specific subclass of linear decision trees. Our computational experiments show that, although policy synthesis can be time-intensive, it allows retrieving optimal solutions orders of magnitude faster than classical and specialized solution methods on repeated queries. Overall, this paradigm provides a new perspective on the complexity of integer linear programs and offers an offline--online approach for solving them. |
| title | Linear Decision Tree Policies for Integer Linear Programs |
| topic | Optimization and Control 90C10, 90C57, 90C60 |
| url | https://arxiv.org/abs/2605.02582 |