Linear Decision Tree Policies for Integer Linear Programs

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 $\Sigma_2^p$-complete.

Alongside these theoretical results, 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 one to retrieve optimal solutions orders of magnitude faster than classical and specialized solution methods on repeated queries.

Overall, this paradigm provides a different perspective on the solution of integer linear programs and offers a principled offline-online approach for repeated optimization.