acceptodds
Under review as a conference paper at ICLR 2027

LEMON: Landscape-Equivalent Continuous Relaxation for Multi-State Optimization

Abstract

Many combinatorial problems require assigning one of several discrete values to each variable, with an objective that couples pairs or larger groups of variables. Finding an assignment that globally minimizes this objective is often intractable, so a practical alternative is to seek one that cannot be improved by changing a single variable. Searching for such assignments can still be expensive, motivating the use of continuous relaxations and gradient-based optimization. The challenge is that local minima of a relaxation need not correspond to locally optimal discrete assignments. We introduce LEMON (Landscape Equivalent Multi-State Optimization), a continuous relaxation that preserves this correspondence. We represent each discrete variable by a probability vector over its possible values. The discrete objective is then extended to these vectors and augmented with a regularization term that promotes discrete assignments. Our main result shows that the local minima of the resulting continuous objective correspond exactly to the local optima of the original discrete problem. LEMON uses a projected variant of ADAM to optimize the probability vectors, decodes them into a discrete assignment, and then checks feasibility and local optimality. We evaluate LEMON on maximum independent set, graph coloring, Max--Cut, and -way number partitioning. It matches the reference optimum on maximum independent set instances and achieves the known chromatic number on coloring instances. It also closely matches public-best Max--Cut values and outperforms specialized number-partitioning baselines, while certifying local optimality across all tasks.

Primary area:
optimization
Keywords:
Combinatorial Optimization, Continuous Relaxation, Multi-State Optimization, Landscape Equivalence, Certified Local Optimality

Reviews

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

This paper proposes LEMON, a continuous relaxation framework for finite-state combinatorial optimization. Each discrete variable is represented by a probability vector on a simplex, and a concave attractor is added to remove fractional local minima. The main theoretical result shows when the continuous local minima correspond exactly to the one-flip local minima of the original discrete problem. The solver then uses projected ADAM, discrete decoding, exact verification, and optional correction. Experiments cover MIS, graph coloring, Max-k-Cut, and k-way number partitioning.

Critical strengths
  1. The product-simplex representation preserves the native categorical one-variable neighborhood rather than replacing one label change with multiple binary flips. The landscape-equivalence result also applies to arbitrary finite-order interactions and provides a sharp characterization of the admissible attractor slope.

  2. The separation between continuous search and discrete certification is a strong design choice. The method does not assume that projected ADAM converges to a valid discrete local optimum; instead, it verifies feasibility and exact one-flip changes after decoding.

Critical weaknesses
  1. The Max-5-Cut ablation in Table 5 appears inconsistent with the stated local-optimality verification procedure. The paper states that the No-ADAM and Projected-ADAM variants use the same discrete correction procedure, and that Max-k-Cut post-processing ends with an exhaustive check of all one-vertex moves. Therefore, both final solutions should be one-vertex local optima. For a nonnegative weighted kk-cut, every such local optimum satisfies C≥k−1kWC \geq \frac{k-1}{k}W, where WW is the total edge weight. Thus, for paired k=5k=5 instances, C‾NoADAM≥0.8,C‾ADAM\overline{C}{\mathrm{NoADAM}} \geq 0.8,\overline{C}{\mathrm{ADAM}}. However, Table 5 reports 895.82 versus 1372.40, while 0.8×1372.40=1097.920.8\times1372.40=1097.92. The reported values therefore violate this necessary condition. This suggests that the reported values, experimental protocol, weight assumptions, or actual post-processing procedure differ from the description.

  2. The NPP implementation description does not clearly explain the large improvement attributed to projected ADAM. The manuscript states that NPP starts from an LPT partition embedded at simplex vertices and then applies projected ADAM using Eq. (21), while the other blocks remain at vertices. For positive inputs, the LPT solution is already locally optimal with respect to a single-item move under the max-minus-min discrepancy objective. At such a vertex, the stated gradient gives gi,b−gi,si=Δib(s)+2η>0g_{i,b}-g_{i,s_i}=\Delta_i^b(s)+2\eta>0. Under the stated projection and standard zero-initialized ADAM moments, the projected update appears to return to the same simplex vertex. It is therefore unclear how the continuous stage leaves the LPT initialization and produces the reported 86.1% improvement. Moreover, Eq. (21) applies only while the other blocks remain at vertices, so the actual NPP update procedure needs to be clarified.

