COExpander: Adaptive Solution Expansion for Combinatorial Optimization

Dear Reviewer F5eW,

We are more than grateful for your time and recognition of our contributions. We sincerely present our point-to-point clarification to your questions below.

Q0-Comparing with UDC.

A0: First, we have cited the UDC method and explained our exclusion of further comparison in Sec.1 (line 25-26, right). Second, we provide a brief performance comparison below, showing that COExpander generally outperform UDC (reported in original paper with the best settings) in terms of both optimality gap and per-instance efficiency.

Q1-Sensitivity to specific strategies for determining operations.

A1: In fact, to mitigate the overreliance on ad-hoc designs, the decisive operators in our work are based on the simplest greedy heuristics. Take MIS for instance, as detailed in Sec. 4.2.2, we sort the predicted heatmap in descending order and sequentially (greedily) attempt to add nodes to the independent set. Once the "independence" constraint is breached, the process halts and the next round of model inference commences. Thus, the version we propose can essentially be regarded as a baseline strategy, while future efforts on more complex determining operations are encouraged and may necessitate ablations against ours. We will also explicitly address this point in the paper to prevent misunderstandings. Thanks for your question!

Q2-Sensitivity to the mask probability in Eq(5).

A2: Please refer to our response A2 to Reviewer UKMH, where the effects of $\alpha$ is systematically evaluated though supplementary experiments.

Q3-Disclosure of the code implementation.

A3: Sure. Rest assured that the code and datasets of this work will be fully open-sourced as soon as the conference permits. At the moment, due to the regulation that "links may only be used for figures (including tables) and captions that describe the figure (no additional text)", we are more than willing to provide our code via anonymous links once we have your confirmation that it does not violate any of the rules.

Q4-Explanation of model input containing optimal solution $x^{*}$.

A4: Recall the process of diffusion mechanism, in the training stage, $x^*$ serves as the starting point to generate the noising trajectory, i.e., $x_{0:T}=x_0,x_1,\cdots,x_T$ where $x_0=x^*$, and the noised representation $x_T$ is fed to the model to learn the denoising mapping. At inference, the noised vector $x_T$ is generated by random Gaussian noise without ground truth label. We note the description in Line 273 slightly inaccurate and have updated it accordingly to mark the difference of model input for training and testing phases. Thank you for the critical point!

Q5-Acquisition of $M$ in the testing phase.

A5: First of all, we'd clarify that the mask $M$ is a Boolean matrix with the same shape as the solution $x$. Its purpose is straightforward: to mark whether an edge or node has been determined (assigned 0 or 1). Hence, $M$ is initialized as a zero matrix (vector) at the beginning of tests, and there is no requirement for the optimal solution $x^*$. We've updated our scripts in Algorithm 1 to explicitly show the initial setting of the mask.

Q6-Request for a simple and clear description of the method.

A6: In this paper, we put forward a novel paradigm for the neural decisive process, aiming to harness the strengths of both global prediction and local construction methods. Briefly, the process of determining the solution for a problem instance is adaptively divided into multiple rounds. During each round, the model generates a heatmap that forecasts the probability of each node/edge being chosen. Subsequently, the solution is greedily constructed in descending order of the heatmap values until the constraints are breached. All the selected nodes/edges are then marked as 1 and, together with the partial solution, fed back into the model to initiate a new round of inference. This cycle continues, with more nodes or edges being determined in each successive round, until every decision variable has been taken into account and assigned a value of either 0 or 1 in the final solution. The modek is trained with randomly generated intermediate states (e.g. 10 out of 50 nodes have been decided in MIS) to learn better predictions for the solving stage.

---

We hope our explanations adequately address your concerns. We are more than willing to provide further clarifications if any question remains, while we'd be rather grateful if, through your valuable reconsideration, our technical contributions merit an improved assessment overall.

Best regards,

The Authors

Dear Reviewer CvKY,

We appreciate your time reviewing and acknowledging the novelty and empirical efforts of our work. There appear to be several misunderstandings, chiefly concerning the claim about the "reimplementation" of baseline solvers and existing neural methods. We offer point-by-point clarifications below.

---

Q1-About paper length.

