acceptodds
Under review as a conference paper at ICLR 2027

Preference-Guided Tree Search for Feasible Solution Generation in Integer Linear Programming

Abstract

Integer linear programming (ILP) arises in many critical decision-making tasks. While recent learning-based methods have shown promise in producing feasible solutions for ILPs, many rely on variable predictions that, on their own, do not necessarily yield high-quality solutions or even feasible solutions during inference. To address this gap, we propose a preference-guided tree search (PgTS) framework for high-quality feasible solution generation. Building on an underlying tree search that guarantees finding a feasible solution, PgTS jointly learns two guidance components to improve search efficiency and solution quality: reference values, which indicate preferred variable assignments, and variable ordering, which reflects the sequence in which variables are explored along the search. To align training with inference, PgTS evaluates each guidance pair through the same tree-search procedure used at inference, so that the learning signal directly reflects the quality of the resulting feasible solution. Based on the search outcomes, objective-based preference learning derives contrastive signals from their objective values to favor better guidance pairs, without requiring optimal-solution labels. Extensive experiments across ILP benchmarks show that PgTS achieves state-of-the-art solution quality and provides strong initial solutions that improve long-term solver performance over conventional and learning-based methods.

Primary area:
optimization
Keywords:
Integer Linear Programming, Preference Learning, Feasible Solution Generation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_MrZcOpenReview ↗
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
  1. 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.

  2. 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 x4=0x_4 = 0 is assigned, the lower-bound check passes, yet both remaining choices for x3x_3 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
  1. Eq. 1 defines a minimization problem, and Section 3 assumes that the objective satisfies cTx>0c^T x > 0 for all feasible xx. 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?

  2. 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?

  3. Does the primal integral (PI) include the execution time of the trained model and the tree search of PgTS?

  4. 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?

  5. 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.

  6. Which 11 instances are used in Appendix E.5, and which of them were used for training and for testing?

  7. 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

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:

  1. Aim. BOPO addresses routing and scheduling problems, where masking during construction keeps every solution feasible, so the learning merely needs to improve solution quality. PgTS addresses general ILPs, where constraints couple many variables and no general construction can guarantee feasibility. Directly constructed solutions are often infeasible (feasible ratios as low as 43.4% in Table 1), and infeasible samples cannot provide effective pairwise comparison signals between objective values, so the BOPO loss designed for feasible solutions are ill-formed to build the preference learning signals.
  2. Solution generation. BOPO obtains feasibility from problem-specific masking in its construction, without applicability and feasibility guarantee in broader problem types. By contrast, PgTS uses the proposed tree search to turn every guidance pair (r,τ)(r, \tau) into a feasible solution over general bounded ILP decision variable space, whenever one exists (Prop. 1). Every sample therefore has a guarantee to gain the feasibility with a valid objective value, enabling the calculation of preference signals.
  3. Training signal. BOPO’s loss raises the likelihood of better solutions under its construction policy, i.e., of the sequences of construction steps that build them. PgTS’s loss raises the likelihood of better guidance pairs: pθ(z∣I)p_\theta(z \mid I) combines Bernoulli distributions over reference values with a Plackett–Luce distribution over orderings, and each pair is scored by the objective value of the solution returned by the same search used at inference. One preference signal thus trains both where the search starts and how it recovers from infeasible reference values through backtracking.

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:

Method (IS)Feasible ratioPG ↓Time (s)
LwD + BOPO loss100%13.520.120
PgTS100%1.230.214

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.

[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:

  1. 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.
  2. 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)CAISSC
