PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Discrete Black-Box Optimization using Mixed-Integer Programming

Theodore Papalexopoulos, Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, David Belanger

arXiv:2110.09569v3math.OC

TL;DR

Discrete constrained black-box optimization makes MBO acquisition optimization difficult and often forces heuristic inner-loop solvers. NN+MILP uses piecewise-linear neural-network surrogates with MILP to optimize acquisitions under declarative constraints. It matches or surpasses strong baselines, while acquisition optimization remains practical on standard hardware.

  • Problem

    Discrete constrained MBO must repeatedly solve difficult acquisition problems, while heuristic inner-loop solvers introduce approximations and are hard to adapt to combinatorial constraints.

    Source: §1 · p. 1

  • Method

    NN+MILP combines piecewise-linear neural-network surrogates with MILP to exactly optimize acquisition functions and encode domain constraints declaratively.

    Source: §1 · pp. 1–2

  • Results

    NN+MILP matches or surpasses strong MBO baselines across diverse discrete black-box problems, with practical acquisition optimization runtimes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    MILP provides a general constraint language and inner-loop optimality guarantees for discrete MBO using standard software and hardware.

    Source: §1 · pp. 1–2

    The approach assumes MILP-representable constraints and focuses on finite discrete domains; continuous and mixed-integer extensions require modifications.

    Source: §3.3 · p. 4, §7 · p. 9

Abstract

from arXiv · show

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.

1. Introduction

NN+MILP addresses discrete constrained black-box optimization by combining piecewise-linear neural-network surrogates with MILP-based acquisition optimization. It matches or surpasses strong baselines while supporting declarative constraints and practical inner-loop runtimes.

  • The framework exactly solves acquisition problems with MILP, providing optimality guarantees and flexible declarative support for logical, combinatorial, and polyhedral constraints.Source: §1 · pp. 1–2
  • NN+MILP matches or surpasses strong MBO baselines across synthetic and real-world discrete black-box problems.Source: §1 · p. 2
  • MILP inner-loop optimization is often practical, solving acquisition problems in seconds with standard software packages and hardware.Source: §1 · p. 2
  • Experiments include constrained binary quadratic problems from MINLPLib to demonstrate MILP’s flexible encoding of problem-specific constraints.Source: §1 · p. 2
  • NAS-Bench-101 provides a neural architecture search case study with a MILP formulation for its graph-structured domain.Source: §1 · p. 2

2. Background and Related Work

MBO iteratively fits surrogates and optimizes acquisition functions, but discrete constrained settings make inner-loop optimization difficult. Prior approaches trade heuristic approximations and specialized feasibility handling against restrictive surrogate or solver choices, motivating MILP’s declarative constraint framework.

2.1. Model-Based Black-Box Optimization

  • MBO fits a surrogate, constructs an acquisition function, and selects each query by approximately optimizing that acquisition function.Source: §2.1 · p. 2
  • Bayesian optimization is an MBO special case that uses uncertainty-aware acquisition functions, whereas MBO also permits non-Bayesian surrogate fitting.Source: §2.1 · p. 2

2.2. Solving the Discrete MBO Acquisition Problem

  • Discrete MBO commonly uses local or evolutionary search with limited guarantees, while alternative solvers depend on specialized surrogate, acquisition, or domain structures.Source: §2.2 · pp. 2–3
  • Practitioners face a trade-off between inexact heuristic acquisition optimization and tractable surrogate models that may be mis-specified for the application domain.Source: §2.2 · p. 3

2.3. Constrained MBO

  • Constraint-aware MBO methods may use learned feasibility models, rejection sampling, penalties, or customized local search, whereas MILP can encode surrogate and white-box domain constraints together.Source: §2.3 · p. 3

2.4. Mixed Integer Linear Programming

  • MILP optimizes a linear objective over mixed integral variables and linear constraints, offering declarative formulations for logical, combinatorial, polyhedral, and piecewise-linear structures.Source: §2.4 · p. 3

3. MILP for MBO

