Exact mathematical programming formulations for estimating classification rules provide guarantees of empirical optimality, but their size grows rapidly with the number of predictive features and model complexity. This paper shows that interpretable classifiers can be estimated by directly maximizing empirical classification accuracy under complexity constraints, using truncation and warm-start strategies compatible with disjunctive normal form and decision tree representations. We first develop Mixed-Integer Linear Programming (MILP) and Quadratic Unconstrained Binary Optimization (QUBO) formulations for categorical and ordinal classification, establish equivalence conditions among alternative treatments of empty and contradictory clauses, and derive reduced saturated representations that reduce the effective size of the clause space. Building on these structural results, we propose an incremental optimization procedure that solves a sequence of smaller problems, progressively enlarging the admissible model class while carrying forward high-quality incumbent solutions. We also investigate hybrid quantum annealing for producing warm-start solutions. Computational experiments on benchmark categorical datasets show that this approach substantially improves the computational tractability of empirical accuracy maximization for categorical and ordinal Boolean classification.
Citation
Statistical classification, Boolean rules, Quantum hybrid optimization, Incremental learning