RL-SPH, first solution35.93 (0.152)35.19 (1.428)96.86 (0.564)
RL-SPH, after 10 s16.3620.3994.93
RL-SPH, after 100 s14.8411.9594.63
RL-SPH, after 1000 s14.7610.7594.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 yy has at most UU copies. Each y∈{0,…,U}y \in \{0,\dots,U\} is replaced by ⌈log⁡2(U+1)⌉\lceil \log_2(U+1) \rceil binary bits bkb_k with y=∑kskbky=\sum_k s_k b_k, where the block sizes s=(1,2,4,… )s = (1, 2, 4, \dots) end with a remainder so that they sum to UU. Then yy takes exactly the values 0,…,U0,\dots,U. We provide an illustrative case for better understanding: an item with value 5, weight ww, 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 2w2w (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:

  1. Feasibility guarantee. Substituting y=∑kskbky=\sum_k s_k b_k 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.
  2. Search efficiency. The number of binary variables grows only logarithmically with the bounds. Fixing bkb_k tightens one bound of yy by sks_k: bk=1b_k=1 raises its lower bound by sks_k and bk=0b_k=0 lowers its upper bound by sks_k. Binarization is therefore not expected to reduce search efficiency significantly.
  3. Learned guidance. Each bit is an ordinary 0/1 decision with a clear meaning: whether to take a block of sks_k units of yy. 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 UjU_j on the copies of item jj is drawn uniformly from {1,…,20}\{1,\dots,20\}, and the capacities are Ci=α∑jwijUjC_i=\alpha\sum_j w_{ij}U_j with α∈{0.25,0.5,0.75}\alpha\in\{0.25, 0.5, 0.75\}. The instances are binarized as above. Gurobi is evaluated by its first solution on both the original integer model and the binarized model.

MethodModelPG ↓Time (s) ↓
Gurobiinteger19.680.091
Gurobibinarized19.590.110
DiffILObinarized45.740.130
PgTSbinarized13.280.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.

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

PgTS targets high-quality feasible solution generation for binary ILPs. Its backbone is a backtracking depth-first tree search that checks constraint lower bounds at each partial assignment and prunes on violation, so any returned solution is feasible by construction. A two-headed GNN jointly learns the two guidance components of this search: reference values, which specify the binary assignments tried first, and a variable ordering, which determines the assignment sequence. Training is aligned with inference: each sampled guidance pair is evaluated by running the same tree search used at test time, and a pairwise preference loss built from the objective values of the resulting feasible solutions rewards pairs that yield better solutions, without requiring optimal-solution labels. Generated solutions also serve as warm starts and local-branching neighborhoods for Gurobi and SCIP.

Critical strengths
  1. The coupling of a constructive feasibility guarantee with label-free, search-aligned preference learning is a clean design.
Critical weaknesses
  1. The evidence base is dominated by synthetic benchmarks, and the only real data study is too small to support the paper's practical effectiveness
Questions for authors
  1. Training-data alignment: PgTS trains on instances generated on the fly while baselines use the fixed DiffILO training set. Are the two training distributions identical? How much does PgTS lose when retrained on the exact fixed training set the baselines use?
  2. Could you test more MIPLIB instances to verify the effectiveness of PgTS on real-world problems?
2 comments

We thank the reviewer for the positive assessment, and in particular for recognizing the coupling of a constructive feasibility guarantee with label-free, search-aligned preference learning. We address the concerns below.

[W1, Q2] More MIPLIB instances

Following the reviewer’s suggestion, we conducted a third MIPLIB study to complement the two reported in Appendix E. Many MIPLIB instances lack structurally similar counterparts, making it extremely challenging to train a model directly on the full benchmark. Among instances containing only binary variables and with known optimal solutions (allowing accurate measurement of PG), we identified two instance families, each containing at least five instances. These families comprise 11 instances in total, of which we use seven for training and the remaining four larger instances for testing, as detailed below.

FamilyTrainingTesting
opm2opm2-z6-s1, opm2-z7-s8, opm2-z8-s0, opm2-z10-s4opm2-z12-s8
sp9 & nseq (railway planning)sp97ar, sp97ic, n2seq36fsp98ar, sp98ic, n3div36

Following the evaluation protocol in Table 16, we evaluate each method using Gurobi as the underlying solver. We measure PG (relative to the known MIPLIB optimal values) and PI at 10, 100, and 1000 seconds, averaging the results across the four test instances. As shown below, PgTS consistently achieves the lowest average PG and PI at all three time points, providing additional evidence for PgTS’s effectiveness. We have incorporated this study into Appendix “MIPLIB Benchmarking”.

MethodPG@10s ↓PI@10s ↓PG@100s ↓PI@100s ↓PG@1000s ↓PI@1000s ↓
Gurobi19.72253.9611.581729.28175687.96
DiffILO19.86260.579.371787.173.476515.59
PgTS14.09220.755.591282.311.583675.29

[Q1] Training data

Yes, the training distributions are identical: PgTS draws its instances on the fly from the same generators (Gasse et al., 2019) and parameters that produced the fixed training set of DiffILO used by the baselines. In each epoch, 800 new instances are generated, so the instances differ across epochs. The protocols differ because on-the-fly training does not fit the baselines: PaS, ConPaS, Apollo, and FMIP need (near-)optimal solutions as labels, which must be computed in advance for every training instance, and DiffILO optimizes its unsupervised objective over many iterations on the same instances (Geng et al., 2025). PgTS needs no labels, so a fresh instance costs only its generation time that is much shorter. Nevertheless, PgTS uses the same generator with the same parameters to generate the training instances, so it is trained on instances of the same distribution, which ensures fairness.

To further isolate the effect, we ran experiments that trained PgTS on exactly the fixed CA training set used by the baselines, as you requested. The results are shown in the table below. It reflects small difference between the two training settings, and PgTS trained on the fixed set still outperforms the baselines in terms of PG.

CAPG ↓Time (s) ↓
PgTS, on-the-fly instances7.900.192
PgTS, fixed training set8.450.246
SCIP (best baseline in Table 1)17.310.046
DiffILO35.530.031

We hope these new results address the reviewer’s concerns and are happy to answer any further questions.

AuthorsOpenReview ↗

Looking Forward to Your Feedback

Dear Reviewer zxCe,

Thank you again for your careful reading and positive comments. As the discussion period ends in less than two days, we would like to kindly check whether our response has addressed your concerns. In particular, we added a comparison on more MIPLIB instances and evaluated PgTS trained on fixed datasets. If anything is still unclear, we would be happy to provide further clarification before the deadline.

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

This paper proposes PgTS, a preference-guided tree search framework for generating high-quality feasible solutions to binary ILPs. The method jointly learns two forms of guidance—reference values (preferred assignments) and variable ordering—to steer a backtracking tree search that guarantees feasibility. Training uses objective-based preference learning: multiple guidance pairs are sampled, each runs the same feasibility-guaranteed search used at inference to produce a feasible solution, and a pairwise loss increases the joint likelihood of guidance pairs that yield better objective values without requiring optimal labels.

Critical strengths

1) Technical novelty and innovation: Jointly learning value guidance (reference values) and search guidance (variable ordering) specifically for a feasibility-guaranteed backtracking tree search is a neat and underexplored angle in the ML4CO literature. It reconnects to classical CP heuristics while learning them end-to-end for ILPs. Objective-based preference learning removes the need for optimal labels while still driving the model toward better first-feasible solutions. The idea of contrasting guidance pairs by downstream objective outcomes is elegant and practical.