Questions for authors
  1. Can the authors reconcile the Max-5-Cut results in Table 5 with the exhaustive one-vertex local-optimality check? In particular, could the authors report the total edge weight, final cut value, and best remaining one-vertex improvement for both variants and confirm that both underwent exactly the same correction and verification procedure?

  2. What exact operation allows the NPP projected-ADAM search to leave the LPT simplex vertex? Please clarify the ADAM initialization, block-update order, projection procedure, attractor coefficient, and whether any perturbation, soft initialization, or intermediate discretization is used. If multiple blocks become fractional, how is Eq. (21) used?

  3. In Table 4, the LEMON coloring result reports a 100% certificate rate and zero corrections while the final conflict value is 1.1±0.61.1\pm0.6. Does “Certificate” mean only one-flip local optimality rather than a proper-coloring certificate? If so, could these two notions be reported separately?

  4. What independent reference values support the statement that LEMON matches the reference optimum on 53/61 MIS instances? Table 8 does not provide an explicit optimum column, and its caption also states that LEMON beats pCQO-MIS in all cases, although some displayed rows contradict this statement. Could the authors clarify the source of the 53/61 count and correct the benchmark summary?

4 comments
AuthorsOpenReview ↗

Reply to Q1, W1, Q2 & W2 of Reviewer ZPFy

Thank you for carefully examining the local-optimality conditions and NPP initialization, and for identifying two points that required clarification and correction.


Q1: Max-5-Cut edge-weight bound and verification

We thank the reviewer for identifying this inconsistency. We reran the experiment on ER(100, 0.3) graphs over 100 paired runs, using the same 5 ms wall-clock budget per run.

ER(100, 0.3), Max-5-CutNo ADAMProjected ADAM
Mean total edge weights WW1475.31475.3
Mean final cut1181.121381.72
One-flip certification rate57%93%

Both variants use the same discrete correction procedure, but the fixed runtime budget does not guarantee convergence to a one-flip local optimum always. Thus, the bound C≥0.8WC\geq 0.8W applies to certified solutions, not necessarily to every time-limited output.

Under the same budget, projected ADAM achieves a 16.98% higher mean cut and increases the one-flip certification rate from 57% to 93%, demonstrating better solution quality and more frequent convergence to discrete local optima.

W1: Max-5-Cut ablation consistency

The original No-ADAM value of 895.82 resulted from sampling from the wrong ER graph. We corrected the graph-generation setting and reran both variants under identical 5 ms budgets.

The corrected result s are adressed in Q1. The respective one-flip certification rates are 57% and 93%, confirming that projected ADAM more frequently reaches locally optimal solutions within the same runtime budget.

We have clarified the fixed-budget protocol and corrected the corresponding results in the revised manuscript.


Q2 & W2: Exact NPP operations.

"At such a vertex ... the projected update appears to return to the same simplex vertex."

The reviewer is correct: projected ADAM initialized at a one-item locally optimal LPT vertex, with zero moments, cannot escape through the stated block updates. Our implementation addresses this through Gaussian-perturbed initialization and intermediate discretization, now clarified in Appendix D of the revised manuscript.