A1: Thank you for your concern. Admittedly, our paper has a relatively long appendix. However, we'd like to explain that: First, each part of the appendix provides supplementary support for the core idea. It includes additional related work for a broader discussion of existing NCO efforts (A), detailes of the 3 paradigms in our proposed taxonomy (B), formal problem definitions (C), introduction of our re-standardized data and re-wrapped tools (D&E), implementation details for reproduction (F), and supplementary results and analysis (G). Second, as far as we know, many works [1,2,3, etc.] have comprehensive content without their contributions being devalued by top conferences, and we've double-checked to ensure no violation of the submission rules. Thus, we believe our paper contains the necessary context to present a complete picture of our proposal, with both narrative and procedural justifications, comparable to precedents of the same tier and area.

---

Q2-Doubts on the claim of reimplementation.

A2: Thank you for posing this significant question. Firstly, we sincerely apologize for any misunderstanding. In fact, we are not "re-implementing" the renowned solvers, rather, our work center on enhancing the usability of invoking them through more unified and efficient APIs for future research. This process is more aptly described as re-"wrapping"/"encapsulating" at the engineering level, without duplicating the underlying algorithms. Hence, the issue of “faithfulness” to the original implementations does not pertain here. Below we provide a sample code how the solvers are accessed within our framework:

solver = MISGurobiSolver()
solver.from_txt("path/to/data")
solver.solve()
>>> (obj: xx, gt_obj: xx, gap: xx, std: xx)

We believe our efforts enables an easy and consistent use of these solvers for future research.

Regarding the improvement of LKH, as elucidated in Appendix D.2, it involves an in-depth exploration of the complex built-in settings of the LKH package. We found that the LKH3 package utilizes a parameter named SPECIAL, which by default disables the use of 2-/3-opt operators, thus compromising the solving quality on TSP. So, we empirically removed it for enhancing both performance and efficiency, and leave it an open question prompting further investigation into its internal mechanisms.

In summary, we regret any confusion caused and hope our clarifications accurately convey the nature of this part in our work—aiming for improved convenience and potential performance gains from an engineering perspective. We'd like to reiterate our primary technical contribution: the proposal of a novel neural paradigm and framework for COPs, supported by comprehensive experiments.

---

Q3-Doubts on retraining of existing neural solvers.

A3: Thanks for your comments. Firstly, in the field of NCO research, it is a common and encouraged practice to retrain and re-evaluate existing methods, which facilitates a fairer comparison, as directly using results from previous works can lead to discrepancies of hardware, datasets, and testing pipelines. Retraining demands significant effort. Regarding the data, our benchmark datasets have covered the vast majority of publicly available datasets, such as TSP(Uniform), MIS(RB-SMALL) and MIS(ER-700-800). In cases where consistent data is currently lacking, like for ATSP, MCl, MVC, MCut, etc., we synthesize new instances following the same generating algorithm as previous works. Our intention is to help establish standardized benchmarks for these problems, similar to the well-established TSP benchmark. It's worth noting that the results obtained from our retrained neural approaches generally match or even surpass those reported in the original papers (see the table below). Rest assured that we shall release the code and data as soon as the conference permits via anonymous links, in any case.

---

References

[1] UDC, NeurIPS 2024 (45 pages)

[2] UniCO, ICLR 2025 (41 pages)

[3] UCOM2, ICML 2024 (34 pages)

---

We hope our clarifications adequately address your concerns. We'd be rather grateful if, through your meticulous reconsideration, stronger consensus could be reached on a more favorable assessment of our work. We remain positive to further discussions!

Best regards,

The Authors

Dear Reviewer UKMH,

Thanks for your recognition and valuable questions.

Q1: Interpretation of "adaptive"

A1: In our work, "adaptive" means exactly the fact that the number of ascertained decision variables within one round of determination is not fixed. Specifically, it is achieved via the autonomy of the determiantion operator (see Sec.4.2), where one determination round usually ends when the greedy operator yields invalid variable assignments, so the number of decisions per round is random. Note that $D_s$, which caused your confusion, is just a maximum limit for the rounds. E.g., $D_s=3$ for a task with 10 variables ensures the problem gets solved within 3 rounds, but no prior is imposed on how the quantity of decisions is distributed across those rounds (possibly [2,3,5] or [4,3,3]). For the term "self-", we have unified our wording to "adaptive" to describe such flexibility to avoid abuse of concepts.

Q2: Choice of $\alpha=0.9$ in Eq.5.