2) Experimental rigor and validation: Broad evaluation across three standard ILP families (CA, IS, SC) with both direct feasible generation and long-term solver integration (Gurobi/SCIP) at multiple time budgets. Additional comparisons against SCIP primal heuristics and classical ordering heuristics isolate the contributions of learned guidance; generalization experiments to substantially larger instances strengthen practical relevance.

3) Clarity of presentation: The overall pipeline is clearly explained, including guidance sampling, feasibility-check/backtracking, and preference construction. The role of the two heads (reference values vs. variable ordering) is well-motivated with illustrative examples. Implementation notes, initialization strategy, and solver integration are described at a high level (with references to appendices for details).

Critical weaknesses

1) Technical limitations or concerns: The pruning description in Section 4.1 is underspecified for general linear constraints; for ≥ or = constraints, feasibility pruning typically requires using both lower and upper bounds, not only a “lower bound check.” While implementation via SCIP probing likely handles this safely, the main text should clarify correctness for all constraint senses and mixed-sign coefficients.

2) Experimental gaps or methodological issues: Initialization uses DiffILO for the value head and GNN layers; this could confer a sizable advantage over baselines. Although the appendix reportedly includes other initializations, stronger in-main ablations (random init, other pretrained predictors, and “ordering-only” vs “value-only”) would help isolate the contribution of PgTS.