The procedure is as follows:

  1. Gaussian-perturbed initialization. Starting from the LPT assignment sLPTs^{\mathrm{LPT}}, we initialize qi=ΠΔ(esiLPT+zi)q_i=\Pi_{\Delta}(e_{s_i^{\mathrm{LPT}}}+z_i), where zi∼N(0,Ik)z_i\sim\mathcal N(0,I_k) independently. The perturbation can change the decoded labels: a competing label bb overtakes the LPT label aa whenever zi,b−zi,a>1z_{i,b}-z_{i,a}>1. Thus, multiple items can change assignments simultaneously, allowing the search to escape the one-item local optimum of LPT.

  2. Sequential block optimization. We process items in random order, keeping all inactive blocks at their decoded simplex vertices. For each active block, we compute the kk exact conditional endpoint energies and apply projected ADAM. The updated block is then decoded by arg⁡max⁡\arg\max and reset to the corresponding vertex. Consequently, Equation (21) is always evaluated with all other blocks at vertices, as required.

  3. Parameters and verification. We use learning rate 0.080.08, (β1,β2)=(0.9,0.999)(\beta_1,\beta_2)=(0.9,0.999), ϵ=10−8\epsilon=10^{-8}, zero-initialized moments, and Euclidean simplex projection. The attractor coefficient is η=0.25\eta=0.25 for 32-bit integer inputs and η=δ/2\eta=\delta/2, with δ\delta as the smallest decimal resolution of the input numbers. For example, {2.15,10.3,7.122.15,10.3,7.12} gives δ=0.01\delta=0.01 and η=δ/2=0.005\eta=\delta/2=0.005. These choices satisfy the sufficient slope condition 2η⩽δ2\eta\leqslant\delta. Final assignments are independently checked for feasibility and improving one-item moves.

NPP ablation. To separate the effects of perturbation and the attractor, we conducted a 10-seed ablation comparing unperturbed LPT, Gaussian-purturbed projected ADAM without the attractor (η=0\eta=0), and with the attractor (LEMON, η>0\eta>0). Representative results from Table 7 are shown below.

Distribution, kkLPT MSDADAM (η=0\eta=0)LEMON (η>0\eta>0)
N(0,1)\mathcal N(0,1), 106.32×10−56.32\times10^{-5}5.75×10−55.75\times10^{-5}8.03×10−68.03\times10^{-6}
U[0,1]\mathcal U[0,1], 57.01×10−67.01\times10^{-6}5.22×10−65.22\times10^{-6}2.96×10−62.96\times10^{-6}
U[32-bit]\mathcal U[32\text{-bit}], 109.47×1049.47\times10^47.95×1047.95\times10^44.21×1044.21\times10^4

We see that LEMON achieves the lowest mean MSD in all six settings, reducing MSD by 43.90% to 87.31% relative to LPT. The ablation separates two effects: Gaussian perturbation allows the search to leave the original LPT assignment, while the η=0\eta=0 versus η>0\eta>0 comparison demonstrates the attractor's additional benefit. One-item local optimality is independently verified after discrete correction, rather than assumed from projected ADAM convergence.

We have further explained these in Appendix D of the revised manuscript.

AuthorsOpenReview ↗

Reply to Q3, and Q4 of Reviewer ZPFy

Q3: Coloring certificate.

As clarified in Q3 of reviewer nhWp, the 100% (10/10) certification rate refers to one-flip local optimality, not proper coloring (zero conflicts), which was achieved in only 1/10 runs. We now report these outcomes separately in the revised manuscript (lines 1391–1392).


Q4: MIS reference values.

As clarified in Q3 of reviewer nhWp, the 53/61 count means LEMON matches or exceeds both pCQO-MIS and ReduMIS, not that it attains certified global optima. Against pCQO-MIS, LEMON performs better/equally/worse on 9/48/4 instances; against ReduMIS, the counts are 1/52/8. On p_hat1000-3, LEMON achieves 65, compared with 67 and 68, respectively, correcting the previously misstated deficits. We have revised the abstract and Table 10 caption accordingly.

