acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
combinatorial optimization, constraint learning, integer programming, constrainted optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1rm9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies binary optimization problems where a pretrained neural network appears in the objective or constraints. The proposed CLEBO method avoids explicitly encoding the network into MILP. Instead, it performs massively parallel optimization over relaxed or probabilistic binary variables on GPU. CLEBO combines annealing, multiple search chains, diversity regularization, constraint penalties, and structural reparameterization. For learned components, it compares direct differentiation on fractional inputs with discrete score-function estimators, including REINFORCE and leave-one-out estimators that evaluate the network only on binary samples. The method is evaluated on random neural objectives, neural-constrained knapsack, and molecular design with GNN objectives, with MILP baselines where available.

Critical strengths
  1. The discrete gradient formulation is useful. The sampled variants evaluate the learned component only on binary inputs, avoiding direct dependence on potentially unreliable gradients at fractional inputs.

  2. The method is practical and scalable. GPU-parallel search, structural constraint handling, and penalty-grid evaluation allow CLEBO to obtain strong solutions on several instances where the MILP formulation becomes difficult within the time limit.

Critical weaknesses
  1. The sharpening and diversity terms are defined on the original parameter pp, while the actual categorical solution distribution is determined by π(p)=softmax(τp)\pi(p)=\mathrm{softmax}(\tau p). These two notions are not equivalent. Different pp values can induce the same categorical distribution, so parameter diversity does not necessarily imply solution-distribution diversity. The paper should clarify this mechanism and provide a corresponding ablation or diagnostic.

  2. The experiments do not sufficiently isolate the source of the reported improvements. In CAMD, the sampled variants use validity-restricted structural sampling, while the relaxed variant evaluates fractional molecules without the same restrictions. Therefore, the difference is not only the gradient estimator. In addition, there is no matched-budget direct binary-search baseline, although LOO uses substantially more neural evaluations. These comparisons are needed to determine what actually drives the improvement.

Questions for authors
  1. Does the implementation apply sharpening and diversity directly to pp, as described in Appendix B.2? If so, how do the authors justify these terms when different pp values can induce the same categorical distribution?

  2. Can the authors separate the effect of the discrete gradient estimator from the effect of validity-restricted structural sampling in the CAMD experiment?

  3. Under equal wall-clock time or equal neural-evaluation budgets, how does CLEBO compare with a direct binary black-box search baseline and with cheaper CLEBO variants given more iterations or restarts?

  4. For the n=1000,  2×100n=1000,\;2\times100 knapsack setting, Table 7 appears to indicate that all MILP instances were proven optimal, while Table 1 reports that MILP reaches the pooled best-known solution on only 8 of 10 instances. Could the authors clarify this discrepancy and the objective-matching tolerance used in the tables?

4 comments
AuthorsOpenReview ↗

Reply to Reviewer 1rm9

We thank the reviewer for the careful and constructive review. The first weakness in particular pointed us to a more principled placement of two terms of the method, and adopting it improved both our results and the fairness of the relaxed baseline. We reply to each point below, with new experiments when applicable. All changes are presented here and will be included in the final revision.

W1, Q1 — Sharpening and diversity are defined on pp, not on π(p)=softmax(τp)\pi(p)=\mathrm{softmax}(\tau p). The reviewer is correct, and we are grateful for this observation. The choice within a group is governed by π(p)\pi(p), and adding a constant to every coordinate of a group changes pp without changing π\pi. So the sharpening term can be satisfied without π\pi selecting one alternative, and the diversity term can reward differences between chains that change no choice. In the revision both terms are defined on π\pi: the diversity term is the standard deviation of π\pi across chains, and the sharpening term of a group with KK alternatives is the generalized entropy that PQQA defines for variables with KK values [1, Appendix B], sK(π)=1−1(K−1)((K−1)α−1+1)∑k=1K(Kπk−1)αs_K(\pi) = 1-\frac{1}{(K-1)\big((K-1)^{\alpha-1}+1\big)}\sum_{k=1}^{K}\big(K\pi_k-1\big)^{\alpha}, which is 0 when π\pi selects one alternative, 1 when π\pi is uniform, and equal to the binary term at K=2K=2. For a binary variable pp is the probability, so the random-network and knapsack results are unaffected.