3) Missing related work or comparisons: Beyond RL-SPH, there exists work on learning CP-style value and variable ordering heuristics; some additional discussion and/or small-scale comparisons (if feasible) would further ground the contribution within the CP/ML crossover literature.

Questions for authors
  1. BOPO (Liao et al., ICML 2025): Best anchored+Objective guided paired preference optimization, adaptively scaling gradients based on differences in target values, almost isomorphic to the mechanism of Eq. 2-3 (in the case of TSP/JSP and other structural NCOs) - this directly affects the novelty statement of the contribution of "object-based preference learning". Please explain the substantive differences between it and this article

  2. Pruning details: How are pruning checks implemented for ≥ and = constraints and for mixed-sign coefficients? Do you compute both lower and upper bounds per constraint or fully delegate to SCIP’s propagation in probing mode? Please clarify safety and provide a brief formula in the main text.

  3. Preference loss: Why multiply the likelihood difference by the objective ratio in Eq. (2) instead of using a more standard Bradley–Terry or listwise ranking loss with a temperature? Did you try alternative formulations, and how sensitive are results to this choice and the epsilon?

5 comments

We thank the reviewer for the positive assessment of the joint learning of values and ordering, the experimental evaluation, and the presentation, and for the precise technical questions. We appreciate the opportunity to further clarify the remaining concerns.

[W1, Q2] Pruning for ≥\geq, == and mixed-sign constraints

Sec. 4.1 describes the check for the standard form of Eq. 1, which is used without loss of generality: ≥\geq constraints are multiplied by −1-1, and == constraints are split into two ≤\leq rows. The upper-bound check of a ≥\geq row thus becomes the lower-bound check of the negated row, and an equality is checked against both of its bounds through its two rows. For a row ∑iaixi≤b\sum_i a_i x_i \leq b and a partial assignment π\pi with assigned set SS, the lower bound of the left-hand side over all completions is

L(π)=∑i∈Saiπi+∑i∉Smin⁡(ai,0).L(\pi) = \sum_{i \in S} a_i \pi_i + \sum_{i \notin S} \min(a_i, 0).

Each unassigned variable contributes its smallest possible term, 00 if ai>0a_i > 0 and aia_i if ai<0a_i < 0, so mixed-sign coefficients need no special treatment. The node is pruned if L(π)>bL(\pi) > b for some row. Since L(π)L(\pi) is the exact minimum over all completions, a node is pruned only if no completion satisfies the constraint. Hence no feasible solution is pruned, and Prop. 1 holds for all constraint senses and coefficient signs. We have added this formulation to App. C.1.

To answer Q2 directly: yes, our implementation delegates the check to SCIP’s propagation in probing mode, which performs this check automatically. Note that the tree search and its check are independent of the solver used for the implementation.

We also performed another experiment on instances with equality and mixed-sign constraints, and found PgTS still achieves superior performance. Please see our response to Reviewer MrZc (W2-b) for details.

[W2] Initialization and ablations

We agree that these ablations are important for isolating the contribution of PgTS and should be presented together in the main text. Following your suggestion, we have moved them into Sec. 5 in the revision: random initialization (PgTS_NoIni) and initialization from another pretrained predictor, PaS (PgTS_PaS), are reported in Table 6, and the ordering-only and value-only variants (PgTS_Order and PgTS_Value) in Table 5.

