Convexification of mixed-integer quadratic optimization via decision diagrams

What the math gives to ML

The paper gives a constructive way to optimize binary activation patterns coupled to continuous variables under a quadratic objective, by representing partial assignments with decision-diagram states and merging assignments that induce the same boundary-conditioned quadratic residual. The transferable asset is not generic mixed-integer optimization itself, but the state-compression principle: for tree-structured or inverse-tree-structured interactions, a potentially exponential collection of masks can be represented by a small dynamic program. This suggests exact structured gating or expert-selection layers for neural networks whose redundancy, communication, or activation-cost model is sparse in a graph. The approximate-boundary result further suggests linear-size routing and pruning procedures with an explicit controllable optimization gap.