Thank you for the detailed response and revisions. I appreciate that the authors acknowledged the original Max-5-Cut experimental error and clarified the Gaussian-perturbed initialization and blockwise discretization used for NPP. These revisions address important concerns in my original review. However, I still have two concerns about the experimental evidence.

  1. The revised Max-5-Cut experiment does not fully resolve the certification concern.

The authors now report one-flip certification rates of 57% and 93% for No ADAM and Projected ADAM, respectively. This clarifies why the local-optimality bound need not hold for every time-limited output. However, the original manuscript described exhaustive verification after discrete correction, whereas the revised experiment introduces a 5 ms budget under which some outputs remain uncertified. The distinction between certified solutions and time-limited outputs should be made explicit. I would also like to know whether the reported certification rates are measured after correction and whether verification time is included in the budget.

  1. The NPP results still do not fully isolate the contribution of projected ADAM.

The Gaussian perturbation explains how the algorithm can escape the LPT local optimum, and the revised block-update procedure addresses the condition required by Eq. (21). However, the new ablation compares unperturbed LPT with perturbed projected ADAM, with and without the attractor. It does not isolate the improvement caused by projected ADAM itself from that caused by perturbation and subsequent discrete correction. A comparison against Gaussian-perturbed LPT followed by the same discrete correction, without projected ADAM, would be important for supporting the claimed contribution of continuous optimization.

Overall, the revisions improve the clarity of the implementation and correct several issues in the original experiments. Nevertheless, I remain unconvinced that the current evidence fully supports the claimed benefits of the continuous search procedure. I therefore maintain my Weak Rejection recommendation.

We appreciate the reviewer's positive acknowledgment of the revisions and the quick follow-up.


1. The exhaustive verification described in the original manuscript applies to our main benchmark experiments. The Max-5-Cut ablation instead uses a fixed 5 ms budget for optimization and a discrete correction to fairly compare No ADAM and Projected ADAM. The reported certification rates (57% and 93%) are measured after correction, using one-flip verification performed outside the 5 ms budget. Thus, all outputs are checked, but only those passing the one-flip check are certified; the remaining outputs are time-limited solutions without a local-optimality guarantee. We have now mentioned the verification procedure in the revised manuscript.


2. We agree that the earlier ablation did not fully isolate the contribution of projected ADAM. To address this, we added the suggested baseline: Gaussian-perturbed LPT followed by discrete correction, without ADAM. We repeated the comparison over the same 10 seeds, using identical perturbation and correction procedures. This allows us to separate the effects of perturbation, continuous optimization, and the attractor.

Dist., kkLPT MSDLPT + PertLPT + Pert + CorrADAM (η=0\eta=0)LEMON (η>0\eta>0)Gain vs. LPTGain vs. Corr
∣N(0,1)∣\mathcal \lvert N(0,1)\rvert, 51.74×10−51.74\times10^{-5}1.92×10−51.92\times10^{-5}1.70×10−51.70\times10^{-5}1.48×10−51.48\times10^{-5}7.13×10−67.13\times10^{-6}59.13%58.06%
∣N(0,1)∣\mathcal \lvert N(0,1)\rvert, 106.32×10−56.32\times10^{-5}7.34×10−57.34\times10^{-5}6.55×10−56.55\times10^{-5}5.75×10−55.75\times10^{-5}8.03×10−68.03\times10^{-6}87.31%87.74%
U[0,1]\mathcal U[0,1], 57.01×10−67.01\times10^{-6}7.71×10−67.71\times10^{-6}7.14×10−67.14\times10^{-6}5.22×10−65.22\times10^{-6}2.96×10−62.96\times10^{-6}57.79%58.54%
U[0,1]\mathcal U[0,1], 101.43×10−51.43\times10^{-5}1.67×10−51.67\times10^{-5}1.40×10−51.40\times10^{-5}1.19×10−51.19\times10^{-5}4.01×10−64.01\times10^{-6}71.90%71.36%
U[32-bit]\mathcal U[32\text{-bit}], 52.19×1042.19\times10^42.43×1042.43\times10^42.15×1042.15\times10^41.75×1041.75\times10^41.23×1041.23\times10^443.90%42.79%
U[32-bit]\mathcal U[32\text{-bit}], 109.47×1049.47\times10^41.10×1051.10\times10^59.80×1049.80\times10^47.95×1047.95\times10^44.21×1044.21\times10^455.52%57.04%