[W3-a] 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:

  1. 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.
  2. 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)CAISSC
RL-SPH, first solution35.93 (0.152)35.19 (1.428)96.86 (0.564)
RL-SPH, after 10 s16.3620.3994.93
RL-SPH, after 100 s14.8411.9594.63
RL-SPH, after 1000 s14.7610.7594.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.

[W3-b] Learned CP heuristics

We agree and have discussed learned value-selection heuristics inside CP solvers (Cappart et al., AAAI 2021; Chalumeau et al., CPAIOR 2021; Marty et al., CP 2023) and learned variable-ordering heuristics for CSPs (Song et al., EAAI 2022) in Related Works. Learned CP heuristics and learning-based ILP methods are mostly evaluated on different problem classes, e.g., graph coloring and TSPTW versus CA, IS, and SC. Among recent learned CP heuristics, Marty et al. (2023) is the only one we found that is both open-source and evaluated on one of our problem classes, maximum independent set (IS), so we compared PgTS with it on IS. Their method learns value selection under a fixed variable ordering, as a step-wise RL policy inside the SeaPearl solver that calls the network at every branching decision. PgTS instead learns the values and the ordering jointly and computes both in one forward pass.

Marty et al. (2023) evaluate MIS on Barabási–Albert graphs with up to 100 nodes. At this size, calling the network at every node already makes their search much slower than impact-based search (253 s vs. 8 s per instance in their Table 1), so we used their largest setting: 100 training and 20 test graphs with 100 nodes from SeaPearl’s generator, given to PgTS as the ILP with one constraint per edge. Both methods were trained only on these 100 graphs. We trained their model with the authors’ code and settings for 10 hours, while PgTS took 2 hours in total, including its initialization. Since SeaPearl keeps searching after its first solution, we let it continue, and for comparison let Gurobi continue from the solution of PgTS, as the long-term settings in Sec. 5.3. The results are shown below. PgTS finds a better first solution about 20 times faster. Including its own inference and search, PgTS + Gurobi finds the optimum of all 20 graphs within 0.70 s, while SeaPearl’s search still has a PG of 1.13 after 1000 s. We have added this comparison in App. E.

MethodFirst solution: PG ↓Time (s)Long-term search: PG ↓Time (s)
Marty et al. (2023)27.380.3554.80 / 1.13100 / 1000
PgTS19.200.0180.00≤ 0.70
Reviewer_dDgqOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper proposes preference-guided tree search, a new machine learning-augmented backtracking algorithm for solving integer linear programs. The machine learning model takes a bipartite graph representation of the integer linear program and produces both a variable ordering and reference values for each variable, which can then be used to guide the search process. Training is done by sampling multiple pairs of variable orderings and reference values, which are then used in the search to generate feasible solutions. These are then compared in a contrastive pairwise loss function so that the model learns to produce variable orderings and reference values that lead to good feasible solutions (meaning a good objective value). The method is evaluated on three ILP benchmarks. It consistently produces high-quality feasible solutions with significantly better primal gaps than the compared baselines and short inference times. The authors also show that the generated solutions can improve the anytime performance of Gurobi and SCIP when used as warm starts, that the approach outperforms traditional heuristics, and that the learned model generalizes well to larger instances without retraining.

Critical strengths

Very clearly written. The entire paper is written very clearly and was a pleasure to read. At no point did I feel confused by the writing style or the structure of the exposition.

Feasibility is guaranteed. By augmenting backtracking search, the method guarantees feasibility of the produced solution.

Good coverage of different baselines. There are both conventional solvers (Gurobi and SCIP), as well as four prediction-guided search methods and two feasibility-aware solution generation methods. That's a nice coverage of different classes of approaches.

The experimental evaluation is very convincing. PgTS consistently produces high-quality feasible solutions across all three benchmarks, with much better primal gaps than the compared baselines while having short inference times. The results also show that the produced solutions are useful as warm starts for Gurobi and SCIP, and improve their anytime performance significantly. I also appreciate the comparisons with conventional search heuristics, and the instance size generalization experiment, which shows that models trained on smaller instances generalize quite well to larger ones.