NN+MILP applies neural-network surrogates and MILP acquisition optimization to finite discrete domains with explicit constraints. Its formulation combines encoded domains, no-good exclusions, and ReLU network constraints, yielding global inner-loop guarantees subject to solver limits.

3. MILP for MBO

  • NN+MILP uses neural-network surrogate models and solves the acquisition problem with MILP at every MBO iteration.Source: §3 · p. 3

3.1. Problem Setting

  • The problem setting assumes an expensive noiseless black-box function over a finite discrete feasible domain and a fixed sequential query budget.Source: §3.1 · pp. 3–4

3.2. Surrogate Model and Acquisition Function

  • The surrogate uses piecewise-linear neural networks, typically fully connected ReLU networks, with one-hot inputs and capacity chosen to balance expressivity and scalability.Source: §3.2 · p. 4
  • Randomly initialized networks retrained at each iteration provide an informal approximation to Thompson-sampling posterior draws for exploration and exploitation.Source: §3.2 · p. 4

3.3. MILP Formulation of the Acquisition Problem

  • The MILP domain formulation encodes one-hot decisions, application-specific MILP-representable constraints, and no-good constraints that exclude previously queried points.Source: §3.3 · p. 4
  • ReLU neurons are represented with auxiliary variables and binary activation indicators, while the MILP objective selects the surrogate regressor’s output.Source: §3.3 · p. 5

3.4. Optimality Guarantees for MILP

  • If the solver does not time out, the acquisition solution is globally optimal; on timeout it returns a feasible solution and an upper bound, but this does not guarantee overall black-box optimization.Source: §3.4 · p. 5

4. Experiments

The experiments evaluate NN+MILP across unconstrained and combinatorially constrained discrete black-box problems, emphasizing exact acquisition optimization, constraint handling, and practical MILP runtime.

4. Experiments

  • The experiments compare NN+MILP with evolutionary inner-loop ablations and application-oriented baselines under a fixed 16-neuron single-hidden-layer surrogate configuration.The MILP solver uses SCIP 7.0.1 with default settings on standard CPU machines.Source: §4 · p. 5, §4.2 · p. 6

4.1. Benchmarking Tasks

  • The benchmark covers RandomMLP, TfBind DNA binding, discretized BBOB, and Ising objectives, evaluated after 1000 queries using normalized final rewards over 20 trials.Trials begin from fixed datasets of 50 random points, and no cross-problem hyper-parameter tuning is performed.Source: §4.1 · p. 5

4.2. Unconstrained Optimization

  • NN+MILP matches or outperforms NN+RegEvo on 22 of 30 unconstrained problems, with lower normalized-score variance within objective families.The comparison isolates the effect of globally optimizing the acquisition function because the methods use the same neural-network surrogate.Source: §4.2 · pp. 6–7, Figure 1 · p. 6

4.3. Constrained Optimization

  • NN+MILP and NN+ConEvo outperform ConEvo across constrained problem sizes, with NN+MILP improving considerably over NN+ConEvo at n = 400.The two model-based methods perform similarly at n = 100, while NN+MILP improves at n = 200 and especially n = 400.Source: §4.3 · p. 7, Figure 2 · p. 7
  • NN+MILP incorporates subset-equality constraints with few extra code lines, whereas the custom ConEvo mutator is tailored to the given structure and may require substantial reworking for new constraints.The MILP formulation can be extended to other interacting MILP-representable constraints.Source: §4.3 · p. 7

4.4. Practicality of MILP

  • MILP acquisition optimization takes 7.92±4.23s on unconstrained experiments and 17.20 ± 12.08s on the largest constrained experiments, with every solution provably optimal.Neither setting exceeded the 500s safeguard time limit.Source: §4.4 · pp. 7–8, Figure 3 · p. 8

5. MINLPLib Case Study

The MINLPLib case study treats linearly constrained binary quadratic problems as black-box objectives with white-box constraints and evaluates NN+MILP against best known solutions.