A2: First, the model convergence and solving quality are not sensitive to $\alpha$. Second, $\alpha=0.9$ is preferred to ensure the model to be sufficiently (Pr=0.9) trained on cases to solve from scratch, while balancing the training diversity for solving from arbitrary intermediate states (Pr=0.1). Empirical results and detailed analysis are illustrated in the table and figures in alpha_ablation.png.

Q3: Sinusoidal embedding layer

A3: Generally, we follow previous works (GCN4TSP,DIFUSCO,T2T,etc) to employ the sinusoidal embedding. It functions in a way similar to how position encoding works for Transformers. (Exactly as you speculated, it assigns numerical identifiers to nodes and edges for GCN.) Specifically, for node-tasks (e.g. MIS), the input graph contains only edge index ($E\in R^{|\mathcal{E}|}$), yet the (noised) solution vector pertains to nodes, i.e. $y_t\in [0,1]^{|\mathcal{V}|}$. Parallelly, for edge-tasks (e.g. TSP), only node coordinates ($V\in R^{|\mathcal{V}|\times2}$) are provided, while the solution are on the edges, i.e. $y_t\in [0,1]^{|\mathcal{E}|}$. Hence, the design rationale is to make up for the lacking part of each task type, i.e. dual initial embeddings for both nodes and edges to feed GCN in either case. Formally, $h_v=S(V),h_e=S(y_t)$ for edge-tasks; $h_v=S(y_t),h_e=S(E)$ for node-tasks. We hope this explanation resolves your confusion, and we'll update our paper with clearer notations.

Q4: $I_s$-performance drop in Fig.3

A4: Unlike the multi-sampling or repeated random re-solving tricks, in our case, each inference step marks distinct time points in the denoising process, and the solution vector being denoised is utilized iteratively throughout the entire process. So, a larger $I_s$ merely implies a finer-grained denoising schedule towards the final solution ($\hat{x_0}$). Intuitively, Fig.3 showns an upward-trended solving quality as $I_s$ grows, however, there is no hard guarantee of performance gain with greater $I_s$, esp. when $I_s$ is small (e.g. 1-5), since the inferences are sequentially linked rather than parallelly independent for "best-picking".

Q5: Applicability to VRP

A5: Please refer to A3 to Reviewer zhdB, due to the space limits.

Q6: Claim of "the first good global predictor for ATSP".

A6: It appears to be a minor misunderstanding. GLOP is indeed a good work, though, as stated in Sec.6.2 of their paper, "we apply MatNet50 checkpoint as our reviser without retraining", implying that MatNet (NIPS21), a solver of the local construction (LC) type, was used as the backbone. Thus, it doesn't contradict our claim to be the first global predictor (GP) with good performance on ATSP. In any case, we've revised our paper with more careful wordings.

Q7: Code release

A7: The regulations seem to emphasize that only figures are allowed in anonymous links during rebuttal. So we are more than willing to provide our code yet awaiting your confirmation that it does not violate any of the rules.

Q8: Discussion of iSCO.

A8: We've noticed recent sampling methods like iSCO and RLSA(arXiv:2502.00277) and added them in our discussion of related work. Actually, they can be orthogonally performed on top of COExpander as a strong post-processor, where neural models serve to quickly yield high-quality initial solutions in aid of the infeasibility issue that sampling methods often encounter. Supplementary experiments on MIS (shown in the rlsa.png) validate the synergy of COExpander+RLSA.

---

Hopefully our responses alleviate your concerns with satisfaction, and we stay open for any further interactions!

Best regards,

The Authors

Dear reviewer zhdB,

We appreciate your meticulous review and constructive advice. Below we respond to the 3 major points mentioned in your comments.

Q1: Comparison with Lwd.

A1: Firstly, it was our oversight not to compare LwD initially. Indeed, LwD is a highly relevant counterpart within the AE paradigm employing the RL learning strategy, and it merits a more in-depth discussion in our paper for its gradual "determination" of decision variables. However, it’s important to note that while LwD focuses predominantly on problems that are "locally decomposable" through RL-based policy learning, our COExpander represents a significant extension. It is designed to handle a broader spectrum of tasks, spanning node-selection tasks like MIS (isolated constraints), edge-selection tasks such as TSP (simple global constraints), and even more complex CVRP (detailed in Q3). This enhanced capability is underpinned by the utilization of more advanced backbone model architectures, specifically diffusion and consistency models, in combination with SL learning. We list the results comparing LwD and COExpander in ae_solvers.png.