Critical weaknesses

Missing closely related work. The paper does not discuss BOPO (Liao et al., ICML 2025), which proposes preference optimization for neural combinatorial optimization. BOPO uses a very similar objective-based pairwise preference loss, including the selection of the best-performing candidate as an anchor and weighting preferences by the relative objective values of the generated solutions. This closely resembles the preference-learning approach proposed in Section 4.2 of this paper. While PgTS applies this idea to learning guidance for a feasibility-preserving tree search rather than directly generating solutions, I think BOPO is highly relevant prior work that should be acknowledged and discussed.

Limited novelty of the individual components. I feel that the individual ideas behind the method are not particularly novel. The preference-learning loss is very similar to the one used in BOPO, and the overall approach combines this with fairly standard backtracking search and an established bipartite graph representation of ILPs processed by a GNN. That said, while worth mentioning, I do not consider this a major weakness. I think the contribution lies more in how these components are combined into a coherent approach for learning search guidance, and the strong experimental results suggest that this combination works well in practice.

Only applicable to binary linear programs. While it is true that all bounded integer variables can be binarized, this is still a limitation that is worth noting.

Computational cost of training. While the proposed preference-learning approach avoids the need for optimal solution labels, it requires running the backtracking search many times per training instance to construct the preference pairs. This could make training quite expensive, and it is not clear how this cost compares to that of obtaining training labels for existing methods.

Questions for authors

The preference-learning objective appears to consider only the quality of the feasible solutions returned by the tree search, without explicitly accounting for the number of backtracks or search nodes visited. Is this a deliberate design choice? I wonder whether the authors have any insights into how the learned guidance affects the number of backtracks compared with standard variable-ordering heuristics. Have the authors also considered incorporating the number of backtracks directly into the preference-learning objective, so that the model learns to favor guidance that produces not only high-quality solutions but also shorter searches?

I found it interesting that the model is initialized using the prediction head and graph convolution layers from DiffILO. I wonder how much of the final performance comes from the additional training with the proposed preference loss, and how much could already be achieved by running the same tree search directly using DiffILO's predictions. Could the authors provide some insight into this?

Could the authors provide more insight into the computational cost of training PgTS? In particular, how does the cost of repeatedly running tree search to construct preference pairs compare with the cost of generating training labels for methods that rely on optimal or high-quality solutions?

10 comments

We thank the reviewer for the careful reading and for the positive comments on the presentation, the feasibility guarantee, and the experimental evaluation. We address your remaining concerns below.

[W1] Relation to BOPO

We thank the reviewer for pointing us to BOPO (Liao et al., ICML 2025) and agree that it is highly relevant prior work. 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 added a paragraph on preference learning, including BOPO, in Sec. 2.3, and cited BOPO at Eq. 2, noting that our loss form is close to it. As the reviewer notes, PgTS applies this idea to learning guidance for a feasibility-guaranteed tree search rather than to generating solutions directly. This is where our main contribution lies (last paragraph of Sec. 1): it makes such a loss applicable to ILPs.