Ablation 1. Tables R1 and R2 extend the CAMD rows of Table 1 and the GAT results of Appendix E to every sampler variant. For each CLEBO variant, the two columns report the best feasible objective (higher is better) with the terms on pp (as the original submission) and on π\pi (revised). Nothing else differs between the two runs, and the pp columns reproduce the submitted results exactly. Bold marks a change. † MILP stopped at the one-hour limit.

Table R1. SAGE

NMILPbasereloo4loo8loo16loo32
pπpπpπpπpπpπ
47.807.807.807.807.807.807.807.807.807.807.807.807.80
65.315.135.135.315.315.135.315.135.315.135.315.135.31
815.3314.0214.0215.3315.3315.3315.3315.3315.3315.3315.3315.3315.33
1016.18†8.3813.6316.1816.1816.1816.1816.1816.1816.1816.1816.1816.18
1217.00†7.8015.9019.5019.5019.5019.5019.5019.5019.5019.5019.5019.50

Table R2. GAT

Nbasereloo4loo8loo16loo32
pπpπpπpπpπpπ
43.1010.5010.5010.5010.5010.5010.5010.5010.5010.5010.5010.50
67.299.829.829.829.829.829.829.829.829.829.829.82
816.7216.7216.7216.7216.7216.7216.7216.7216.7216.7216.7216.72
1012.8813.2216.2516.2516.2516.2516.2516.2516.1216.2516.2516.25
128.4210.8215.9517.4911.3617.4312.2316.439.3916.439.8716.43

No variant is worse under the revised placement in any of the 60 cases, and 16 improve. The sampled estimators are unchanged on SAGE, except that all four LOO variants now attain the MILP optimum at N=6N=6, and they improve on GAT at N=12N=12. The relaxed estimator improves on both models, while the sampled estimators remain ahead of the relaxed estimator, but the margin is smaller than the originally reported values. Beyond the best objectives (our primary metric), we also report the mean/median performance across feasible chains in Table R3 for three variants. "Feasible chains" is the share of chains whose solution is feasible, and the median and mean are taken over the objectives of the feasible chains.

Table R3.

NVariantFeasible chainsMedian objectiveMean objective
pπpπpπ
8base10%81%-12.08-0.12-12.50-1.40
10base13%74%-13.25-1.45-14.25-2.82
12base14%75%-14.44-0.15-14.52-1.72
8re26%21%9.509.308.408.99
10re25%22%6.037.524.507.45
12re28%30%4.629.112.978.85
8loo3219%18%10.1311.789.0711.56
10loo3219%16%6.849.814.779.35
12loo3218%22%0.4310.830.2710.60

With the terms on π\pi, the mean and median objective improve in all almost all settings. For this reason we use π\pi as the default, and these results will be added to the appendix.

W2, Q2 — Separating the gradient estimator from validity-restricted sampling. We agree that in CAMD there were two changes at once, the gradient estimator and the restriction of every draw to valid molecules, so we added sampled variants with no restriction, where each choice is drawn from its softmax over all alternatives and nothing is repaired. Table R4 compares the relaxed estimator (A) with every sampled variant without the restriction (B) and with it (C) on SAGE, where "Valid draws" is the share of unrestricted draws that are valid molecules at termination and bold marks a change.

Table R4.

NRelaxedreloo4loo8loo16loo32Valid draws in B
ABCBCBCBCBC
47.807.807.807.807.807.807.807.807.807.807.8045%
65.135.315.315.315.315.315.315.315.315.315.3133%
814.0215.3315.3315.3315.3315.3315.3315.3315.3315.3315.3314%
1013.6316.1816.1816.1816.1816.1816.1816.1816.1816.1816.1810%
1215.9017.9919.5019.5019.5019.5019.5018.5219.5019.5019.502%

Without the restriction, every sampled variant matches the relaxed estimator at N=4N=4 and exceeds it at every larger size, so the advantage of the sampled variants persists without the validity masks. The masks provide additional gains at the largest size, N=12N=12, particularly for CLEBO-re and CLEBO-loo16. The random-network and knapsack benchmarks use no structural sampling, so the comparisons there isolate the estimator. As an addition, we note that the validity restrictions are a feature of the sampled variants, that do not have an obvious analogue in the relaxed setting, so we see this as a strength of the method itself, that may be particularly useful in structured problems beyond CAMD.