LPT + Pert denotes Gaussian perturbation followed by decoding, while LPT + Pert + Corr additionally applies discrete correction without ADAM. The gain columns report LEMON's relative MSD reduction against LPT and perturbation-plus-correction, respectively. All MSD values are averaged across the 10 seeds (lower values are better).

The results directly address the reviewer's concern:

  • Perturbation and correction alone: The resulting MSD remains close to the original LPT solution across all six settings; indicating that one-flip correction alone largely returns to comparable local optima.

  • Contribution of projected ADAM: Even without the attractor (η=0\eta=0), projected ADAM reduces mean MSD by 12.2% to 26.9% relative to perturbation-plus-correction across all six settings.

  • Additional contribution of the attractor: Adding the attractor further reduces MSD relative to ADAM (η=0\eta=0). Overall, LEMON achieves 42.79% to 87.74% lower MSD than perturbation-plus-correction.

Thus, the controlled comparisons demonstrate that projected ADAM improves solution quality beyond Gaussian perturbation and discrete correction, while the attractor provides an additional benefit.

We have included these comparisons, clarified the experimental procedure, and updated Table 7 in the revised manuscript.

Reviewer_nhWpOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

LEMON proposes a continuous relaxation for finite-state combinatorial optimization using a product of probability simplices and a strictly block-concave attractor. Its main contribution is a characterization of when the continuous local minima coincide exactly with discrete one-variable local optima, including a sharp threshold on the attractor slope. The framework preserves the original multi-state neighborhood without relying on binary encodings. A solver combines projected Adam with decoding, discrete correction, and verification. Experiments cover maximum independent set, graph coloring, Max-k-Cut, and multi-way number partitioning.

Critical strengths
  1. A clear theoretical statement. The framework accommodates heterogeneous state spaces and higher-order interactions while preserving the original one-variable neighborhood. The sharp slope characterization strengthens the sufficient-condition result and clarifies when the relaxation introduces additional local minima. These theoretical results support the solution framework with observation on combinatorial structure.
  2. Broad empirical instances with promising reported performance. The experiments span four problem classes. In particular, the paper reports reaching the known chromatic number on 27/30 applicable coloring instances and matching public-best values on 26/144 Max-k-Cut settings. These results suggest practical potential beyond a single problem-specific formulation.
Critical weaknesses
  1. There are some well-known baselines omitted. The Max-k-Cut experiments omit ROS [1], a closely related probability-simplex approach, while the binary Max-Cut evaluation does not include MCPG [2], a recent method combining policy-gradient optimization, MCMC sampling, and local search. The graph-coloring evaluation would also benefit from comparisons with ANYCSP [3] and the decision-diagram solver of van Hoeve [4]. These omissions limit the assessment of LEMON’s competitiveness against relevant learning-based and mathematical-programming approaches. Comparisons on shared instances under matched computational budgets, reporting both solution quality and runtime, would strengthen the empirical conclusions.
  2. The practical contribution of the landscape-preserving attractor is not sufficiently isolated. Figure 4 verifies the theoretical threshold on small enumerated instances, Table 4 compares different representations, and Table 5 removes the entire continuous optimization stage. These experiments do not establish whether the proposed attractor improves practical solution quality over the same simplex relaxation without it. A controlled comparison with identical initialization, optimization, and correction procedures, under matched computational budgets, is needed to connect the theoretical contribution to the reported solver performance.