PgTS differs from BOPO in their aims, how they obtain feasible solutions, and how preference loss is used, as specified below:

  1. Aim. BOPO addresses routing and scheduling problems, where masking during construction keeps every solution feasible, so the learning merely needs to improve solution quality. PgTS addresses general ILPs, where constraints couple many variables and no general construction can guarantee feasibility. Directly constructed solutions are often infeasible (feasible ratios as low as 43.4% in Table 1), and infeasible samples cannot provide effective pairwise comparison signals between objective values, so the BOPO loss designed for feasible solutions are ill-formed to build the preference learning signals.
  2. Solution generation. BOPO obtains feasibility from problem-specific masking in its construction, without applicability and feasibility guarantee in broader problem types. By contrast, PgTS uses the proposed tree search to turn every guidance pair (r,τ)(r, \tau) into a feasible solution over general bounded ILP decision variable space, whenever one exists (Prop. 1). Every sample therefore has a guarantee to gain the feasibility with a valid objective value, enabling the calculation of preference signals.
  3. Training signal. BOPO’s loss raises the likelihood of better solutions under its construction policy, i.e., of the sequences of construction steps that build them. PgTS’s loss raises the likelihood of better guidance pairs: pθ(z∣I)p_\theta(z \mid I) combines Bernoulli distributions over reference values with a Plackett–Luce distribution over orderings, and each pair is scored by the objective value of the solution returned by the same search used at inference. One preference signal thus trains both where the search starts and how it recovers from infeasible reference values through backtracking.

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 for PgTS:

Method (IS)Feasible ratioPG ↓Time (s)
LwD + BOPO loss100%13.520.120
PgTS100%1.230.214

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.

[W2] Novelty of individual components

We agree that the preference-based loss, the backtracking search, and the bipartite GNN each build on established ideas, and we appreciate the reviewer’s view that the contribution lies in how they are combined. We see the value of PgTS mainly in what this combination makes possible for ILPs, where existing approaches face complementary limitations. Learning-based methods mostly predict variable values, and the predictions themselves do not guarantee feasibility. Prediction-guided search methods (e.g., PaS, ConPaS, Apollo) therefore rely on a solver to correct or search around the predictions, and they need (near-)optimal labels that are costly to collect. Feasibility-aware generation methods (Diffusion, DiffILO) raise the feasible ratio empirically, but it can still be as low as 49.0% (Diffusion, IS) or 43.4% (DiffILO, SC) in Table 1. Backtracking search, in contrast, guarantees feasibility, but its solution quality depends on the guidance: with hand-designed orderings on DiffILO’s reference values, the PG on SC remains around 58, and IMPACT takes over 2,000 s (Table 3).

In PgTS, the three components are coupled so that each addresses one of these limitations:

  • Feasibility comes from the search, not from the prediction. The tree search turns any guidance pair into a feasible solution whenever one exists (Prop. 1), so the model only needs to steer the search toward good solutions. PgTS reaches a 100% feasible ratio on all three benchmarks, outperforming most learning-based baselines in Table 1.
  • Training uses the final solutions instead of labels. Since every sample is feasible, guidance pairs can be compared by the objective values of the solutions returned by the same search used at inference. Preference learning turns these comparisons into a training signal without optimal-solution labels, even though the search itself is non-differentiable.
  • The guidance is learned rather than hand-designed. The GNN learns the variable ordering jointly with the reference values, adapting the order of decisions to each instance and its reference values instead of following a fixed rule.

The ablations suggest that the combination matters: neither head alone matches the full model on CA (15.36 and 11.40 vs. 7.90, Table 5), and the same tree search guided by DiffILO’s reference values and heuristic orderings remains well behind PgTS (Table 3; see Q2).

[W3] Restriction to binary ILPs

We agree that this is worth noting. Like most prior work on learning-based solution generation (Nair et al., 2021; Han et al., 2023; Geng et al., 2025; Liu et al., 2025), our main experiments focus on binary ILPs. As the reviewer notes, bounded integer variables can be binarized, and we will state explicitly in Eq. 1. Our response to Reviewer MrZc (W2-a) reports an experiment on bounded knapsack problems, where PgTS on the binarized instances reaches a lower PG than Gurobi’s first solution on the original integer model.

We have also considered two direct extensions, which we have not yet explored experimentally but hope they can provide potential insights:

  • Native integer variables. The Bernoulli value head could be replaced by a categorical distribution over each variable’s domain, with the search trying values in order of their predicted probabilities.
  • MILPs with continuous variables. The tree search could run over the integer variables only, solve the remaining LP once they are all fixed, and backtrack if the LP is infeasible.

[W4, Q3] Training cost

