Constrained Discrete Black-Box Optimization using Mixed-Integer\n Programming

2021/10/18 by Theodore Papalexopoulos, Papalexopoulos, Theodore, Christian Tjandraatmadja +7 · 1 citation
Computer Science · #Advanced Multi-Objective Optimization Algorithms #FOS: Mathematics #Machine Learning and Algorithms #Machine Learning and Data Classification #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2110.09569

openalex publication_date 2021/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Scalable Bayesian Optimization Using Deep Neural Networks
• Practical Bayesian Optimization of Machine Learning Algorithms
• Taking the Human Out of the Loop: A Review of Bayesian Optimization
• An approach to reachability analysis for feed-forward ReLU neural networks
• Deep learning for molecular design—a review of the state of the art
• Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles
• Combinatorial Bayesian Optimization using the Graph Cartesian Product
• Scaling Up Exact Neural Network Compression by ReLU Stability

Cited by

• BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks

Related

• Polynomial-Model-Based Optimization for Blackbox Objectives
• Optimization Over Trained Neural Networks: Taking a Relaxing Walk
• Scalable neural network-based blackbox optimization
• Solving Black-Box Optimization Challenge via Learning Search Space Partition for Local Bayesian Optimization
• End-to-End Constrained Optimization Learning: A Survey