Constrained Discrete Black-Box Optimization using Mixed-Integer Programming

Abstract

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.

9 pages, 4 figures, accepted to ICML 2022, appendix with additional results in same file

References in corpus (14)

• Scikit-learn: Machine Learning in Python
• Practical Bayesian Optimization of Machine Learning Algorithms
• Neural Architecture Search with Reinforcement Learning
• Deep learning for molecular design - a review of the state of the art
• Scalable Bayesian Optimization Using Deep Neural Networks
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• Bayesian Optimization with Unknown Constraints
• Safe Controller Optimization for Quadrotors with Gaussian Processes
• An approach to reachability analysis for feed-forward ReLU neural networks
• ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
• Bayesian Optimization of Combinatorial Structures
• Combinatorial Bayesian Optimization using the Graph Cartesian Product
• Learned Hardware/Software Co-Design of Neural Accelerators
• Scaling Up Exact Neural Network Compression by ReLU Stability