arxiv: 2605.02582 · v1 · submitted 2026-05-04 · 🧮 math.OC

Recognition: 3 theorem links

· Lean Theorem

Linear Decision Tree Policies for Integer Linear Programs

Th\'eo Guyard , Cleber Oliveira , Maximilian Schiffer , Eduardo Uchoa , Thibaut Vidal

Authors on Pith no claims yet

Pith reviewed 2026-05-08 17:55 UTC · model grok-4.3

classification 🧮 math.OC

keywords integer linear programmingdecision treesoptimal policiesoffline-online optimizationfixed feasible set

0 comments

The pith

For integer linear programs with a fixed feasible set, a linear decision tree policy exists that returns an optimal solution using only polynomially many arithmetic operations for any cost vector.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that optimal solutions to an integer linear program can be recovered from a fixed feasible set by following a sequence of linear tests on the cost vector. Once the decision tree is built for that set, the entire process stays within a polynomial number of arithmetic steps no matter which costs are presented. This separates the heavy offline work of constructing the tree from the fast online queries that follow. The authors also give a concrete method to synthesize one practical subclass of such trees and test it on repeated optimization queries.

Core claim

There exists a linear decision tree policy that, for any cost vector, returns an optimal solution to the integer linear program over a fixed feasible set by performing only a polynomial number of arithmetic operations in the worst case.

What carries the argument

Linear decision trees that branch on linear tests of the cost vector to identify the optimal solution for the fixed feasible set.

If this is right

Any number of subsequent optimization queries with the same feasible set can be answered by walking the pre-built tree rather than resolving the integer program.
The offline synthesis step can be performed once and then reused for arbitrarily many cost vectors.
The approach yields a new complexity classification for integer linear programs distinguished by whether their feasible set is fixed or varies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same tree-based offline-online split might apply to other combinatorial problems whose constraint set is stable across many queries.
Practical synthesis methods could be refined by limiting tree depth or by pruning redundant linear tests.
Applications that repeatedly solve the same integer program under changing objectives, such as real-time routing, would benefit most from the speedup.

Load-bearing premise

The feasible set is fixed and finite so that a single decision tree can be built once to handle every possible cost vector.

What would settle it

An explicit feasible set of integer points together with a family of cost vectors for which every linear decision tree that always returns the optimum requires super-polynomial depth.

Figures

Figures reproduced from arXiv: 2605.02582 by Cleber Oliveira, Eduardo Uchoa, Maximilian Schiffer, Th\'eo Guyard, Thibaut Vidal.

**Figure 1.** Figure 1: Left: Two-dimensional feasible set X = {x1, . . . , x5} and its associated normal fan. Its cones are separated by hyperplanes normal to the faces of conv(X ) and passing through the origin. Each cone F(xi) corresponds to the set of cost vectors for which xi ∈ X is an optimal solution to Problem (P). Note that x4 ∈ int conv(X ), so this feasible solution is never optimal for any cost vector, and its associa… view at source ↗

**Figure 2.** Figure 2: Average evaluation time for solving the selected ILP classes as a function of the view at source ↗

**Figure 3.** Figure 3: Construction and evaluation time for policies based on NNS data structures. view at source ↗

**Figure 4.** Figure 4: Flattened C representation of an LDT policy to solve any view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

For ILPs with a fixed finite feasible set, a linear decision tree can return optimal solutions for any cost vector in polynomial arithmetic operations worst-case, and the paper gives both the existence argument and a workable synthesis method.

read the letter

The core result is that when the feasible set is fixed and finite, the cost space splits into finitely many polyhedral regions, one per optimal solution, separated by the hyperplanes where two solutions tie in cost. A linear decision tree can navigate those regions with a sequence of sign tests on linear forms in the cost vector, and because the number of regions is finite the worst-case depth stays bounded by a constant that depends only on the problem parameters, not on the particular query. That gives the polynomial arithmetic-operation bound they claim, and the argument is straightforward once you accept the finite-partition premise. No circularity or hidden fitting there. They also supply a concrete framework for building policies inside a restricted family of these trees and run experiments that show the query phase is orders of magnitude faster than standard solvers once the tree exists. That offline-online split is the practical hook. Synthesis itself is expensive, which they state plainly, so the approach only makes sense when the same feasible set will be queried many times. The experiments are on concrete instances and the speedups look real, but the subclass restriction means the constructed trees may not always hit the theoretical minimum depth; that is a minor practical gap rather than a flaw in the existence claim. The citation pattern is light and focused on the relevant decision-tree and ILP literature. This is aimed at operations-research people who repeatedly solve the same constraint structure under varying objectives, such as in routing or scheduling. It reframes the complexity question by moving the heavy lifting offline. I would send it to peer review; the central existence result is internally consistent and the empirical side shows enough promise to justify referee time even if synthesis cost needs more discussion.