W2, Q3 — Comparison at matched budgets. Cheaper CLEBO variants and wall clock. Our primary goal was to provide a collection of CLEBO variants that deliver high-quality feasible solutions at different computational costs. The results include near-optimal solutions where MILP is tractable and substantial improvements over its time-limited incumbent on several challenging instances. We therefore evaluate the variants under a common optimization protocol and report both solution quality and runtime, demonstrating the practical trade-offs available within the framework. Comparing how the same computational budget could be allocated among additional samples, iterations, or restarts would further inform the choice among these variants. We will clarify that the reported results characterize their quality–cost trade-offs, without establishing an estimator ranking under matched computational budgets.

W2, Q3 — Comparison at matched budgets (continued). Direct black-box search at equal network evaluations. We implemented a parallel local search on binary solutions, where each chain proposes single bit flips and keeps a flip when the penalized objective improves. To our knowledge, a direct local search on binary solutions has not been evaluated in this setting before. We see it as a useful baseline in its own right: it needs only forward evaluations of the network, applies to any architecture, and gives future work a simple reference point between the MILP and gradient-based methods. The existing local search heuristics for optimization over trained networks [2, 3] move between the linear regions of a ReLU network by solving LP or MILP subproblems, so they do not treat the network as a black box, and natively apply only in settings with continuous decision variables. Table R5 extends Table 1 with two versions, both with the same number of chains and steps as CLEBO. The first tries one flip per step, which matches the network evaluations of CLEBO-base and CLEBO-re. The second tries 32 different flips per step and keeps the best one, which matches the evaluations of CLEBO-loo32. Conventions follow Table 1, and the CAMD rows use the revised placement from W1. The GAT rows have no MILP entry, since GAT has no MILP embedding. We match on network evaluations and not on wall clock because the local search was run on CPU.

Table R5.

InstanceMILPCLEBO-baseCLEBO-reCLEBO-loo32Local search, 1 flipLocal search, best of 32
Random network
n=100, 1x500.00 (10)0.65 (0)0.75 (0)0.05 (5)0.01 (9)0.01 (9)
n=100, 2x1007.47 (0)0.95 (1)2.76 (0)0.05 (8)0.00 (10)0.11 (5)
n=100, 2x500100.00 (0)1.25 (1)2.42 (0)0.01 (9)0.03 (8)0.04 (8)
n=100, 4x100100.00 (0)3.13 (3)6.25 (0)0.53 (7)0.67 (4)1.61 (4)
n=100, 4x500100.00 (0)2.50 (0)5.14 (0)0.17 (8)1.20 (3)1.13 (2)
n=1000, 2x1007.62 (0)6.20 (0)30.60 (0)0.29 (7)9.40 (0)0.58 (3)
n=1000, 2x500100.00 (0)1.18 (1)31.51 (0)0.03 (8)10.93 (0)0.49 (1)
n=1000, 4x10048.14 (0)6.50 (0)35.80 (0)1.60 (4)12.09 (0)0.53 (6)
n=1000, 4x500100.00 (0)2.45 (2)38.52 (0)0.20 (7)18.86 (0)2.09 (1)
Knapsack
n=100, 2x1000.00 (8)0.86 (3)0.48 (1)0.52 (0)2.33 (0)2.27 (3)
n=100, 2x5000.00 (6)0.55 (6)0.20 (2)0.22 (1)2.24 (0)2.54 (2)
n=100, 4x1000.34 (4)0.42 (4)0.38 (3)0.43 (2)2.14 (0)2.49 (2)
n=100, 4x5000.15 (1)0.24 (4)0.03 (5)0.06 (5)2.14 (0)2.19 (3)
n=1000, 2x1000.00 (8)0.80 (1)0.59 (1)0.54 (0)1.34 (0)1.41 (0)
n=1000, 2x5000.00 (10)0.58 (0)0.41 (0)0.49 (0)0.97 (0)1.41 (0)
n=1000, 4x1000.00 (9)0.59 (1)0.51 (0)0.53 (0)1.73 (0)1.42 (0)
n=1000, 4x5000.00 (9)0.53 (1)0.67 (0)0.59 (0)1.72 (0)1.40 (0)
Molecular design (CAMD), SAGE
N=40.000.000.000.000.000.00
N=60.003.390.000.000.000.00
N=80.008.580.000.000.000.00
N=100.0015.770.000.000.000.00
N=1212.8018.460.000.000.000.00
Molecular design (CAMD), GAT
N=4–0.000.000.000.000.00
N=6–0.000.000.000.000.00
N=8–0.000.000.000.000.00
N=10–18.680.000.000.000.00
N=12–38.180.006.060.360.36