5. MINLPLib Case Study

  • MILP constraint handling avoids potentially impractical feasible-point rejection sampling, whose probability can fall below 10^-6 in graphpart instances.This lets the general method address constraint classes without specialized sampling procedures.Source: §5 · p. 8
  • NN+MILP matches the best known solution in at least one trial for 20 of 61 MINLPLib problems and comes within 10% on 25 additional problems.The problems span graph partitioning, generalized assignment, shortest path, and other constraint classes.Source: §5 · p. 8
  • The study measures the primal gap after 1000 steps using 20 trials per problem initialized with 50 feasible points generated by MILPs with random objectives.MINLPLib instances contain 48 to 2203 binary variables and at least one linear constraint.Source: §5 · p. 8

6. NAS-Bench-101 Case Study

The NAS-Bench-101 case study formulates valid neural-architecture cells as MILP-representable DAGs and evaluates NN+MILP against evolutionary and linear-surrogate alternatives. NN+MILP significantly outperforms regularized evolution, although Linear+MILP is initially stronger before being overtaken.

6. NAS-Bench-101 Case Study

  • The benchmark represents neural cells as directed acyclic graphs whose internal nodes use convolution or max-pooling operations, with image-classification accuracy as the objective.Source: §6 · p. 8
  • The MILP formulation encodes DAG adjacency and node operations, including a null operation for cells with fewer than V nodes.Source: §6 · p. 8
  • Connectivity constraints require every non-null node to lie on an input-to-output path and require at least one such path.Source: §6 · p. 8
  • NN+MILP significantly outperforms regularized evolution on incumbent NAS-Bench-101 test accuracy over cumulative training time.The comparison averages results over 100 trials with 95% confidence bands.Source: §6 · p. 9, Figure 4 · p. 9
  • Linear+MILP outperforms NN+MILP in early iterations but is eventually overtaken.Source: §6 · p. 9

7. Conclusion and Future Work

The paper presents NN+MILP as a general framework for constrained discrete MBO and identifies formulation strengthening and solver warm starts as practical directions. Its scope is bounded by MILP-representable piecewise-linear models and discrete domains, while continuous or mixed-integer extensions remain future work.

7. Conclusion and Future Work

  • NN+MILP combines ReLU neural-network surrogates with MILP acquisition optimization and declarative constraints for discrete MBO.Source: §7 · p. 9
  • The approach performs well across discrete black-box problems with practical computational overhead using standard packages and hardware.Source: §7 · p. 9
  • More complex acquisition functions are possible when they remain MILP-representable, including Expected Improvement over ensembles of ReLU networks.Source: §7 · p. 9
  • The framework focuses on finite discrete domains, while continuous and mixed-integer domains require modifications and remain outside this paper’s scope.Source: §7 · p. 9

A. Strengthening the MILP formulation for neural networks

7. Conclusion and Future Work

A. Strengthening the MILP formulation for neural networks

B. Benchmarking Tasks

The benchmarks span biological sequences, synthetic neural objectives, discretized continuous functions, Ising models, and constrained subset-equality problems. The evaluation also compares NN+MILP with evolutionary, ensemble, radial-basis, and constraint-specific solvers under their respective experimental configurations.

B. Benchmarking Tasks

B.1. TfBind

  • TfBind uses length-8 DNA sequences with four nucleotide values and experimentally measured transcription-factor binding affinity.Source: §B.1 · p. 13

B.2. RandomMLP

  • RandomMLP problems use length-25 categorical inputs with alphabet size 5 and vary fully connected or convolutional architectures across random seeds.Source: §B.2 · p. 13

B.3. BBOB

  • The BBOB set samples two functions from each of five categories, spanning separable, conditioned, unimodal, and multimodal landscapes.Source: §B.3 · p. 14
  • BBOB objectives are discretized onto a grid with n = 10 and alphabet size 10, while preserving the continuous optimum on the grid.Source: §B.3 · p. 14

B.4. Ising

  • Constrained Ising experiments contain 30 instances across n ∈ {100, 200, 400}, paired with subset-equality constraints.Source: §B.4 · p. 14

C.1. NN+MILP

  • NN+MILP uses a single hidden layer of 16 neurons and solves each acquisition MILP with SCIP under a 500-second time limit.Source: §C.1 · p. 14