[1] Yeqing Qiu, Ye Xue, Akang Wang, Yiheng Wang, Qingjiang Shi, and Zhi-Quan Luo. “ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-k-Cut Problems.” ICML, PMLR 267:50721–50743, 2025. [2] Cheng Chen, Ruitao Chen, Tianyou Li, Ruicheng Ao, and Zaiwen Wen. “A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization.” Mathematical Programming, 2025. [3] Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. “One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction.” IJCAI, pp. 4280–4288, 2023. [4] Willem-Jan van Hoeve. “Graph coloring with decision diagrams.” Mathematical Programming, 192:631–674, 2022.

Questions for authors
  1. Does the attractor improve performance over the same projected-Adam solver with η=0\eta=0? Under matched total wall-clock budgets and paired random seeds, please report decoded solution quality and certification rates before correction, final solution quality, and correction time.
  2. How is the vertex condition required by Equation (21) maintained during NPP block-coordinate search? Simplex projection alone does not guarantee that an updated block returns to a vertex. Please specify the block-update and discretization procedure, as well as the attractor coefficient used for the non-integer NPP instances and whether it satisfies the stated slope condition.
  3. What exactly does “certification” mean in Table 4? The coloring results report 100% certification despite a nonzero conflict energy of 1.1±0.61.1\pm0.6. Does this refer only to one-flip local optimality? Please distinguish this from proper-coloring success. Please also reconcile the Table 8 caption with the results on p_hat1000-3: LEMON obtains 65, compared with 67 for pCQO-MIS and 68 for ReduMIS, contradicting both the claimed universal superiority over pCQO-MIS and the stated one-unit deficit to ReduMIS.
4 comments
AuthorsOpenReview ↗

Reply to W1, W2, Q1, and Q2 of Reviewer nhWp

We appreciate your positive assessment of our theoretical and empirical results.

W1: Missing baselines.

We have added comparisons with MCPG, decision diagrams (DD), ROS, and ANYCSP in Tables 1 and 9, reporting both favorable and unfavorable results. The results were reproduced using the publicly available implementations of these methods.

For Max-Cut, LEMON surpasses MCPG on G15 and G50, matches it on G49, and trails on G14 and G55.

For Max-3-Cut, it outperforms ROS on G22, G48, G49, G50, while trailing on G55 (11730 vs. 12033) and G70 (9968 vs. 9989).

For graph coloring, LEMON beats ANYCSP and matches the chromatic number on all five instances, while matching DD's exact bounds on miles750 and school1 in shortest time.

These results acknowledge the strengths of specialized methods while demonstrating LEMON's competitiveness across different problems.


W2: Does the attractor improve practical performance?

We thank the reviewer for suggesting this useful ablation. We compared the same projected-ADAM solver without (η=0\eta=0) and with (η=0.25\eta=0.25) the attractor over 100 paired seeds, keeping initialization, optimization steps, decoding, and correction identical. Each entry reports results without / with the attractor, respectively.

TaskDecoded valueDecoded certificateFinal valueCorrection time (ms)Total runtime (s)
C125.9 MIS ↑29.40 / 31.9025% / 71%32.40 / 33.702.6 / 1.10.765 / 0.755
ER(100, 0.03) MIS ↑43.50 / 47.8030% / 76%47.00 / 49.700.7 / 0.30.650 / 0.640
le450_5a coloring conflicts ↓115.27 / 13.5713% / 57%2.80 / 0.7036.8 / 35.00.3335 / 0.3327
ER(100, 0.3) coloring conflicts ↓22.33 / 3.7033% / 79%3.10 / 0.025.23 / 4.910.1897 / 0.1774
G14 Max-3-Cut ↑3122.93 / 3566.9747% / 82%3825.33 / 3933.901.10 / 0.510.0361 / 0.0288
ER(100, 0.1) Max-3-Cut ↑361.87 / 419.8361% / 91%435.87 / 459.800.12 / 0.11 0.0032 / 0.0031