Referee Report

1 major / 3 minor

Summary. The manuscript claims that for integer linear programs with a fixed finite feasible set, there exists a linear decision tree policy that returns an optimal solution for any cost vector using a polynomial number of arithmetic operations in the worst case. The authors also develop a practical synthesis framework for a subclass of such policies and report computational experiments demonstrating orders-of-magnitude speedups over classical solvers for repeated queries, at the cost of offline synthesis time.

Significance. If the existence result and polynomial bound hold, the work introduces a novel offline-online paradigm for ILPs that reframes their complexity when the feasible set is static. This could enable substantial practical gains in applications with repeated queries, such as parametric optimization or real-time decision making, and the empirical speedups provide concrete evidence of the approach's potential utility beyond the theoretical guarantee.

major comments (1)

[Theoretical result (around the existence proof)] The central existence claim relies on the finite partition of cost space into polyhedral regions (one per optimal solution) delimited by O(m²) hyperplanes c·(x_i - x_j)=0. The manuscript should explicitly derive the worst-case tree depth (or number of arithmetic operations) as a function of the input parameters (number of variables, constraints, and bit size) rather than leaving it as an implicit constant; this bound is load-bearing for the polynomial-time assertion.

minor comments (3)

[Abstract] The abstract and introduction should clarify the precise subclass of linear decision trees for which the practical synthesis algorithm is provided, as the general existence result applies to a broader class.
[Computational experiments] Experimental section: more detail is needed on the benchmark instances (e.g., number of variables, constraint density, range of cost vectors) and on how synthesis time scales with feasible-set size to allow reproducibility and assessment of the offline-online trade-off.
[Throughout] Notation for the decision tree nodes and the linear test forms should be standardized across the theoretical and algorithmic sections to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestion regarding the theoretical result. We address the comment below and will incorporate the requested clarification in the revised manuscript.

read point-by-point responses

Referee: The central existence claim relies on the finite partition of cost space into polyhedral regions (one per optimal solution) delimited by O(m²) hyperplanes c·(x_i - x_j)=0. The manuscript should explicitly derive the worst-case tree depth (or number of arithmetic operations) as a function of the input parameters (number of variables, constraints, and bit size) rather than leaving it as an implicit constant; this bound is load-bearing for the polynomial-time assertion.

Authors: We agree that an explicit derivation strengthens the presentation. In the revised manuscript we will add a dedicated paragraph in Section 3 (or the relevant theoretical section) providing the bound. Let K = |X| denote the cardinality of the fixed feasible set and let n be the number of variables. A linear decision tree can be constructed that identifies an optimal solution by a tournament of pairwise comparisons: each internal node evaluates the sign of the linear form c · (x − y) for a pair of candidate solutions x, y ∈ X. Finding the minimum among K scalar values requires at most K − 1 such comparisons in the worst case. Evaluating each dot product c · d (where d = x − y has at most n nonzero entries) takes O(n) arithmetic operations (multiplications and additions). Consequently the worst-case number of arithmetic operations is O(K n). Because the feasible set X is fixed, both K and n are constants independent of any particular query; the bound is therefore constant (hence polynomial) in the bit size of the cost vector c. The original number of constraints m in the ILP description does not appear explicitly, as the policy is synthesized from the enumerated set X rather than from the constraint matrix. This construction makes the polynomial-time claim fully rigorous and explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper claims existence of a linear decision tree policy that, for any fixed finite feasible set, returns an optimal ILP solution for any cost vector using polynomially many arithmetic operations. This follows from the finite partition of cost space into polyhedral regions (one per optimal solution), delimited by hyperplanes c·(x_i−x_j)=0; any such finite partition admits a decision tree of bounded depth performing sign tests on linear forms. The argument is self-contained under the stated hypothesis of a fixed finite feasible set and does not reduce to fitted parameters, self-definitional equations, or load-bearing self-citations. No step equates a derived quantity to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the feasible set is fixed and finite, allowing precomputation of a decision tree that distinguishes optimal solutions via linear tests on cost vectors.

axioms (1)

domain assumption The feasible set of the integer linear program is fixed and finite.
The entire approach of synthesizing a policy once for all future cost vectors depends on this.

pith-pipeline@v0.9.0 · 5435 in / 1131 out tokens · 59925 ms · 2026-05-08T17:55:56.230002+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

181 extracted references · 1 canonical work pages

[1]

