# Constrained Discrete Black-Box Optimization using Mixed-Integer Programming

arXiv: https://arxiv.org/abs/2110.09569 · HTML: https://mlsanity.com/paper/2110.09569/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2021.

## Built on by (most cited first, 16 of 16)

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [A mixed-categorical correlation kernel for Gaussian process](https://mlsanity.com/paper/2211.08262/) (2022)
- [Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces](https://mlsanity.com/paper/2207.00879/) (2022)
- [Modeling Design and Control Problems Involving Neural Network Surrogates](https://mlsanity.com/paper/2111.10489/) (2021)
- [Bayesian Optimization-based Combinatorial Assignment](https://mlsanity.com/paper/2208.14698/) (2022)
- [Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation](https://mlsanity.com/paper/2410.16893/) (2024)
- [P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints](https://mlsanity.com/paper/2202.05198/) (2022)
- [Learning to Optimize with Stochastic Dominance Constraints](https://mlsanity.com/paper/2211.07767/) (2022)
- [Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?](https://mlsanity.com/paper/2503.03625/) (2025)
- [Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement](https://mlsanity.com/paper/2406.05830/) (2024)
- [Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates](https://mlsanity.com/paper/2302.04686/) (2023)
- [BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks](https://mlsanity.com/paper/2505.20997/) (2025)
- [Constraint-Aware Discrete Black-Box Optimization Using Tensor Decomposition](https://mlsanity.com/paper/2609.09370/) (2026)
- [ILP-BO: Integer Linear Programming-Based Black-Box Optimization](https://mlsanity.com/paper/2609.33131/) (2026)

## Abstract (arXiv)

Discrete black-box optimization problems are challenging for model-based optimization (MBO) algorithms, such as Bayesian optimization, due to the size of the search space and the need to satisfy combinatorial constraints. In particular, these methods require repeatedly solving a complex discrete global optimization problem in the inner loop, where popular heuristic inner-loop solvers introduce approximations and are difficult to adapt to combinatorial constraints. In response, we propose NN+MILP, a general discrete MBO framework using piecewise-linear neural networks as surrogate models and mixed-integer linear programming (MILP) to optimize the acquisition function. MILP provides optimality guarantees and a versatile declarative language for domain-specific constraints. We test our approach on a range of unconstrained and constrained problems, including DNA binding, constrained binary quadratic problems from the MINLPLib benchmark, and the NAS-Bench-101 neural architecture search benchmark. NN+MILP surpasses or matches the performance of black-box algorithms tailored to the constraints at hand, with global optimization of the acquisition problem running in a few minutes using only standard software packages and hardware.