Key observations:

  • The attractor improves both decoded and final objective values across all six settings.
  • One-flip local-optimality certification of decoded solutions improves consistently, from 25% to 71% on C125.9 and 47% to 82% on G14, for example. (certification refers to one-flip local optimality, not global optimality or proper coloring.)
  • Correction and total runtimes decrease in all six settings, indicating that the attractor brings decoded solutions closer to discrete local optima.

The results are included in Tables 6 and 7 of the revised manuscript.

For the complementary NPP ablation, please see our response to W2 of reviewer ZPFy.


Q1: Effect of attractor ablation.

As shown in W2, adding the attractor to projected ADAM consistently improves decoded and final objective values, increases pre-correction one-flip certification rates, and reduces correction time across all six settings. The ablation uses 100 paired seeds with identical optimization procedures and reports total wall-clock runtimes.


Q2: NPP Block Updates, Vertex Condition, and Attractor Coefficient.

"...simplex projection alone does not guarantee that an updated block returns to a vertex."

We agree. Projection alone does not produce a simplex vertex; explicit discretization is applied after optimization. Gaussian perturbation allows the decoded initialization to move away from the locally optimal LPT assignment. We then optimize blocks sequentially in random order, keeping all inactive blocks fixed at their decoded simplex vertices. After updating each active block using projected ADAM, we decode it by arg⁡max⁡\arg\max and reset it to the corresponding vertex. Thus, all other blocks remain at vertices when Equation (21) is evaluated, as required.

"...the attractor coefficient used for the non-integer NPP instances and whether it satisfies the stated slope condition."

For non-integer NPP, we choose δ\delta as the smallest decimal resolution of the input numbers. For example, {2.15,10.3,7.122.15,10.3,7.12} gives δ=0.01\delta=0.01 and η=δ/2=0.005\eta=\delta/2=0.005. Each input is an integer multiple of δ\delta, so any objective formed from integer linear combinations of these inputs also takes values in δZ\delta\mathbb{Z}. Also, every nonzero difference between objective values is ⩾δ\geqslant \delta. Hence, 2η=δ2\eta=\delta satisfies the sufficient slope condition at equality (Corollary A.6), provided the objective and any additional penalties preserve this lattice structure.

We have further explained initialization, block updates, attractor coefficients, and verification in response to W2 of ZPFy, and added the complete explaination in Appendix D of the revised manuscript.

AuthorsOpenReview ↗

Reply to Q3 of Reviewer nhWp

Q3: Certification and MIS caption.

Clarification of certification: The 100% certification rate refers to one-flip local optimality, not proper coloring: no single-vertex recoloring improves the objective, even if conflicts remain. Thus, zero corrections do not imply zero conflicts, as reflected by the remaining 1.1±0.61.1\pm0.6 conflicts. We now report one-flip certification (10/10) and proper coloring (1/10) separately (revised manuscript, lines 1391–1392).

Correction of benchmark claims: The 53/61 figure means that LEMON matches or exceeds the reported values of both pCQO-MIS and ReduMIS, not that it achieves 53 certified global optima. The better/equal/worse counts are 9/48/4 against pCQO-MIS and 1/52/8 against ReduMIS. On p_hat1000-3, LEMON achieves 65, compared with 67 and 68, respectively (deficits of 2 and 3). The other seven deficits against ReduMIS are each one unit. We have corrected the abstract and Table 10 caption accordingly in the revised manuscript.

I thank the authors for their responses and the revised manuscript. My concerns have been addressed, and I will update my score.

Thank you for your positive feedback and acknowledging our revisions.

Reviewer_ysLbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper explores combinatorial optimization through the perspective of continuous relaxations, which enables fast and parallelizable gradient-based methods to be used on non-differentiable optimization problems. They also propose a theory around how the discovered solutions can be mapped to feasible discrete solutions.