W2, Q3 — Comparison at matched budgets (continued). Direct black-box search at equal network evaluations (continued). At matched forward-evaluation budgets, CLEBO-loo32 achieves a lower mean gap than best-of-32 local search in 7 of the 9 random-network configurations and in all 8 knapsack configurations. On knapsack this also holds for CLEBO-base and CLEBO-re against both local search versions. On the random network, the one-flip version is competitive at n=100n=100 and far behind at n=1000n=1000, where only CLEBO-re is behind it, and the best-of-32 version closes most of that gap. On CAMD, both local search versions match the best objectives of the sampled CLEBO variants at every tested size except GAT at N=12N=12, where CLEBO-re is ahead of both and both are ahead of CLEBO-loo32. Local search uses the same validity-restricted construction as CLEBO for CAMD, incorporating structural constraints into candidate generation. This shows that high-quality solutions to these instances can be found through simple discrete local search, even at sizes where the corresponding MILP formulation remains computationally challenging. Direct local search is therefore a new and useful baseline for this setting, although at matched budgets it does not match CLEBO on knapsack and on most random-network configurations, and on CAMD the best result at the largest GAT size comes from CLEBO-re.

Q4 — The n=1000n=1000, 2×1002\times100 knapsack setting in Table 1 and Table 7. There is no contradiction, and we thank the reviewer for catching an under-explained caption. All ten MILP runs on that configuration terminate with Gurobi's optimal status, a relative gap tolerance of 10−410^{-4}. On two of the ten instances a sampler returned a feasible solution slightly better than Gurobi's incumbent. Both differences are inside that tolerance, so both are consistent with Gurobi's certificate. The count of instances attaining the best-known solution in Table 1 uses an exact match, so the MILP is counted on 8 of 10 while its mean gap rounds to 0.00. Table 7 marks a configuration only when at least one instance was not proven optimal within the time limit, which is why it carries no mark here. We will clarify this in the revision.

We hope these additions address the reviewer's concerns. If analysis in a further direction would affect the reviewer's assessment and score, we would be happy to provide it.

References

  • [1] Ichikawa et al. Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling. ICLR 2025.
  • [2] Tong et al. Optimization Over Trained Neural Networks: Taking a Relaxing Walk. CPAIOR 2024.
  • [3] Perakis et al. Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling. arXiv:2205.14189, 2022.
Reviewer_oDFBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CLEBO, a framework for binary optimization over pretrained neural-network objectives and constraints. It combines parallel annealed optimization with three gradient estimators: CLEBO-base (direct differentiation through relaxed inputs), CLEBO-re (single-sample REINFORCE), and CLEBO-loo (a multi-sample leave-one-out estimator). Experiments on random neural objectives, neural-constrained knapsack problems, and molecular design show promising scalability and competitive solution quality compared with MILP baselines.

Critical strengths

1.The paper is generally well-written and clearly identifies the key challenges of binary optimization over pretrained neural networks, an interesting problem with potential real-world applications.

2.Incorporating CRA and PQQA annealing into optimization over pretrained neural-network objectives and constraints is a reasonable and promising approach.

3.The experimental results demonstrate promising performance, particularly for CLEBO-re and CLEBO-loo, across several binary optimization settings.

Critical weaknesses

1.Although this paper proposes a meaningful learning framework for binary optimization over pre-trained neural networks, much of the proposed framework builds upon existing annealing and sampling-based optimization methods, making its theoretical contribution somewhat incremental.

2.Although molecular design is included as an application, the paper provides limited discussion and comparison with existing optimization methods for molecular design. Moreover, no other compelling application scenarios are presented. This limits my assessment of the paper's practical utility.

3.Insufficient disscussion on related work of binary gradient estimators. The sampled variants rely on REIFORCE and LOO baselines, but the paper does not adequately discuss similar estimators such as ARM, DisARM.

[1]ARM: Augment-REINFORCE-merge gradient for stochastic binary networks. ICLR 2019.

[2]Disarm: An antithetic gradient estimator for binary latent variables. NeurIPS 2020.

Questions for authors

1.Beyond molecular design, could the authors discuss broader application scenarios? This is important for assessing practical value.

2.Could the authors review related work on binary gradient estimators? Comparative experiments are needed to properly evaluate the theoretical contribution.

4 comments
AuthorsOpenReview ↗

Reply to Reviewer oDFB