C.2. RegEvo

  • RegEvo combines tournament selection, crossover, and mutation, whereas NN+RegEvo uses the same neural surrogate but replaces MILP with batched evolutionary acquisition optimization.Source: §C.2 · pp. 14–15, §C.3 · p. 15

D. Binary vs Integer Variables

Binary encoding is preferred because it supports no-good constraints and was observed to outperform integer encoding. Across constrained Ising problems, exact acquisition optimization improves with scale, while larger surrogate networks provide little benefit.

D. Binary vs Integer Variables

  • Binary encoding supports no-good constraints and was empirically observed to outperform integer encoding for these problems.Integer variables use arbitrary or problem-specific orderings, whereas binary variables use one-hot encodings.Source: D. Binary vs Integer Variables · p. 16

E.1.1. NORMALIZED AREA UNDER THE CURVE (AUC)

  • AUC measures how quickly algorithms reach high reward, with higher normalized scores indicating better early performance.Scores are min/max normalized within each problem, assigning one to the best on-average algorithm and zero to the worst.Source: §E.1.1 · p. 17
  • AUC rankings qualitatively match final-reward rankings across unconstrained objective classes.Figure 6 reports normalized AUC distributions over all unconstrained problems.Source: §E.1.1 · p. 17, Figure 6 · p. 17

E.2.1. NORMALIZED MAX REWARD

  • NN+MILP considerably improves over NN+ConEvo on larger constrained Ising problems, although the methods perform similarly on smaller instances.The comparison uses normalized max-reward scores across problem sizes n = 100, 200, and 400.Source: §E.2.1 · p. 17, Figure 7 · p. 18

E.2.2. SURROGATE MODEL CAPACITY

  • Increasing the surrogate from 16 to 32 hidden-layer neurons yields no substantial improvement, suggesting limited training data is the bottleneck.This pattern holds for both NN+MILP and NN+ConEvo, including instances with 400 binary variables.Source: Figure 8 · p. 18, §E.2.2 · p. 19

E.2.3. RANDOM OPTIMIZER

NN+RejSample tests random feasible-point selection as a declarative-constraint baseline. Its poor performance, together with the prohibitive feasible-set sparsity, highlights the need for a stronger inner-loop optimizer.

E.2.3. RANDOM OPTIMIZER

  • NN+RejSample samples 10k feasible points uniformly at random and selects the point with the highest acquisition value.The surrogate and other settings remain identical to NN+MILP, but inner-loop optimization uses random search.Source: §E.2.3 · p. 19
  • For subset-equality constraints, feasible-point probability is < 10^-6 at n = 100, k = 10 and decreases for larger problems.The implemented custom sampler relies on the constraints’ special disjoint structure; interacting constraints may require harder-to-design samplers.Source: §E.2.3 · p. 19
  • NN+RejSample performs poorly even against ConEvo, so rejection sampling is unlikely to work well in highly constrained domains.The method was evaluated on n = 100 problems and not run at n = 200 or n = 400 because random search was expected to perform worse.Source: §E.2.3 · p. 19

E.3.1. ADDITIONAL TIMING RESULTS

MILP acquisition solves remain practically usable across the tested problem classes, but timing grows with iteration and surrogate size. The reported timing results are illustrative because experiments used heterogeneous parallel hardware.

E.3.1. ADDITIONAL TIMING RESULTS

  • Timing results are illustrative rather than rigorous because experiments used a cluster with variable standard CPU hardware, approximately 1G RAM, and at most 10 cores.The authors explicitly qualify the computational-overhead analysis on this basis.Source: §E.3.1 · p. 19
  • Average MILP solve time increases roughly linearly with iteration across problem classes, presumably as no-good constraints accumulate and surrogates use more data.Problem size does not predict runtime reliably: lower-dimensional TfBind instances had higher mean and variance than larger BBOB and RandomMLP instances.Source: §E.3.1 · pp. 19–20