Critical strengths
  1. The problem of deriving continuous relaxations for combinatorial optimization problems such that a solution in the former corresponds to a feasible solution in the latter is a difficult problem and this paper uses an innovative approach around energy landscapes to establish such a guarantee.
  2. The empirical results are promising, with the proposed approach even outperforming state-of-the-art classical heuristics such as ReduMIS. Such heuristics are very difficult to beat even though they have been around for a long time
Critical weaknesses
  1. This paper compares against pCQO-MIS, which also uses continuous relaxations and seems to have a theorem for mapping continuous solutions to feasible discrete solutions in the original MIS problem. That raises the question of what the additional theory in this paper accomplishes that is not already there in the pCQO-MIS paper.
Questions for authors

As mentioned in the weaknesses, what does the proposed theory accomplish over similar theory derived in the pCQO-MIS paper?

1 comment
AuthorsOpenReview ↗

Reply to Reviewer ysLb

Thank you for recognizing the theoretical contributions and the strong empirical results.

W1: Novelty relative to pCQO-MIS.

We agree that pCQO-MIS (Alkhouri et al., 2025) provides important local-minimum guarantees for binary MIS using a graph-specific quadratic penalty. LEMON differs in both generality and theoretical guarantees.

First, LEMON accommodates arbitrary finite-state variables, heterogeneous state spaces, and higher-order interactions while preserving the native categorical one-variable neighborhood. This enables a unified treatment of MIS, Max-kk-Cut, graph coloring, and kk-way number partitioning, beyond the scope of pCQO-MIS.

Second, our theory establishes two stronger results:

  • Exact landscape equivalence: Continuous local minima correspond exactly to discrete one-variable local minima, in both directions.
  • Sharp attractor characterization: We establish necessary and sufficient conditions for a broad class of admissible attractors, including equality at the sharp slope threshold (Figure 4 of the revised manuscript).

The main contribution is therefore a general multi-state framework with exact landscape guarantees and sharp conditions on the attractor, rather than a binary MIS-specific formulation. We have clarified these distinctions and acknowledged pCQO-MIS in the revised introduction.

Q1: What does LEMON add beyond pCQO-MIS?

On the theoretical side, pCQO-MIS provides local-optimality guarantees for MIS, whereas LEMON establishes necessary and sufficient conditions for landscape equivalence across general finite-state problems, including Max-kk-Cut, graph coloring, and kk-way NPP, without problem-specific relaxations. On the empirical side, LEMON matches or outperforms pCQO-MIS on 57 of the 61 common MIS instances, achieving better solutions on 9, equal solutions on 48, and worse solutions on only 4.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revisions

In response to the reviewers' comments, we have strengthened the manuscript by clarifying the theoretical contributions, adding new baselines and ablations, and addressing the identified experimental and implementation issues. The key changes (highlighted in blue in the revised manuscript) are summarized below.

  1. Novelty relative to pCQO-MIS: Clarified LEMON's broader scope beyond MIS, covering heterogeneous multi-state variables and higher-order interactions (extending to Max-kk-Cut, graph coloring, and multi-way number partitioning), and its stronger theoretical guarantees of exact landscape equivalence and sharp necessary-and-sufficient attractor conditions.

  2. Additional comparisons and ablations: Added comparisons with MCPG, ROS, ANYCSP, and decision diagrams, reporting both favorable and unfavorable results. Conducted attractor ablations showing improvements in solution quality across graph problems and NPP, as well as one-flip certification rates and correction time on graph problems.

  3. NPP implementation: Clarified Gaussian-perturbed LPT initialization, sequential projected-ADAM updates, intermediate discretization to satisfy the vertex condition in Eq. (21), and the choice of η\eta satisfying 2η⩽δ2\eta \leqslant \delta.

  4. Corrections and consistency checks: Corrected the Max-5-Cut graph-generation error and reran the experiments. Clarified one-flip optimality certificate versus proper graph coloring, corrected MIS and coloring benchmark claims and deficits. We also rechecked the remaining experimental results and claims for consistency.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.