International Journal of Computer Applications , volume=

A Survey on Nearest Neighbor Search Methods , author=. International Journal of Computer Applications , volume=
[2]

Mathematical Programming Computation , volume =

SCIP: solving constraint integer programs , author =. Mathematical Programming Computation , volume =. 2009 , publisher =

2009
[3]

INFORMS Journal on Computing , volume =

Presolve reductions in mixed integer programming , author =. INFORMS Journal on Computing , volume =. 2020 , publisher =

2020
[4]

Reading/Addison-Wesley , year =

The Design and Analysis of Computer Algorithms , author =. Reading/Addison-Wesley , year =
[5]

Journal of Statistics and Management Systems , volume =

A comparative analysis of optimization solvers , author =. Journal of Statistics and Management Systems , volume =. 2017 , publisher =

2017
[6]

ACM Computing Surveys , volume =

Voronoi diagrams—a survey of a fundamental geometric data structure , author =. ACM Computing Surveys , volume =. 1991 , publisher =

1991
[7]

1996 , publisher=

Voronoi diagrams , author=. 1996 , publisher=

1996
[8]

Journal of Molecular Graphics , volume =

Searching for geometric molecular shape complementarity using bidimensional surface profiles , author =. Journal of Molecular Graphics , volume =. 1992 , publisher =

1992
[9]

Astrophysics Source Code Library , pages =

Qhull: Quickhull algorithm for computing the convex hull , author =. Astrophysics Source Code Library , pages =
[10]

Early writings on graph theory: Euler circuits and the K

Barnett, Janet Heine , journal =. Early writings on graph theory: Euler circuits and the K. 2005 , publisher =

2005
[11]

Annals of Operations Research , volume =

The continuous reactive tabu search: blending combinatorial optimization and stochastic search for global optimization , author =. Annals of Operations Research , volume =. 1996 , publisher =

1996
[12]

Bulletin of the American Mathematical Society , volume =

The theory of dynamic programming , author =. Bulletin of the American Mathematical Society , volume =
[13]

Quarterly of applied mathematics , volume =

On a routing problem , author =. Quarterly of applied mathematics , volume =
[14]

Journal of the ACM , volume =

Dynamic programming treatment of the travelling salesman problem , author =. Journal of the ACM , volume =. 1962 , publisher =

1962
[15]

European Journal of Operational Research , volume =

Machine learning for combinatorial optimization: a methodological tour d’horizon , author =. European Journal of Operational Research , volume =. 2021 , publisher =

2021
[16]

Computing Science and Statistics , pages =

Global tree optimization: A non-greedy decision tree algorithm , author =. Computing Science and Statistics , pages =. 1994 , publisher =

1994
[17]

Optimization methods and Software , volume =

Multicategory discrimination via linear programming , author =. Optimization methods and Software , volume =. 1994 , publisher =

1994
[18]

Communications of the ACM , volume =

Multidimensional binary search trees used for associative searching , author =. Communications of the ACM , volume =. 1975 , publisher =

1975
[19]

Machine Learning , volume =

The voice of optimization , author =. Machine Learning , volume =. 2021 , publisher =

2021
[20]

2016 IEEE International Symposium on High Performance Computer Architecture (HPCA) , pages =

Memristive boltzmann machine: A hardware accelerator for combinatorial optimization and deep learning , author =. 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA) , pages =. 2016 , organization =

2016
[21]

1984 , publisher =

Classification and Regression Trees , author =. 1984 , publisher =

1984
[22]

Machine learning , volume =

Bagging predictors , author =. Machine learning , volume =. 1996 , publisher =

1996
[23]

Journal of Complexity , volume =

On randomized semi-algebraic test complexity , author =. Journal of Complexity , volume =. 1993 , publisher =

1993
[24]

24th Annual European Symposium on Algorithms (ESA 2016) , pages =

Solving k-SUM Using Few Linear Queries , author =. 24th Annual European Symposium on Algorithms (ESA 2016) , pages =. 2016 , organization =

2016
[25]

Journal of applied science and technology trends , volume =

Classification based on decision tree algorithm for machine learning , author =. Journal of applied science and technology trends , volume =
[26]

Proceedings of the 32nd Annual Symposium of Foundations of Computer Science , pages =

An optimal convex hull algorithm and new results on cuttings , author =. Proceedings of the 32nd Annual Symposium of Foundations of Computer Science , pages =. 1991 , organization =

1991
[27]

IEEE transactions on pattern analysis and machine intelligence , volume =

Learning to index for nearest neighbor search , author =. IEEE transactions on pattern analysis and machine intelligence , volume =. 2019 , publisher =

