- 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
-
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.
-
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
-
The sharpening and diversity terms are defined on the original parameter , while the actual categorical solution distribution is determined by . These two notions are not equivalent. Different 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.
-
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
-
Does the implementation apply sharpening and diversity directly to , as described in Appendix B.2? If so, how do the authors justify these terms when different values can induce the same categorical distribution?
-
Can the authors separate the effect of the discrete gradient estimator from the effect of validity-restricted structural sampling in the CAMD experiment?
-
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?
-
For the 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
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.
| N | Relaxed | re | loo4 | loo8 | loo16 | loo32 | Valid draws in B | |||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | B | C | B | C | B | C | B | C | B | C | ||
| 4 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 7.80 | 45% |
| 6 | 5.13 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 5.31 | 33% |
| 8 | 14.02 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 15.33 | 14% |
| 10 | 13.63 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 16.18 | 10% |
| 12 | 15.90 | 17.99 | 19.50 | 19.50 | 19.50 | 19.50 | 19.50 | 18.52 | 19.50 | 19.50 | 19.50 | 2% |
Without the restriction, every sampled variant matches the relaxed estimator at 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, , 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.
| Instance | MILP | CLEBO-base | CLEBO-re | CLEBO-loo32 | Local search, 1 flip | Local search, best of 32 |
|---|---|---|---|---|---|---|
| Random network | ||||||
| n=100, 1x50 | 0.00 (10) | 0.65 (0) | 0.75 (0) | 0.05 (5) | 0.01 (9) | 0.01 (9) |
| n=100, 2x100 | 7.47 (0) | 0.95 (1) | 2.76 (0) | 0.05 (8) | 0.00 (10) | 0.11 (5) |
| n=100, 2x500 | 100.00 (0) | 1.25 (1) | 2.42 (0) | 0.01 (9) | 0.03 (8) | 0.04 (8) |
| n=100, 4x100 | 100.00 (0) | 3.13 (3) | 6.25 (0) | 0.53 (7) | 0.67 (4) | 1.61 (4) |
| n=100, 4x500 | 100.00 (0) | 2.50 (0) | 5.14 (0) | 0.17 (8) | 1.20 (3) | 1.13 (2) |
| n=1000, 2x100 | 7.62 (0) | 6.20 (0) | 30.60 (0) | 0.29 (7) | 9.40 (0) | 0.58 (3) |
| n=1000, 2x500 | 100.00 (0) | 1.18 (1) | 31.51 (0) | 0.03 (8) | 10.93 (0) | 0.49 (1) |
| n=1000, 4x100 | 48.14 (0) | 6.50 (0) | 35.80 (0) | 1.60 (4) | 12.09 (0) | 0.53 (6) |
| n=1000, 4x500 | 100.00 (0) | 2.45 (2) | 38.52 (0) | 0.20 (7) | 18.86 (0) | 2.09 (1) |
| Knapsack | ||||||
| n=100, 2x100 | 0.00 (8) | 0.86 (3) | 0.48 (1) | 0.52 (0) | 2.33 (0) | 2.27 (3) |
| n=100, 2x500 | 0.00 (6) | 0.55 (6) | 0.20 (2) | 0.22 (1) | 2.24 (0) | 2.54 (2) |
| n=100, 4x100 | 0.34 (4) | 0.42 (4) | 0.38 (3) | 0.43 (2) | 2.14 (0) | 2.49 (2) |
| n=100, 4x500 | 0.15 (1) | 0.24 (4) | 0.03 (5) | 0.06 (5) | 2.14 (0) | 2.19 (3) |
| n=1000, 2x100 | 0.00 (8) | 0.80 (1) | 0.59 (1) | 0.54 (0) | 1.34 (0) | 1.41 (0) |
| n=1000, 2x500 | 0.00 (10) | 0.58 (0) | 0.41 (0) | 0.49 (0) | 0.97 (0) | 1.41 (0) |
| n=1000, 4x100 | 0.00 (9) | 0.59 (1) | 0.51 (0) | 0.53 (0) | 1.73 (0) | 1.42 (0) |
| n=1000, 4x500 | 0.00 (9) | 0.53 (1) | 0.67 (0) | 0.59 (0) | 1.72 (0) | 1.40 (0) |
| Molecular design (CAMD), SAGE | ||||||
| N=4 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=6 | 0.00 | 3.39 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=8 | 0.00 | 8.58 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=10 | 0.00 | 15.77 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=12 | 12.80 | 18.46 | 0.00 | 0.00 | 0.00 | 0.00 |
| Molecular design (CAMD), GAT | ||||||
| N=4 | – | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=6 | – | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=8 | – | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=10 | – | 18.68 | 0.00 | 0.00 | 0.00 | 0.00 |
| N=12 | – | 38.18 | 0.00 | 6.06 | 0.36 | 0.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 and far behind at , 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 , 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 , 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 . 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.
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 p, not on π(p)=softmax(τp). The reviewer is correct, and we are grateful for this observation. The choice within a group is governed by π(p), and adding a constant to every coordinate of a group changes p without changing π. So the sharpening term can be satisfied without π selecting one alternative, and the diversity term can reward differences between chains that change no choice. In the revision both terms are defined on π: the diversity term is the standard deviation of π across chains, and the sharpening term of a group with K alternatives is the generalized entropy that PQQA defines for variables with K values [1, Appendix B], sK(π)=1−(K−1)((K−1)α−1+1)1∑k=1K(Kπk−1)α, which is 0 when π selects one alternative, 1 when π is uniform, and equal to the binary term at K=2. For a binary variable p 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 p (as the original submission) and on π (revised). Nothing else differs between the two runs, and the p columns reproduce the submitted results exactly. Bold marks a change. † MILP stopped at the one-hour limit.
Table R1. SAGE
Table R2. GAT
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=6, and they improve on GAT at N=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.
With the terms on π, the mean and median objective improve in all almost all settings. For this reason we use π as the default, and these results will be added to the appendix.