We thank the reviewer for recognizing the relevance of optimization over pretrained neural networks, the clarity of our presentation, and the experimental performance of CLEBO-re and CLEBO-loo.

W1 — Relationship to existing annealing methods. We agree that CLEBO builds on established annealing methods, particularly CRA and PQQA, and we will revise the paper to distinguish more clearly what is inherited from these approaches. Our contribution is not a new general-purpose annealing method. Rather, CLEBO extends this promising optimization paradigm to binary optimization over pretrained neural networks, a setting not addressed by existing annealing methods and in which a direct application is unreliable: the network may provide misleading gradients at fractional inputs, learned and analytic components require fundamentally different gradient treatments, and learned, structural, and analytic constraints must be handled within a common optimization procedure. Addressing these obstacles requires more than substituting a neural network into the annealing objective. CLEBO evaluates learned components at binary samples while retaining exact pathwise gradients for analytic terms, enforces suitable combinatorial constraints by construction, and searches scale-normalized penalty weights in parallel. Taken together, these components yield an architecture-agnostic, GPU-native method that requires only network evaluations and gradients, including for architectures such as graph attention networks that are not readily or directly representable by standard MILP embeddings.

Hence, we adapt established annealing principles to binary optimization problems in which a trained neural network represents part of the objective or constraint system, a setting not directly addressed by the cited annealing methods. Moreover, the experiments show that the extension is practically consequential: CLEBO remains effective on networks and architectures for which exact embedding in MILP formulations is intractable or unavailable, while producing competitive feasible solutions where such comparisons are possible.

We will clarify this relationship and limit our novelty claims accordingly.

W2, Q1 — Application scope and practical utility. We agree that the paper should better substantiate CLEBO’s applicability beyond molecular design. Our experiments were designed to cover representative classes of optimization over pretrained neural networks:

  • random-network instances provide a controlled and broadly applicable test bed, following a longstanding tradition of using randomized instances to evaluate optimization methods independently of any single application [1, 2, 3];
  • neural-constrained knapsack captures the important setting in which a learned model defines feasibility; and
  • molecular design demonstrates the framework on a structured application with a learned graph-neural objective and hard combinatorial constraints.

We agree that the molecular-design experiment should be better situated within its application literature. We will add a concise discussion of optimization-based CAMD, evolutionary search, reinforcement learning, and molecular generative models. At the same time, we will clarify that molecular design is used as a demanding and representative application of the proposed general framework, rather than being the paper’s central object of study or the domain in which it seeks a comprehensive methodological comparison.

The potential scope is nevertheless considerably broader: neural networks have been embedded as objectives or constraints in applications including chemical-process design and operation, power systems, planning, facility and resource allocation, energy production, data-center scheduling, and engineering design [4]. In such constraint-learning applications, the neural network serves as a proxy for an unknown or difficult-to-handle mathematical relationship. CLEBO addresses the resulting downstream optimization problem, while validation of the proxy and of the decisions obtained from it remains application-specific. We will revise the paper to explain more clearly the rationale and complementary roles of the selected problem classes, discuss additional application domains, and substantiate how CLEBO’s architecture-agnostic treatment of trained networks could apply to them, while recognizing that application-specific validation remains important future work.

W3, Q2 — Binary gradient estimators. We thank the reviewer for highlighting ARM and DisARM. CLEBO’s novelty lies in integrating discrete gradient estimation into constrained, annealed binary optimization over pretrained neural objectives and constraints. This allows learned components to be evaluated on discrete inputs, avoiding unreliable gradients at fractional inputs, while retaining exact pathwise gradients for analytic terms. The contribution is this use of discrete estimation within the optimization framework; we do not propose a new binary gradient estimator or provide an extensive analysis comparing alternatives. REINFORCE and LOO are established estimators that instantiate this design and provide a common interface across the Bernoulli and structured conditional distributions used in our experiments. ARM and DisARM offer alternative choices for the Bernoulli settings and can be incorporated without changing the surrounding framework. The particular estimator choice is therefore modular, rather than the basis of our novelty claim. We will add a short discussion of related discrete gradient estimators, including ARM and DisARM, with appropriate citations, and clarify their relationship to CLEBO and the distinction between the framework’s contribution and its estimator implementations.

References

  • [1] Perakis et al. Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling. arXiv:2205.14189, 2022.
  • [2] Tong et al. Optimization Over Trained Neural Networks: Taking a Relaxing Walk. CPAIOR 2024.
  • [3] Tong et al. Optimization over Trained Neural Networks: Going Large with Gradient-Based Algorithms. CPAIOR 2026.
  • [4] Fang et al. Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial. arXiv:2610.35505, 2026.