2019
[28]

International Symposium on Algorithms and Computation , pages =

On greedy algorithms for decision trees , author =. International Symposium on Algorithms and Computation , pages =. 2010 , organization =

2010
[29]

Nearest-neighbor methods for learning and vision: theory and practice , pages =

Nearest-neighbor searching and metric space dimensions , author =. Nearest-neighbor methods for learning and vision: theory and practice , pages =
[30]

Proceedings of the fourth annual ACM symposium on Theory of computing , pages =

Time-bounded random access machines , author =. Proceedings of the fourth annual ACM symposium on Theory of computing , pages =
[31]

Research Trends in Combinatorial Optimization , volume =

Combinatorial optimization , author =. Research Trends in Combinatorial Optimization , volume =. 1994 , publisher =

1994
[32]

Artificial Intelligence Review , volume =

Recent advances in decision trees: An updated survey , author =. Artificial Intelligence Review , volume =. 2023 , publisher =

2023
[33]

1: User’s Manual for CPLEX , author =

V12. 1: User’s Manual for CPLEX , author =. International Business Machines Corporation , volume =
[34]

Bulletin of the Academy of Sciences of the USSR Classe des Sciences Mathematiques et Naturelles , volume =

Sur la sphere vide , author =. Bulletin of the Academy of Sciences of the USSR Classe des Sciences Mathematiques et Naturelles , volume =
[35]

, author =

A Note on Two Problems in Connexion with Graphs. , author =. Numerische Mathematik , volume =
[36]

Journal of Computer and System Sciences , volume =

A lower bound of 12n2 on linear search programs for the knapsack problem , author =. Journal of Computer and System Sciences , volume =. 1978 , publisher =

1978
[37]

1987 , publisher =

Algorithms in combinatorial geometry , author =. 1987 , publisher =

1987
[38]

IEEE transactions on pattern analysis and machine intelligence , volume =

Dynamic programming and graph algorithms in computer vision , author =. IEEE transactions on pattern analysis and machine intelligence , volume =. 2010 , publisher =

2010
[39]

Proceedings of the 41st International Conference on Machine Learning , pages =

Trained random forests completely reveal your dataset , author =. Proceedings of the 41st International Conference on Machine Learning , pages =
[40]

Communications of the ACM , volume =

Algorithm 97: shortest path , author =. Communications of the ACM , volume =. 1962 , publisher =

1962
[41]

Canadian journal of Mathematics , volume =

Maximal flow through a network , author =. Canadian journal of Mathematics , volume =. 1956 , publisher =

1956
[42]

Handbook of Discrete and Computational Geometry , pages =

Voronoi diagrams and Delaunay triangulations , author =. Handbook of Discrete and Computational Geometry , pages =. 2017 , publisher =

2017
[43]

Journal of Global Optimization , volume =

Three enhancements for optimization-based bound tightening , author =. Journal of Global Optimization , volume =. 2017 , publisher =

2017
[44]

Advanced School on the Algorithmic Foundations of Geographic Information Systems , pages =

Voronoi methods in GIS , author =. Advanced School on the Algorithmic Foundations of Geographic Information Systems , pages =. 1996 , publisher =

1996
[45]

2010 , publisher =

P, NP, and NP-Completeness: The basics of computational complexity , author =. 2010 , publisher =

2010
[46]

1993 , publisher =

Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees , author =. 1993 , publisher =

1993
[47]

Proceedings of IEEE 36th Annual Foundations of Computer Science , pages =

Improved lower bound on testing membership to a polyhedron by algebraic decision trees , author =. Proceedings of IEEE 36th Annual Foundations of Computer Science , pages =. 1995 , organization =

1995
[48]

Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing , pages =

A lower bound for randomized algebraic decision trees , author =. Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing , pages =
[49]

Computational Complexity , volume =

Randomization and the computational power of analytic and algebraic decision trees , author =. Computational Complexity , volume =. 1996 , publisher =

1996
[50]

Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages =

Randomized O(n2) lower bound for knapsack , author =. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages =
[51]

Algorithmica , volume =

Randomized incremental construction of Delaunay and Voronoi diagrams , author =. Algorithmica , volume =. 1992 , publisher =

1992
[52]

Mixed integer nonlinear programming , pages =

Perspective reformulation and applications , author =. Mixed integer nonlinear programming , pages =. 2011 , publisher =

2011
[53]

2012 , publisher =

Approximate nearest neighbor: Towards removing the curse of dimensionality , author =. 2012 , publisher =

2012
[54]

Journal of computational and applied mathematics , volume =