To summarise, we are more than delighted to have incorporated your recommended work into our discussion and experimental comparisons. Our collective efforts, we believe, will contribute to a more systematic establishment of the AE paradigm in the context of NCO problem-solving.

Q2: Suggestions on additional related works (LCP & GFACS).

A2: Thanks for your suggestion. We have carefully studied the works you provided and agree that LCP introduces a reviser mechanism for refining partial solutions and GFACS provides valuable insights into advanced sampling techniques for LC solvers, which are both significant approaches in the NCO community. Therefore, we have followed your advice to cite them in our related work to enhance the paper’s connection to the broader NCO research landscape.

Q3: Applicability to more complex problems like CVRP.

A3: Firstly, COExpander can be directly applied to CVRP, as presented in cvrp.png, which is the first attempt to demonstrate applicability of heatmap-based methods on VRPs, to our knowledge. To admit, there is limitation of SL methods to tackle complex constraints. Inspired by LwD, we have theoretically conceived to extend the AE paradigm to solve complex problems like VRPs via PPO.

(i) Overview. AE paradigm is an iterative process and satisfies the Markov property, thus can be modeled as MDP. We plan to use PPO for model training, in order to better adapt to the relationship between actions and constraints. Note that a feasible scheme is theoretically described as follows, while the implementation and empirical results have obviously exceeded the scope of this paper, hence reasonably remitted to future researches.

(ii) Modeling. state $s_t:=(x_t,M_t)$; action $a_t:=(m_t,z_t)$ (selection and assignment); transition $P(s_{t+1}|s_t,a_t)$ devided to $x_{t+1}^{i} = \begin{cases}z_t^i&\text{if }m_t^i=1 \\\ x_t^i&\text{else }\end{cases}$ and $M_{t+1}=M_t\lor m_t$; reward is only defined in the final step $R(s_t,a_t) := \begin{cases} -c(G, x_t) & \text{if } t=k-1,\\\ 0 & \text{else} \end{cases}$

(iii) Training Model with PPO. Given the model $f(\cdot, \cdot)$, $\pi_\theta^t := \pi_\theta(a_t|s_t, G) = f(G, s_t)$. $z_t$ of $a_t$ is sampled from $\pi_\theta^t$ via Bernoulli sampling and then set the determined variables as 0. The advantage function: $\hat{A}\_t= -\gamma^{k-1-t} \cdot c(G,x_{k-1})-\mathbb{E}\_\theta [ -c(G,x_{k-1} | s_t)]$.

(iv) The Selection Part of Action. The selection part $m$ of $a$ is the core of controlling constraint satisfaction. Take CVRP as an example.

• Reshape $m$, $z$, and $M$ to $n\times n$, where $n$ is the number of nodes including the depot. $z$ needs to undergo an OR operation with its transpose.
• Make pre-assignment: $\hat{x}\_{i,j}=\begin{cases}z_{i,j}&\text{if }M_{i,j}=0, \\\ x_{i,j}&\text{if }M_{i,j}=1\end{cases}$.
• Check Constraints: $C_i=\begin{cases}1&\text{if }\sum_{j=1}^{n}\hat{x}\_{i, j}>2\text{ or }\sum_{j=1}^{n}p_{i,j}\cdot d_j>1 \\\ C_i&\text{else}\end{cases}$
• Re-Assignment. $\hat{z}\_{i,j}=\begin{cases}1&\text{if }C_i=1,\\\ z_{i,j}& \text{else}\end{cases}$; $\hat{x}\_{i,j} = \begin{cases}\hat{z}\_{i,j}&\text{if }M_{i,j}=0,\\\ x_{i,j}&\text{else}\end{cases}$.
• Selection Part. $m_{i,j}=\begin{cases}1&\text{if }\hat{z}\_{i,j}=1\text{ or } \sum_{j=1}^{n}\hat{x}\_{i,j}=2,\\\ 0&\text{else}\end{cases}$

---

We hope our point-by-point clarificaitons, supplementary experiments, and positive feedbacks on your requests, have satisfactorily addressed your concerns. We remain fully committed to involving further discussions with you towards an elevated evaluation of our work.

Best regards,

The Authors