- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes PgTS, a preference-guided tree search framework for generating high-quality feasible solutions to integer linear programs (ILPs). A depth-first tree search with backtracking is guided by two learned components, reference values and a variable ordering, which are trained jointly through objective-based preference learning. PgTS directly generates feasible solutions with a 100% feasible ratio on the three evaluated benchmarks, outperforming prior learning-based methods.
Critical strengths
The approach circumvents the need for optimal solutions as training labels, a requirement that limits the practicality of learning-based methods for ILP. Instead, PgTS obtains its learning signal by comparing the objective values of feasible solutions returned by the tree search. The trained model generalizes without retraining to instances with up to eight times as many variables as the training instances.
Critical weaknesses
-
The novelty claim needs to be reorganized, because discussion of the differences from closely related prior work is either missing or insufficient. First, although PgTS is built on preference learning, the paper cites no prior work on preference learning, including its applications to combinatorial optimization (CO). Without such a literature review and comparison, the claim that objective-based preference learning is a contribution is not adequately supported. In particular, the authors should clarify the differences from BOPO [1], which applies preference learning to CO: the preference loss in this paper (Eq. 2) closely resembles Eq. 4 of BOPO. Second, RL-SPH [2], mentioned in the introduction, is closely related to PgTS in that it also iteratively searches for feasible solutions, yet the differences between the two are not compared. The introduction also groups RL-SPH with methods that rely on external post search for feasibility, but RL-SPH generates feasible solutions without an external solver. Given that RL-SPH is presented as addressing the feasibility gap that earlier learning-based methods struggle with, the paper needs to state more clearly which challenge PgTS tackles.
-
The scope in which feasibility is actually guaranteed and tested is narrower than the scope of several claims. Proposition 1 is stated for binary ILPs only, whereas Eq. 1 is stated for general integer variables without bounds, and the abstract, introduction, and conclusion never restrict the claims to binary ILPs. Section 3 argues that bounded integer variables can be binarized, but the paper does not discuss how this transformation affects PgTS in practice. After binarization, the search would operate over the resulting binary variables, but it is unclear how this expanded representation affects search efficiency, learned variable ordering, or solution quality for general bounded-integer ILPs. Moreover, as Figure 2 (left) shows, once is assigned, the lower-bound check passes, yet both remaining choices for are infeasible, so the subtree contains no feasible solution. This illustrates that the pruning test may fail to identify an infeasible subtree early. In instances with equality or mixed-sign constraints, such tests may be less effective, potentially leaving large infeasible subtrees and increasing the practical risk of exponential worst-case behavior. PgTS was not evaluated on such instances in the main experiments: in CA, IS, and SC, all constraints are inequalities whose coefficients within each constraint share the same sign. Therefore, without clarifying the above and adding experiments on instances with integer variables and with equality or mixed-sign constraints, the current version of the method lacks the generality that its claims suggest.
[1] BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization, ICML, 2025.
[2] RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs, ICML, 2026.
Questions for authors
-
Eq. 1 defines a minimization problem, and Section 3 assumes that the objective satisfies for all feasible . How is this assumption satisfied for CA and IS, which are originally maximization problems? Please specify the exact objective transformations used for CA and IS. Since Eq. 2 depends on the ratio of objective values, is the preference loss invariant to the transformations used in the paper? How do the chosen transformations affect training and the reported results?
-
Could you specify the exact start and end points used to measure running time (Time) in Table 1, and whether the time refers to one guidance pair or all five?
-
Does the primal integral (PI) include the execution time of the trained model and the tree search of PgTS?
-
From my reading of Line 895, PgTS was trained on instances generated on the fly, whereas the baselines were trained on the fixed training dataset. Why do the training sets differ between PgTS and the baselines? Do the 800 training instances described in Line 914 differ across epochs? Have you evaluated PgTS trained on the same fixed training set as the baselines?
-
Does the 10-hour time limit in Line 914 include the pretraining time for DiffILO, whose parameters are used for initialization? If the pretraining time is not included, what is the total training cost of PgTS including pretraining, and how does it compare with that of the baselines? Given the paper’s motivation that obtaining optimal solutions for supervision can be computationally expensive (Line 230), the total training cost including pretraining is important for assessing this claimed advantage.
-
Which 11 instances are used in Appendix E.5, and which of them were used for training and for testing?
-
The pruning rule in Section 4.1 is described only as checking whether the lower bound of the left-hand side exceeds the right-hand side. Could you state this bound explicitly, in particular how unassigned variables contribute to it?
13 comments
[W1-b] RL-SPH
We agree that RL-SPH is closely related, and that our introduction misclassified it. RL-SPH is a reinforcement-learning start primal heuristic. Starting from an infeasible solution, its policy repeatedly increases or decreases selected integer variables, guided by rewards on constraint violation and objective value, and reaches feasible solutions without an external solver. We have corrected its classification and discussed it in the related work.
We admit that RL-SPH and PgTS address the same challenge: generating high-quality feasible solutions with a learned model and without an external solver. Unlike many existing methods that directly predict variable values from optimal solutions without guaranteeing feasibility, both approaches prioritize finding feasible solutions, but they take different routes. RL-SPH learns to reach feasibility step by step, whereas PgTS learns to guide a feasibility-guaranteed tree search toward better solutions. This route brings two advantages:
- Feasibility independent of the model. RL-SPH reaches a feasible solution if every step strictly reduces the total violation within the bounds (its Proposition 1). As stated by Lee & Kim (2026) in App. A.2, the learned policy is assumed, rather than guaranteed, to do so. In PgTS, any guidance pair yields a feasible solution whenever one exists (our Prop. 1), regardless of the model.
- A direct learning signal. RL-SPH moves through infeasible states, so its reward must weigh bound, violation, and objective terms over two phases. Every PgTS sample is feasible, so the guidance is trained on the objective values of the returned solutions alone, with no weights between feasibility and objective to tune.
RL-SPH’s code has not been released, so we did not include it as a baseline at submission. For this response, we reimplemented RL-SPH following its paper as closely as possible, with LP initialization as in its default setting, and evaluated it on our test sets and hardware. Both methods reach a 100% feasible ratio on all three benchmarks. Since RL-SPH keeps improving after its first solution, we also report its PG after 10, 100, and 1000 s. PG is measured against the Gurobi best-known values, as in Table 1. The RL-SPH paper instead uses the best solution among the compared methods as reference, so its reported values are not directly comparable.
| PG (time in s) | CA | IS | SC |
|---|---|---|---|
| RL-SPH, first solution | 35.93 (0.152) | 35.19 (1.428) | 96.86 (0.564) |
| RL-SPH, after 10 s | 16.36 | 20.39 | 94.93 |
| RL-SPH, after 100 s | 14.84 | 11.95 | 94.63 |
| RL-SPH, after 1000 s | 14.76 | 10.75 | 94.60 |
| PgTS, first solution (Table 1) | 7.90 (0.192) | 1.23 (0.214) | 11.61 (0.825) |
At equal feasibility, PgTS’s first solution, found within one second, is better than RL-SPH’s solution after 1000 s on all three benchmarks. We have added this comparison to Sec. 5.2 and App. E.
[W2-a] Binary scope and general integer variables
Thank you for pointing the scope issue out. We have followed learning-for-ILP literature to perform experiments with typical ILPs with binary variables. We argue that PgTS can apply to broader ILPs by reformulating bounded integer variables to binary variables. Below we explain how the reformulation affects the feasibility guarantee and the search, and report an experiment with general integer variables.
For example, we use the standard reformulation of the bounded knapsack problem, where each item has at most copies. Each is replaced by binary bits with , where the block sizes end with a remainder so that they sum to . Then takes exactly the values . We provide an illustrative case for better understanding: an item with value 5, weight , and at most 3 copies can turn to two 0/1 items: item A with value 5 and weight w (one copy), and item B with value 10 and weight (two copies). Taking 0, 1, 2, or 3 copies of the original item exactly corresponds to taking none of A or B, taking A but not B, taking B but not A, and taking both A and B, separately. The binarized problem is thus a binary multi-dimensional knapsack.
We have three straightforward conclusions:
- Feasibility guarantee. Substituting into the original ILP gives a binary ILP of the form of Eq. 1, which is feasible exactly when the original ILP is. Prop. 1 applies to it directly, so PgTS returns a feasible solution of the original ILP whenever one exists.
- Search efficiency. The number of binary variables grows only logarithmically with the bounds. Fixing tightens one bound of by : raises its lower bound by and lowers its upper bound by . Binarization is therefore not expected to reduce search efficiency significantly.
- Learned guidance. Each bit is an ordinary 0/1 decision with a clear meaning: whether to take a block of units of . In the example above, the two bits are simply two 0/1 items, so a binarized bounded knapsack is again a 0/1 knapsack. As for any binary variable, the model predicts a reference value for each bit and places it in the variable ordering, just as what we did for CA, IS,and SC.
Experiment: We evaluated PgTS on multi-dimensional bounded knapsack problems (BKP) with 400 item types and 30 resource constraints. The bound on the copies of item is drawn uniformly from , and the capacities are with . The instances are binarized as above. Gurobi is evaluated by its first solution on both the original integer model and the binarized model.
| Method | Model | PG ↓ | Time (s) ↓ |
|---|---|---|---|
| Gurobi | integer | 19.68 | 0.091 |
| Gurobi | binarized | 19.59 | 0.110 |
| DiffILO | binarized | 45.74 | 0.130 |
| PgTS | binarized | 13.28 | 0.301 |
Gurobi’s first solution has nearly the same quality and time on both models, so binarization does not make the instances materially harder. On the binarized model, PgTS gives the lowest PG, about one third lower than Gurobi on the original integer model, in 0.3 s. We have added this comparison in App. E.
We thank the reviewer for the detailed review, and for recognizing that PgTS avoids optimal-solution labels and generalizes to instances up to eight times larger. We answer each point below.
[W1-a] Preference learning and BOPO
We agree that the paper should have discussed prior work on preference learning. We have added a paragraph in Related Works covering pairwise preference models (Bradley & Terry, 1952), learning from preferences (Christiano et al., 2017; DPO, Rafailov et al., 2023), and preference optimization for neural CO (Pan et al., ICML 2025; BOPO, Liao et al., ICML 2025).
We also notice that our loss (Eqs. 2–3) conceptually resembles BOPO’s to some extent: both anchor on the best sample and scale each pairwise preference by relative objective values. We have cited BOPO at Eq. 2, admitting that our loss form is close to it. However, PgTS differs from BOPO in their aims, how they obtain feasible solutions, and how preference loss is used, as specified below:
Moreover, we have noted that our main contribution is more than preference learning itself (last paragraph of Sec. 1), but learning guidance for a feasibility-guaranteed tree search, which makes such a loss applicable to ILPs.
It is not trivial to directly investigate the empirical difference given the difference in problems. However, we still manage to perform a direct experimental comparison. Among our benchmarks, we find IS has an established learned feasibility-preserving construction, LwD (Ahn et al., ICML 2020), which always yields valid independent sets. We therefore compare PgTS with LwD on IS. We integrated LwD with the BOPO loss and trained it on the same IS distribution with the same 10-hour budget, and then sampled five solutions per test instance, as did for PgTS:
Both methods are always feasible and very fast. But the primal gap (PG) of LwD is about 11 times that of PgTS. This indicates that, with the same kind of preference loss, learning to guide a tree search yields much better solutions on IS than learning a problem-specific construction policy directly.
To verify that the advantage of PgTS is not only from our preference loss contribution, we further retrained PgTS on CA with Bradley–Terry, Plackett–Luce, and REINFORCE losses in the same setting. It reaches PG 7.2–8.9, below every CA baseline in Tables 1 and 14 (best: 11.89); details are in our response to Reviewer TTUi (Q3). These results further indicate that the gains of PgTS come from the framework rather than only from the preference loss: the bipartite GNN with two guidance heads, the feasibility-guaranteed tree search, and training on the outcome of the same search used at inference. In other words, our main contribution is not only the preference learning itself. The effects of other main contributions have been ablated in Sec. 5.6.