Combinatorial optimization: Current successes and directions for the future , author =. Journal of computational and applied mathematics , volume =. 2000 , publisher =

2000
[55]

Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages =

Approximate nearest neighbors: towards removing the curse of dimensionality , author =. Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages =
[56]

Oikos , volume =

Entropy and diversity , author =. Oikos , volume =. 2006 , publisher =

2006
[57]

European Journal of Operational Research , volume =

Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art , author =. European Journal of Operational Research , volume =. 2022 , publisher =

2022
[58]

Management Science , volume =

A primal method for minimal cost flows with applications to the assignment and transportation problems , author =. Management Science , volume =. 1967 , publisher =

1967
[59]

Computational Geometry , volume =

Randomized incremental construction of abstract Voronoi diagrams , author =. Computational Geometry , volume =. 1993 , publisher =

1993
[60]

Discrete & Computational Geometry , volume =

A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems , author =. Discrete & Computational Geometry , volume =. 1987 , publisher =

1987
[61]

2011 , publisher =

Combinatorial optimization , author =. 2011 , publisher =

2011
[62]

Proceedings of the American Mathematical society , volume =

On the shortest spanning subtree of a graph and the traveling salesman problem , author =. Proceedings of the American Mathematical society , volume =. 1956 , publisher =

1956
[63]

Naval research logistics quarterly , volume =

The Hungarian method for the assignment problem , author =. Naval research logistics quarterly , volume =. 1955 , publisher =

1955
[64]

Operations research , volume =

Branch-and-bound methods: A survey , author =. Operations research , volume =. 1966 , publisher =

1966
[65]

2007 IEEE workshop on applications of computer vision (WACV'07) , pages =

Clustering billions of images with large scale nearest neighbor search , author =. 2007 IEEE workshop on applications of computer vision (WACV'07) , pages =. 2007 , organization =

2007
[66]

Theory driven by influential applications , pages =

Performance variability in mixed-integer programming , author =. Theory driven by influential applications , pages =. 2013 , publisher =

2013
[67]

Traveling salesman problem, theory and applications , volume =

Traveling salesman problem: an overview of applications, formulations, and solution approaches , author =. Traveling salesman problem, theory and applications , volume =. 2010 , publisher =

2010
[68]

2005 , publisher =

Discriminant analysis and statistical pattern recognition , author =. 2005 , publisher =

2005
[69]

Information and Computation , volume =

Point location in arrangements of hyperplanes , author =. Information and Computation , volume =. 1993 , publisher =

1993
[70]

Journal of the ACM , volume =

A polynomial linear search algorithm for the n-dimensional knapsack problem , author =. Journal of the ACM , volume =. 1984 , publisher =

1984
[71]

Journal of the ACM , volume =

Lower bounds for solving linear Diophantine equations on Random Access Machines , author =. Journal of the ACM , volume =. 1985 , publisher =

1985
[72]

Journal of the ACM , volume =

Fast algorithms for n-dimensional restrictions of hard problems , author =. Journal of the ACM , volume =. 1988 , publisher =

1988
[73]

Handbook of Applied Optimization , volume =

Branch-and-cut algorithms for combinatorial optimization problems , author =. Handbook of Applied Optimization , volume =. 2002 , publisher =

2002
[74]

Nature Reviews Physics , volume =

Ising machines as hardware solvers of combinatorial optimization problems , author =. Nature Reviews Physics , volume =. 2022 , publisher =

2022
[75]

Discrete Optimization , volume =

Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning , author =. Discrete Optimization , volume =. 2016 , publisher =

2016
[76]

Parallel computing , volume =

Evolution algorithms in combinatorial optimization , author =. Parallel computing , volume =. 1988 , publisher =

1988
[77]

IEEE transactions on pattern analysis and machine intelligence , volume =

Scalable nearest neighbor algorithms for high dimensional data , author =. IEEE transactions on pattern analysis and machine intelligence , volume =. 2014 , publisher =

2014
[78]

KDD , pages =

Decision Tree Induction: How Effective Is the Greedy Heuristic? , author =. KDD , pages =
[79]

2017 International Conference on Current Trends in Computer, Electrical, Electronics and Communication (CTCEEC) , pages =

Classification and prediction of breast cancer using linear regression, decision tree and random forest , author =. 2017 International Conference on Current Trends in Computer, Electrical, Electronics and Communication (CTCEEC) , pages =. 2017 , organization =

2017
[80]

23rd ACM/IEEE Design Automation Conference , pages =

Simulated annealing and combinatorial optimization , author =. 23rd ACM/IEEE Design Automation Conference , pages =. 1986 , organization =

1986

Showing first 80 references.