I thank the authors for their detailed rebuttal.

The paper is well-motivated, as it extends the optimization over pretrained neural networks paradigm to discrete binary optimization.​​ However, unlike general-purpose binary optimization solvers, whether this extension constitutes a meaningful framework depends heavily on its effectiveness in practical, real-world scenarios.

My primary concerns are twofold:

1.​ In the context of molecular design (the primary focus of this paper) the proposed method should be compared against existing state-of-the-art approaches, or its specific advantages over current molecular design methods should be clearly articulated.

2.​ The paper needs to sufficiently explore other potential real-world application domains and empirically substantiate its efficacy in those areas.

If at least one of these concerns were adequately addressed, I would be convinced of the practical value of this work. Although the authors provided several references (published in CPAIOR or arXiv) in the rebuttal, I still feel that as a general optimization framework, its applicability has not been thoroughly validated. For this reason, I decide to maintain my score.

We thank the reviewer for the follow-up, and for stating what would change the assessment. We believe that those concerns can be framed as two expectations of what the paper should be: (1) a paper about molecular design; or (2) a paper selling a new methodology. We invite the reviewer to consider a different framing below. This is a paper proposing new algorithms for an established methodology, but targeting two underserved subcategories, and for which molecular design was used as one of the benchmarks:

  • The established methodology: embedding neural networks in mathematical optimization models, often denoted as constraint learning. This methodology has found a wealth of applications in optimization problems that have components that are highly nonlinear or entirely learned from data [3, 4]. Examples include humanitarian food aid and chemotherapy design [3], stochastic and robust decision problems such as facility location and capital budgeting [5, 6], and planning and process engineering [7, 8]. That leads to optimization models formulated as a combination of objective, constraints, and neural networks.
  • The underserved subcategories: because these models need to be solved by optimization algorithms with exponential time worst-case, cost-effective approaches have been developed based on heuristics that exploit the structure of these optimization models. However, to our knowledge, they still miss two important categories: (i) none had yet been proposed for handling discrete decision variables, of which the binary case is a very important one for combinatorial optimization problems in general; and (ii) almost all prior work assumed the use of ReLU activation functions, which greatly limits what can be modeled in constraint learning: a method that needs only evaluations and gradients of the network can be applied more broadly than existing heuristics.
  • The molecular design scope: we have used this application because (a) it is a hard optimization problem; (b) the neural network is embedded as the objective function, which is different from the knapsack case; and (c) it shows how the approach adapts to a trained graph neural network (not as common yet in other applications) while also having additional constraints beyond the neural network embedding. Hence, we use it to test our algorithm and not to claim the best way to design molecules, which is an active area with extensive work on generative, reinforcement learning and evolutionary approaches. For this reason, we compare with the exact MILP approach of [1, 2] because that is the line of work we target.
  • Experimental study scope. Evaluating a new algorithm on benchmark problem classes, each chosen to test a specific capability, is the precedent in optimization research, including methodological work on optimization over trained networks [2, 9]. Our three benchmarks test scaling with network size and input dimension (random networks), learned feasibility alongside analytic constraints (knapsack), and structured graph optimization with a different architecture (molecular design).

We hope this framing clarifies the contribution, and we would be grateful if the reviewer would reconsider our work from this perspective.

References

  • [1] Zhang et al. Augmenting optimization-based molecular design with graph neural networks. Computers & Chemical Engineering, 2024.
  • [2] Zhang et al. Optimizing over trained GNNs via symmetry breaking. NeurIPS 2023.
  • [3] Maragno et al. Mixed-integer optimization with constraint learning. Operations Research, 2025.
  • [4] Fajemisin et al. Optimization with constraint learning: a framework and survey. European Journal of Operational Research, 2024.
  • [5] Dumouchelle et al. Neur2SP: Neural two-stage stochastic programming. NeurIPS 2022.
  • [6] Dumouchelle et al. Neur2RO: Neural two-stage robust optimization. ICLR 2024.
  • [7] Say et al. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. IJCAI 2017.
  • [8] Schweidtmann and Mitsos. Deterministic global optimization with artificial neural networks embedded. Journal of Optimization Theory and Applications, 2019.
  • [9] Tsay et al. Partition-based formulations for mixed-integer optimization of trained ReLU neural networks. NeurIPS 2021.
