{"id":"arxiv/2605.02582","url":"https://arxiv.org/abs/2605.02582","tags":["math.OC"],"score":0,"title":"Linear Decision Tree Policies for Integer Linear Programs","domain":"math.OC","source":"arxiv","authors":["Théo Guyard","Cleber Oliveira","Maximilian Schiffer","Eduardo Uchoa","Thibaut Vidal"],"reviews":0,"subject":"math.OC","summary":"We study optimal decision policies, represented as linear decision trees, for integer linear programs with a fixed feasible set and varying cost vectors. 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. In contrast, deciding whether there exists an exact policy with a prescribed maximum number of leaves is $Σ_2^p$-complete. Alongside these theoretical results, we develop a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}