Binary Optimization over Trained Neural Networks: Parallel Sampling on an Annealed Landscape

In constraint learning, optimization problems are formulated with an objective function or constraints that are learned from data and represented as pretrained neural networks. Although promising as a modeling paradigm, this approach has scalability challenges that have been progressively addressed with tailored algorithms. However, those algorithms assume that the decision variables are continuous. In this work, we introduce CLEBO (Constraint Learning via Energy-Based Optimization), to our knowledge the first algorithm tailored for constraint learning over binary domains. CLEBO performs massively parallel first-order optimization using an annealed relaxation inducing binary variables toward binary values. We present two variants that differ in how neural gradients are computed. The first is a relaxed estimator that differentiates through the neural network. The second is a discrete sampling estimator that avoids unreliable gradients by not evaluating the network at non-binary inputs. Compared to other solving methods, CLEBO also stands out for being a GPU-native sampler that is agnostic to both the network architecture and its activation functions. Experiments on three benchmark problems demonstrate that CLEBO computes solutions that are competitive with exact mixed-integer programming solvers up to the sizes that such solvers can handle. For larger networks in which finding the optimal solution is computationally prohibitive, CLEBO often finds higher-quality solutions in substantially less time.