Running the tree search for many guidance pairs does add to the training cost, but each search is cheap, and the total cost compares favorably with that of label-based methods. As shown in Table 1, PgTS takes 0.192 s, 0.214 s, and 0.825 s per guidance pair on CA, IS, and SC, including model inference and the tree search. During training, the searches for different guidance pairs are independent of each other and can run in parallel on CPU cores, which can further decrease the tree search cost in training.

Even with pretraining included, PgTS takes less time to train than methods that need labels. Our full pipeline takes about 22 hours per benchmark: about 12 hours to pretrain DiffILO and 10 hours of preference training. Since DiffILO is trained without labels, no optimal-solution labels are needed at any stage. For comparison, take PaS as a conservative example, since its model is relatively simple and cheap to train. PaS collects labels by running Gurobi for one hour on each of its 300 training and validation instances. This takes 18.75 wall-clock hours on the same 16-core CPU, and many of the labels are still only near-optimal. With another 6 hours of training, PaS needs 24.75 hours in total, already longer than our 22 hours. The gap should widen on larger instances: label collection time can grow exponentially with instance size, whereas the search effort of PgTS grew roughly linearly up to 12,000 variables (Table 9).

Moreover, pretraining is not essential: PgTS_NoIni, trained from random initialization for 10 hours in total, reaches an inference PG of 17.99 on CA, about half of DiffILO’s 35.53, and the same 10-s PG with Gurobi as the full model (0.47; Table 6). However, we agree with the reviewer’s concern and recognize two limitations of the current design. First, the short search times above are empirical, while the worst-case complexity of the tree search remains exponential (Sec. 4.1). Second, the tree search is inherently sequential and cannot fully exploit the parallelism of GPUs, as noted in our conclusion. We see two possible directions to address them: designing a better loss and pretraining that take search efficiency into account (see Q1), and developing feasibility-guaranteed search procedures that make better use of parallel hardware.

[Q1] Backtracks in the preference objective

Yes, using only the objective value was a deliberate choice, although we agree that search effort also matters. We considered adding the number of backtracks to the objective as a penalty term when constructing preferences, but found the penalty coefficient hard to tune, since objective values and backtrack counts lie on scales that vary across instances and problem classes. As the search times and backtrack counts were modest on our experiments (Table 9), we did not pursue this further. We thank the reviewer for this suggestion and agree that incorporating search effort into the preference is a promising direction. Possible ways include penalizing backtracks or using them to break ties between guidance pairs with equal objective values. We have added this further direction to the conclusion.

[Q2] Contribution of DiffILO initialization

Our existing experiments can answer this question: Table 3 evaluates the same tree search guided directly by DiffILO’s predictions, and Tables 8 and 9 further separate the contributions of the two output heads and of the initialization on CA. In the MinDom and IMPACT rows of Table 3, the reference values are sampled from DiffILO’s Bernoulli distribution, and the variable ordering is given by the heuristic. Sec. 5.4 wrongly suggests that these rows use our learned reference value, and we have corrected this in the revision. Compared with DiffILO’s direct predictions, the tree search alone restores feasibility and improves the PG, and preference training improves it further, most markedly on SC (IMPACT gives nearly the same PG as MinDom):

PG ↓CAISSC
DiffILO, direct prediction (Table 1)35.539.0471.72
DiffILO values + tree search + MinDom (Table 3)11.752.9958.02
PgTS7.901.2311.61

On CA, neither output head alone matches the full model: learning only the ordering on DiffILO’s values gives 15.36, and learning only the values with MinDom gives 11.40, compared with 7.90 for both (Table 5). The ordering is thus most useful when trained jointly with the reference values it is applied to. Without any pretrained parameters, PgTS_NoIni still reaches 17.99, about half of DiffILO’s 35.53 (Table 6). DiffILO initialization provides a useful starting point (17.99 →\rightarrow 7.90), while preference training contributes substantially on its own.

We hope these responses address the reviewer’s concerns and are happy to answer any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.