Reviewer_f2vxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper CLEBO tries to solve binary optimization over neural networks with analytic and learned constraints, and the optimization function is treated as a black box. It is claimed to be the first heuristic method to optimize trained neural networks with binary inputs, instead of relying on MILP encodings. As treating the pretrained network treated as a black box, CLEBO has generality and is independent from net architectures.

There are three main designs, the first is sampled gradient estimator, it is used to estimate gradients at fractional inputs. The second is structural constraints, special structures such as tree in molecular design, are enforced by softmax reparameterization or sequential parent selection. The third one is the scale-normalized penalties with a parallel penalty grid, to prevent per-instance tuning.

Critical strengths

See above. The designs are reasonable, and experiments show good performance.

Critical weaknesses

W1. No guarantees on solutions. CLEBO is heuristic and certifies neither optimality nor feasibility. Unlike MILP, it proves optimality whenever it finishes.

W2. It is only designed for binary variables. Integer problems are not feasible, giving a huge limitation.

W3. The computation costs are huge, thus the speed boosting is minor over MILP. At the same time, on random networks, MILP's one-hour failure is not fair to compare. The comparison to MILP is setting-specific, not leading to the conclusion that CLEBO is state-of-the-art.

Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Reply to Reviewer f2vx

We appreciate the reviewer’s recognition of CLEBO’s novelty and architecture-agnostic treatment of trained neural networks.

W1 — Relationship to MILP. We welcome the opportunity to clarify CLEBO’s intended relationship to MILP methods and the scope of our comparison.

We agree that CLEBO is heuristic and does not replace MILP as an exact optimization approach. But while MILP can certify global optimality when the optimality gap is closed, reaching such a certificate may be computationally prohibitive within a practical time limit. Consistent with this distinction, CLEBO does not guarantee that its search will find a feasible solution; however, every binary solution it returns and that we report is directly verified against the optimization model constraints and is therefore feasible. Accordingly, our comparison targets solution quality in regimes where exact MILP encodings become computationally limiting. ReLU networks are convenient to encode in MILP, but their standard big-M formulation has a weak linear relaxation, while stronger alternatives are substantially larger and still do not provide a practical convex-hull formulation for an entire network. The one-hour limit therefore exposes the scalability issue motivating CLEBO rather than establishing universal superiority over MILP. More broadly, when exact solution becomes too expensive, heuristics are routinely used to advance incumbents without certificates. This tradeoff is particularly relevant in constraint learning, where embedding a trained network can make an already difficult discrete model much harder to solve.

CLEBO should therefore be read as a complementary heuristic for this expensive regime, not as a replacement for exact MILP. We will revise the paper to state this scope explicitly, clarify that CLEBO does not guarantee finding a feasible solution but directly verifies the feasibility of every solution it returns, and avoid any implicit claim beyond the tested setting.

W2 — Focus on binary decision variables. We agree that CLEBO’s current restriction to binary decision variables limits its applicability to more general integer problems. That said, binary optimization has broad practical applicability, with natural formulations for many selection, assignment, routing, scheduling, and network-design problems. Binary decisions therefore define a practically important scope in their own right. Moreover, developing methods tailored to well-defined problem classes is an established approach in both classical and learning-based optimization; our aim is likewise to establish an effective framework for binary optimization over pretrained neural objectives and constraints. Extending CLEBO to general integer or mixed-variable problems is a natural direction for further research, involving additional choices in representation, gradient estimation, and constraint handling. We will revise the paper to clarify both the current scope and this extension direction.

W3 — Computational cost. CLEBO provides variants with different tradeoffs of quality and runtime: on the largest knapsack configuration, for example, the inexpensive variants run in 25 to 28 seconds and remain within 0.53 to 0.67% of the best-known solution, while Gurobi averages 2,066 seconds and obtains better objectives when feasible. We compare methods using both a common one-hour runtime and the time Gurobi takes to first match each CLEBO solution. Gurobi often does so on knapsack, but stronger sampled solutions on larger random-network and molecular-design instances remain unmatched within the hour. We will revise the paper to emphasize this setting-dependent tradeoff rather than claim universal superiority over MILP.

Taken together, these clarifications delineate a focused but meaningful contribution to the broader challenge of optimization over trained neural networks. As these revisions directly address the stated weaknesses, we ask that the reviewer please reconsider the score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.