E.3.2. SCALABILITY OF MILP TO LARGER NETWORKS

  • Larger surrogate networks increase solve times, but the largest tested network, FC(16,16), rarely times out and almost always finishes within the practical time limit.The timing table uses a 300s limit for TfBind8 benchmarks.Source: §E.3.2 · p. 20, Table 2 · p. 20
  • No architecture consistently optimizes better across instances, although the Linear model is almost always outperformed by the nonlinear alternatives.The tested architectures include FC(16), FC(32), FC(16,16), and Linear.Source: §E.3.2 · p. 20

F. Constrained binary quadratic problems from MINLPLib

NN+MILP is evaluated on constrained MINLPLib binary quadratic problems and NAS-Bench-101 architectures using declarative MILP formulations. It matches known optima on some large instances but struggles more as graph-partitioning instances grow.

F. Constrained binary quadratic problems from MINLPLib

  • NN+MILP matches the best known objective in at least one run on 20 of 61 reported MINLPLib instances, including pb302095 with 600 variables.Eleven instances were omitted from the table because the method could not find a solution within a 10% primal gap, though they remain in aggregate statistics.Source: F. Constrained binary quadratic… · p. 20
  • On graphpart clique problems, NN+MILP finds an optimum quickly at 60 variables but struggles to reach the best known solution at 180 variables.The larger-instance difficulty occurs under the same constraint structure with the current parameters and network size.Source: F. Constrained binary quadratic… · p. 20, Figure 11 · p. 21

G.1. Background

  • NAS-Bench-101 models cells as DAGs with up to V = 7 nodes and M = 9 edges, using operation assignments and edge variables under feasibility constraints.The goal is to maximize out-of-sample accuracy, while the benchmark includes validation and test accuracies from three independently trained replications.Source: §G.1 · p. 22, §G.2 · p. 22
  • NAS evaluation samples validation accuracy from a replication and uses a cumulative training-time budget of T = 5 × 10^6 seconds.Reported performance tracks the out-of-sample accuracy of the incumbent architecture over cumulative architecture training time.Source: §G.1 · p. 22

G.2. Domain Formulation

  • Upper-triangular edge variables impose topological ordering and acyclicity, while linear constraints enforce operation assignments, edge limits, connectivity, and null-node behavior.The formulation uses binary edge, one-hot operation, and null-operation variables.Source: §G.2 · pp. 22–23
  • Symmetry-breaking constraints canonicalize null-node placement by requiring null nodes to follow their topological successors, excluding isomorphic representations.The paper compares NN+MILP with symmetry-breaking constraints against simple NN+MILP without them.Source: §G.2 · p. 23

G.3. Additional results

Additional results examine NN+MILP across NAS-Bench-101, binary quadratic problems, and unconstrained and constrained benchmark problems. On NAS-Bench-101, adding symmetry-breaking constraints worsened overall outer-optimization performance, possibly by reducing exploration.

NAS-Bench-101

  • Including symmetry-breaking constraints worsened NN+MILP’s overall NAS-Bench-101 outer-optimization performance.The comparison uses incumbent architecture test accuracy over cumulative training time, averaged over 100 trials with 95% confidence bands.Source: §G.3 · p. 23, Figure 12 · p. 23
  • The authors hypothesize that the larger search space increases surrogate uncertainty and encourages NN+MILP to explore previously unvisited areas.Source: §G.3 · p. 23
  • A proposed future direction is augmenting training data with isomorphic graph representations created by randomly reordering nodes.Source: §G.3 · p. 23

Benchmark results

  • Table 3 evaluates binary quadratic problems by counting runs reaching primal gaps of at most 0%, 1%, and 10% relative to the best known primal feasible solution.Source: Table 3 · p. 24
  • The reported benchmark visualizations summarize best observed reward over iterations for unconstrained problems and constrained Ising-model problems.The unconstrained results average 20 trials, while constrained Ising results use 20 or 10 trials depending on problem size, or 10 trials for the second half.Source: Figure 13 · p. 25, Figure 14 · p. 26, Figure 15 · p. 27
Loading 2110.09569v3…