acceptodds
Under review as a conference paper at ICLR 2027

Reducing the Irreducible: Learning Reductions Beyond Exact Kernelization

Abstract

Exact reductions simplify hard optimization problems while preserving optimality, but their structural requirements can leave difficult instances unchanged. We study this limitation for maximum independent set, a natural test case given the extensive exact-reduction literature for independent set and minimum vertex cover. We develop heuristic reductions that aim to retain optimal or near-optimal solutions while continuing to simplify instances on which exact rules stall. In reduce-then-solve, language-model-guided program search generates a fast reduction rule before an exact solver processes the remaining graph. Rules are selected jointly for graph shrinkage, solution quality, and runtime. These criteria reflect the practical purpose of reduction: remove computational work without losing too much solution value or spending more time than it saves. In reduce-as-solve, localized greedy trials guide successive decisions on the shrinking graph. Language-model-guided program search also generates a policy that uses cached trial solutions to decide which vertices to include or discard, requesting fresh trials only when the stored evidence is insufficient. The reduction rule and cache policy are generated offline on small synthetic graphs and applied to hard instances without further tuning or language-model calls. Experiments on the evaluated methods show that reduce-then-solve enables more reduced graphs to be solved to optimality within a fixed time budget while usually retaining most of the reference solution value. Reduce-as-solve achieves higher solution quality than the tested reduction-based and greedy baselines, while localization and caching reduce trial-evaluation costs. These results demonstrate the practical value of heuristic reduction when the tested exact rules provide no simplification.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
heuristic reduction, kernelization, optimization

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_Nb1kOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies data reduction as preprocessing for finding a maximum independent set (MIS) in a given graph. The idea is to use heuristic reduction rules which are not necessarily maintaining an optimal solution but are fast to apply and yield close to optimal solutions. The authors used an LLM to propose which heuristics to apply. They introduced two settings called "Reduce-then-solve" and "Reduce-as-solve". In the first one, the reduced instance is given to a solver to optimally solve the residual instance, whereas in the second one the reductions continue until the instance is solved. The authors run experiments on some benchmark dataset showing that their approach yields indeed close to optimal solutions in less time compared with applying exact data reductions (which guarantee optimal solutions).

The idea to use ML for data reduction is not new. I find it not surprising that you can heuristically find good solutions with LLMs. The writing consists of rather high-level descriptions (often unclear or imprecise) without any real technical details. So, the paper does not really provide new interesting insights into data reduction for independent set nor any theoretical explanations/guarantees. I also believe that it does not really fit the scope of ICLR.

Critical strengths

Heuristic data reduction based on LLMs can improve running times to solve hard MIS instances near optimally.

Critical weaknesses

I do not really see why data reduction for MIS belongs to ICLR (except for using LLMs).

There are no deeper insights gained from the experiments. It seems not surprising that you can gain some advantage on some datasets from using heuristics. I find this not convincing enough.

Questions for authors

Do the experiments give any information which could improve our understanding of data reduction for MIS?

What about other optimization problems?

5 comments
AuthorsOpenReview ↗

[Authors Response (1/3)]

We thank the reviewer for the review. The review raises four concerns: novelty, significance, theory and scope. None of them is supported by a concrete argument, and the judgment on novelty in particular comes with no stated basis. Meanwhile, the review rates soundness 3 and lists as a strength that our approach "can improve running times to solve hard MIS instances near optimally." This makes the reviewer's core argument difficult for us to identify. Nonetheless, we will use our best effort to assist the reviewer resolve the concerns.

Scope. LLM-guided program search for combinatorial optimization is clearly within the scope of ICLR. ICLR publishes learning methods for combinatorial optimization [1], including work on MIS and its kernelization [2,3] as well as work on LLMs for optimization and NP-complete graph problems [4-5]. Our work belongs squarely to this line, with a distinct use of the LLM: it generates the reduction rules and the cache policies that our methods deploy. ICLR's reviewer guidelines also explicitly value empirical contributions alongside theoretical ones. The review offers no reason why our work falls outside this line of research.

Novelty and "not surprising.". The claim that using LLM for data reduction is unsupported. Stated this broadly, it could be made against any submission. The related prior work that we cite uses learning to choose which exact reductions to run [6]. Our work targets a different direction: hard instances on which the exact rules no longer fire at all. Once these rules stop firing, further reduction requires giving up some exactness, and our methods do so in a controlled way. To the best of our knowledge, we are first to study this direction as an application work. The remaining argument, that heuristics can "gain some advantage on some datasets", applies to almost any empirical ML methods for NP-hard problem. To the best of our knowledge, no existing work claims universal generalization, whether it is based on ML or on LLM search. Therefore, it identifies no specific weakness in our usage. We evaluate on the standard hard MIS benchmark, DIMACS/BHOSLIB instances. The reduction rules are learned on small graphs and applied to this benchmark without any tuning. Finally, the review describes the LLM as a tool to "propose which heuristics to apply." This misses its second role. In GenReduce, the LLM generates the reduction rule. In CacheReduce, it also generates the cache policy that guides the reduce-as-solve process. The LLM does not find solutions: it generates both programs during training, and it is never called at test time to solve the instances directly (Section 3, Appendix A).

AuthorsOpenReview ↗

[Authors Response (2/3)]

Understanding of data reduction for MIS. The reviewer asks whether the experiments improve our understanding of data reduction for MIS. They do, and this is the core of our contribution. We invite the review to reconsider our methods with the following evidence. Our experiments first show where exact reduction stops working. We then evaluate three methods designed to keep reducing graphs beyond that point.

  • Where exact reduction stops working. On the hard benchmark, all seven standard exact rules fire on 0% of instances, yet the stronger check still cost up to 138s per graph (Fig. 2, Tab. 6). Exact reduction can therefore remain correct while giving no practical benefit.
  • GenReduce: reduce beyond exact rules. LLM-guided program search generates a reduction rule, which we select by its shrinkage, solution quality and runtime. For NP-hard problems, data reduction exists to make an instance small enough for an exact solver to handle. On our hard benchmark, the exact rules remove NOTHING, so the solver must work on the full graph, and Gurobi proves optimality on only 52% of instances within one hour. After GenReduce, Gurobi proves optimality on 78% of the reduced graphs. Although this optimality applies to the reduced graphs, we report it because it shows how much heuristic reduction can do where exact rules do nothing: it turns many instances that are too hard for the solver into smaller ones it can solve completely. To see what this reduction costs, we map the solution of the reduced graph back to the original graph and compare its size with the best solution Gurobi finds on the original instances within one hour. Because the rule is heuristic, it can make mistakes and miss the optimality. Yet, on the benchmark, the recovered solution keeps a median of 97.7% of the optimality. Together, the two results show that our heuristic reduction can make hard instances solvable while losing only a small part of the solution value.
  • LocalizedReduce: Standard rollout uses trial solutions to build a single solution. LocalizedReduce instead uses the consensus among trial solutions, meaning the agreement on which vertices to include or discard, to decide which vertices to remove. Because we restrict trial starts to a minimum-degree vertex and its neighbors, total runtime falls by 98% compared with exhaustive rollout, at a cost of 1.3 percentage points in mean ratio (Tab.2).
  • CacheReduce: CacheReduce stores trial solutions from earlier steps. At each step, an LLM-learned policy decides whether this stored evidence is enough to include or discard a vertex, or whether fresh trials are needed. Compared with LocalizedReduce, it reduces mean runtime by about 20% more, at a cost of 0.6 percentage points in mean ratio (Tab.1). Together, these results show that data reduction for MIS does not have to stop when exact rules stop firing. Heuristic evidence, gathered and reused at a controlled cost, can keep reducing hard instances.

Theory. The paper does not claim theoretical guarantees. Heuristic reduction gives up optimality guarantees by design, as we state in the abstract and introduction. Our contribution is empirical: we show where exact reduction stops working and how reduction can continue beyond that point. Where a structural argument is available, we use it. For example, LocalizedReduce restricts candidates to N[u] because every maximum independent set intersects N[u] (Section 3). A theoretical analysis of heuristic reduction is an interesting direction, but it is beyond the focus of this submission.

Technical details. The review describes the paper as high-level descriptions without technical details. The paper provides:

  • pseudocode for both frameworks (Algorithms 1 and 2);
  • the full prompts and the verbatim code of the selected rules (Appendix D);
  • all seven exact rules with justifications (Appendix C);
  • definitions of all metrics (Appendix B). We invite the reviewer to point to any specific part that remains unclear, and we will clarify it.
AuthorsOpenReview ↗

[Authors Response (3/3)]

Other optimization problems. The design of our methods can be reused for other problems, but the algorithms in this paper are specific to MIS. We chose MIS because it has one of the richest collections of expert-designed reduction rules, which makes it the most demanding setting for showing where exact reduction stops working. With the limited time and computing resource, we added a quick trial experiment. We kindly guide the reviewer to the comments for all.

We hope this effort, our explanation on the overall design, together with the reviewer's own assessment that our results are sound, can motivate the reviewer to kindly reconsider the score accordingly.

[1] Kool et al. Attention, Learn to Solve Routing Problems! ICLR 2019.
[2] Böther et al. What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization. ICLR 2022.
[3] Acikalin et al. Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization. ICLR 2025.
[4] Tang et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation. ICLR 2025.
[5] Yang et al. Large Language Models as Optimizers. ICLR 2024.
[6] Großmann et al. Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem. arXiv 2024.

Reviewer_gxHjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies heuristic reductions for maximum independent set (MIS) when exact reduction rules become inactive. GenReduce uses offline LLM-guided program search to generate a vertex-deletion rule before passing the residual graph to Gurobi. LocalizedReduce restricts one-step rollout candidates to the closed neighborhood of a minimum-degree vertex. CacheReduce uses an LLM-generated policy to reuse previous rollout solutions, requesting fresh lookahead when cached evidence is insufficient. The authors evaluate these methods on 101 DIMACS/BHOSLIB instances, reporting solution quality relative to a one-hour Gurobi reference, runtime, and residual-graph solvability. The reported results demonstrate empirical quality–runtime trade-offs for heuristic reduction and rollout localization.

Critical strengths

LocalizedReduce demonstrates a useful quality–runtime trade-off. On the 97 instances completed by both LocalizedReduce and exhaustive one-step rollout, the authors report approximately 98% lower total runtime, with a 1.3-percentage-point decrease in the mean reference-value ratio. This provides concrete evidence that the proposed candidate restriction can substantially reduce rollout costs while retaining much of its empirical solution quality.

Critical weaknesses
  1. Limited methodological novelty and insufficient evidence of improvements over existing heuristics. GenReduce uses an established LLM-guided program search framework to discover a heuristic deletion rule. However, the prompt already suggests degree-based features and a rank-then-delete strategy, and the final rule is simply a weighted combination of local graph statistics that removes approximately 14% of vertices. Without comparisons against simple hand-designed or tuned pruning rules, the benefit of LLM-based discovery remains unclear. LocalizedReduce also has limited algorithmic novelty. Its central idea of restricting candidates to the closed neighborhood of a minimum-degree vertex is already established in classical MIS branching algorithms (Kratsch, Branching Algorithms, 2009). Evaluating candidate decisions through heuristic completion follows the standard rollout framework (Bertsekas et al., Rollout Algorithms for Combinatorial Optimization, 1997). Related MIS-specific heuristics have also been studied (Alidaee et al., Simple and Fast Surrogate Constraint Heuristics for the Maximum Independent Set Problem, 2008). The proposed method therefore appears to combine established techniques, and the paper does not sufficiently clarify its incremental algorithmic contribution or compare against closely related MIS heuristics. CacheReduce further extends the same framework with weighted-frequency scoring, fixed thresholds, and fallback lookahead. Its incremental benefit is relatively modest, and the lack of simple cache-policy ablations makes its independent contribution difficult to assess.

  2. The experimental evidence does not sufficiently support the claimed computational benefits. Figure 2 emphasizes that traditional exact reduction rules are 12.28× and 24.88× slower than the baseline. However, their actual average runtimes are only 3.05 and 6.52 seconds, respectively, compared with approximately 1,945 seconds for Gurobi. These differences are unlikely to constitute a major computational bottleneck, and the paper does not demonstrate otherwise. Moreover, only seven individual reduction rules are evaluated, rather than a complete exact-reduction pipeline. Figure 4 reports an increase in optimality certification from 52.5% to 78.2%. However, the higher rate applies to the reduced graphs, not the original problems. Removing vertices naturally makes many instances easier to solve, but this does not demonstrate that GenReduce is more effective than simple pruning strategies. Furthermore, 15.8% of instances retain less than 80% of the reference solution value. Without comparisons against simple pruning baselines under matched budgets, the claimed benefits remain insufficiently supported.

Questions for authors

see weakness

5 comments
AuthorsOpenReview ↗

[Authors Response (1/2)]

We thank the reviewer for recognizing our work and the effort invested. Although the review's central focus is not immediately clear to us, as its concerns span many aspects of the paper, we have addressed each of them carefully below. We sincerely invite the reviewer to further discuss the paper and we expect to resolve the reviewer's concerns.

On the first point, the reviewer asks what our methods add beyond established reduction techniques. Our methods address a specific limitation of exact reductions (kernelization) for NP-hard problems. Kernelization shrinks an instance while preserving optimality, so that an exact solver can work on a smaller size. However, each exact rule removes vertices only when a particular local structure appears in the graph. On our hard benchmark, none of the seven exact rules we tested removes a single vertex. We contribute a way to continue reducing such graphs after the exact rules stop working, while controlling both solution loss and computational cost.

For GenReduce, the reviewer raises two concerns: that the prompt already specifies much of the rule, and that the LLM rule is simple. On the first concern, the prompt's guidance is a deliberate part of the method. It suggests candidate graph features, asks the LLM to rank vertices for removal, and sets runtime requirements. These instructions define the search space for LLM. They leave open the scoring formula and the fraction of vertices to remove, and the LLM must determine both. We improve each proposed rule on training graphs, select one based on shrinkage ratio, solution quality, and runtime, and apply it unchanged to the test set. On the second concern, simplicity is a requirement for preprocessing, which must cost far less than the solver that follows it. The LLM aims to find which simple rule performs best on these measures, and this can only be learned by testing candidates. The simplicity of the selected rule therefore does not reduce the value of the search that found it.

LocalizedReduce differs from standard rollout in both purpose and cost. Standard rollout builds a solution: at every step it runs a heuristic from each remaining vertex and keeps the best move, which is expensive. LocalizedReduce instead uses rollout to reduce the graph. It compares several rollouts to find consensus, meaning agreement on which vertices to include or discard, and removes vertices accordingly. A single heuristic run produces only one solution, so it cannot show which choices good attempts agree on. To avoid the exhaustive cost of standard rollout, we restrict trial starts to a minimum-degree vertex and its neighbors. Rollout supplies the evidence, and the neighborhood restriction keeps that evidence cheap to obtain. Table 2 isolates the effect of this restriction. Compared with exhaustive rollout, on the 97 instances that both variants complete, it reduces total runtime by 98% at a cost of 1.3 percentage points in mean reference-value ratio.

CacheReduce addresses a cost that remains in LocalizedReduce. In LocalizedReduce, the trial solutions produced by rollouts serve as evidence. The consensus among these solutions, meaning their agreement on which vertices to include or discard, then determines each reduction. LocalizedReduce collects this evidence anew at every step by running fresh rollouts, even though each round of rollouts is limited to a small neighborhood. CacheReduce instead stores the trial solutions from earlier steps and reuses them as evidence in later steps. At each step, its LLM-learned policy uses this stored evidence to decide whether to include a vertex, discard a vertex, or request fresh trials. The saving comes from the steps where the stored evidence is enough, because CacheReduce runs no rollouts at those steps. Our contribution is this policy, which decides when stored evidence is enough and when new evidence is needed as the graph shrinks. We measure the improvement against LocalizedReduce, a baseline that already lowers rollout cost through localization. Even against this baseline, CacheReduce cuts mean runtime by about 20% more, at a cost of 0.6 percentage points in mean reference-value ratio (Table 1).

AuthorsOpenReview ↗

[Authors Response (2/2)]

On the second point, the reviewer questions whether our experiments support the claimed computational benefits. Our experiments support two claims. First, on our hard benchmark, the standard exact reductions remove no vertices. Second, GenReduce shrinks these graphs, so more instances can be solved to optimality at a controlled cost in solution quality. The first claim rests on whether the exact rules fire. We apply each of the seven rules exhaustively to a fixed point, and none removes any vertex on the 101 instances (Figure 2, Table 6). Since no rule changes the graph, a pipeline combining these rules also leaves every graph unchanged.

Even when the exact rules remove nothing, they still spend time certifying that no reduction applies. Without this check, there is no way to know whether a rule will eventually fire, so this cost is the price of using exact rules. It should be compared with other reduction methods rather than with Gurobi: UNCONFINED takes 6.52 s on average, about 12 times the full runtime of Reducing-Peeling (Table 1). The second claim reflects a deliberate trade-off. GenReduce is a heuristic reduction, so it gives up guaranteed optimality in exchange for shrinking graphs that exact rules cannot. Figures 4b and 4a measure the two sides of this trade-off under the same one-hour Gurobi budget, and they answer two different questions. Figure 4b asks whether the reduction makes the graphs easier to solve. GenReduce shrinks hard graphs to a size that Gurobi can handle: Gurobi proves optimality on 78.2% of the reduced graphs, compared with 52.5% of the original graphs. As the reviewer notes, these optimality proofs apply to the reduced graphs. This is intended, because Figure 4b measures only how much easier the reduction makes each instance for the solver. Since GenReduce is a heuristic reduction, an optimal solution on the reduced graph need not be optimal for the original graph. Figure 4a then answers the second question: how much solution quality the reduction costs on the original problem. On most graphs, this cost is small. The solution recovered from the reduced graph keeps a median of 97.7% of the reference value, and 77.2% of instances keep at least 90%. The 15.8% of instances below 80% are part of this reported cost. On seven instances, the recovered solution is even better than the one Gurobi finds on the original graph within the full hour.

For baselines, we follow standard practice in kernelization and compare GenReduce with the predominant exact reduction rules for MIS. For reduce-as-solve, we also compare with Reducing-Peeling, an established heuristic reduction that removes high-degree vertices once exact rules stall (Table 1). Our contribution in this part is to show that reduction can continue where exact rules stall.

Additionally, we applied our methods for another problem in the public comment. We hope this effort, together with our explanation, can motivate the reviewer to reconsider the evaluation, and we would be happy to discuss further.

Thank you for the clarifications and additional experiments. I acknowledge the useful runtime improvements.

However, my main concern about the incremental contribution remains. GenReduce follows an established FunSearch-style framework, but its advantage over simple pruning rules is not sufficiently demonstrated. Similarly, CacheReduce lacks comparisons with simpler caching policies to establish the value of its specific design.

While the additional results strengthen the evaluation, they do not fully resolve these concerns. I therefore maintain my rating of 2.

Reviewer_5tFFOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary
  • The authors propose using language models to generate reduction rules quickly. These rules can be cached and are generated offline on small synthetic graphs and applied to larger instances without further LLM calls. Specifically, they look at heuristic reduction as a scalable competition to exact kernalization.
  • They propose two types of methods - a reduce-then-solve paradigm following classic preprocessing pipelines and a reduce-as-solve paradigm that uses repeated heuristic searches when structural certificates are unavailable.
Critical strengths
  • Well written overall, the experiments seem sound and I like how clear the authors were from the get go that what they do will break guarantees of optimality for measurable performance gains.
Critical weaknesses

Not a critical weakness, but a weakness nonetheless:

  • While this looks like an interesting idea, LocalizedReduce and CachReduce - two methods that presumably do a lot of the heavy lifting in cases when reduction is not easy, are tied very closely to MIS. How would such a method be applied to other CO problem types? Would it even be applicable or this is tied down to MIS only? A small trial experiment for other types of problems like set cover or combinatorial auctions would have been interesting.
Questions for authors
  • There is a clear relationship in the results and the density of the problem - from prior experience, as density goes down, heuristics and ML methods suffer. Looks like this is the case here too - I'd have liked to see a discussion on this - atleast in the appendix.

This one is just for my curiosity:

  • Can GenReduce be used alongside Localized/CacheReduce during" the solving process? That is, during the solve process, take the intermediate solution, and apply CacheReduce? Alternatively, apply GenReduce multiple times to the same instance but at different timesteps during the optimization process?
2 comments
AuthorsOpenReview ↗

[Authors Response]

We appreciate the reviewer's time and effort in providing this insightful feedback.

On "Critical Weaknesses": The design of our methods can be reused for other combinatorial optimization problems. However, the specific experiments that our methods produce remain specific for MIS. We would like to clarify why we chose MIS. The choice does not reflect a limitation of our method. Kernelization is the data reduction technique we study from parameterized algorithm research, and it has been studied extensively for MIS. MIS has one of the richest collections of expert-designed reduction rules with theoretical guarantees, whereas other problems have fewer reduction rules that are useful in practice. We therefore started with MIS. Under our method design, we expect the same experimental pattern to carry over to other problems. Doing so, however, requires selecting a problems and its practically useful reduction rules, which we see as the scope of a separate paper. Yet we still added a small quick trial as requested (Please check the comment for all.) with limited time and computing resource. We hope this consolidates the reviewer's positive standpoint.

On "Question on density": We agree with the reviewer's observation. We discuss it below and will add this discussion to the revised paper. Data reduction for NP-hard graph optimization problems aims to shrink an instance without losing its global optimal solutions, so that the problem can be solved faster. Reduction rules are typically designed by experts and come with theoretical guarantees. However, for NP-hard optimization problems, there is always a trade-off between exactness and practical usefulness. More powerful reduction rules often look for more complex structures, such as a diamond-shaped subgraph. To apply such a rule, we must first search the graph for its structure, and on many instances, that structure does not exist. We therefore design heuristic and ML-based methods that reduce instances empirically. In doing so, we give up a small amount of accuracy to enable practical reduction. This also explains why our methods appear weaker on sparser graphs. On sparser graphs, the structures that exact rules require appear maybe more often and are also cheaper to find, so exact rules work maybe well there. Even so, our methods remain competitive on these graphs. However, they are still heuristics, and some loss of solution quality is inherent to heuristic methods. As instances become denser and harder to solve, these structures become very expensive to find, and running the exact rules soon become unworthy. Because the procedure is: reduce the instance if possible -> solve the NP-hard graph problems. If the reduction step itself is already very expensive, is it worth paying that cost? We hope this clarifies our perspective.

In response to the "Curiosity": Yes, the two can be combined during problem-solving process. However, combining them would make it harder to see how each component contributes. In this first attempt, we aim to show clearly the contribution of each method on its own. The suggested integration is a natural and fairly direct extension, but here we keep the focus on the proposed methods themselves.

We hope these responses address the reviewer's concerns.

Thank you for addressing my questions as well as the set cover experiment!

Comments on the paper

2 comments
AuthorsOpenReview ↗

[To All (1/2)]

We thank all reviewers for the thoughtful feedback. Kernelization for NP-hard graph problems is hard. Each reduction rule needs expert design and a proof that it keeps an optimal solution, and it acts only when a specific structure appears. Checking these rules costs time whether or not they remove anything, and usually, the time cost is high. On our hard MIS benchmark, the seven standard rules remove no vertices at all, that means, we paid the time cost for nothing. We continue reduction beyond this point in two settings, trading a little exactness for further reduction and using the LLM to design the algorithmic components of reduction.

In reduce-then-solve, GenReduce shrinks the graph before an exact solver runs. It uses an LLM-designed reduction rule, selected jointly for shrinkage, solution quality, and runtime. In reduce-as-solve, reduction continues until the instance is solved. At each step, we look ahead by greedily completing several full solutions from different starting vertices, and we commit only the decisions on which these solutions agree. We build two methods on this idea, each one cheaper than the one before.

LocalizedReduce makes this look-ahead fast without losing its ability to reduce, because it looks ahead only from a minimum-degree vertex and its neighbors. At every step, it runs these look-aheads again and commits the decisions on which they agree.

CacheReduce cuts the cost further by reusing the solutions completed in earlier steps, which remain informative as the graph shrinks. We use the LLM to design the policy that decides when these stored solutions can be trusted, because generally, this demands expert experience or data pattern. It commits a decision when the stored solutions clearly support it and looks ahead again only when they share no consensus. This judgment is hard to design by hand, because acting too early loses solution quality, and acting too late saves no time.

After GenReduce, Gurobi proves optimality on 78.2% of the reduced graphs, up from 52.5% of the original graphs, and the recovered solutions keep a median of 97.7% of the reference value. LocalizedReduce cuts runtime by 98% compared with looking ahead from every vertex, and CacheReduce cuts a further 20% compared with LocalizedReduce, both at a small cost in solution quality.

For all, with this busy rebuttal time and limited resource, we present this small trial experiments in response to the question on "other problems", despite it is not our current research focus. We will add the full details after reviewing. We truly hope this effort can motivate you to reconsider the evaluation and a potential score upgrade.

Trial experiment on set cover. As the reviewer suggested, we ran a small trial on set cover. We used 30 OR-Library instances (classes C, D, NRE, NRF, NRG, NRH) in their unit cost versions. All methods run single-threaded. The reference OPT_ref is the best cover Gurobi finds within 1 hour, and the ratio is the size of the OPT_ref cover divided by the size of the method's cover, so higher is better. Gurobi proves optimality on none of these instances within the hour, so ratios above 1.0 occur when a method finds a smaller cover than Gurobi's timeout incumbent.

Table 1. Firing rate of the exact set cover reduction rules on the 30 test instances. The standard data reduction rules for set cover [1], each applied alone exhaustively. Set domination applies only on the five instances, removing at most 42 of their 4,000 sets.

RuleFire (%)
Forced set0.0 (0 / 30)
Set domination16.7 (5 / 30)
Element domination0.0 (0 / 30)

Table 2. GenReduce (reduce-then-solve).

GenReduce + Gurobi (1 h)
Sets removed by the rule30%
Median ratio1.000
Mean ratio0.999
Min ratio0.917
# ratio ≥ 0.930 / 30
# ratio > 1.08 / 30

Table 3. Reduce-as-solve. Time is in seconds.

MethodMean ratioMin ratio# ratio = 1.0# ratio > 1.0Mean timeMedian timeMax time
Gurobi (1 h, OPT_ref)1.000–––3600.173600.173600.17
Greedy (Chvátal)1.0630.9576 / 3020 / 300.050.050.11
Exh-1L1.1311.0001 / 3029 / 30213.8756.62837.16
LocalizedReduce (ours)1.1181.0003 / 3027 / 306.714.2519.30
CacheReduce (ours)1.1161.0003 / 3027 / 303.502.4913.10
AuthorsOpenReview ↗

[To All (2/2)]

Results. The results on set cover follow the same pattern as our main experiments.

  • Exact reduction rules rarely apply on these instances: forced set and element domination never fire, and set domination fires on only 5 of the 30 instances. We note that exact rules fire more often on set cover than on MIS, which comes from the structure of the problem itself. Even so, they leave most instances unreduced.
  • GenReduce removes 30% of the sets, and the reduced instances keep solution quality: the median ratio is 1.000, all 30 instances reach a ratio of at least 0.9, and 8 instances exceed the reference.
  • LocalizedReduce reduces mean runtime by 96.9% compared with Exh-1L, with a mean per-instance ratio change of −1.33%. It is faster on all 30 instances, with a median per-instance speedup of 22.3× (other metrics include: geometric mean 21.6×, max 76.3×).
  • CacheReduce cuts mean runtime by a further 47.8% compared with LocalizedReduce, with a mean per-instance ratio change of −0.12% and a median per-instance speedup of 1.9× (other metrics include: geometric mean 2.2×, max 5.7×).
  • Both of our reduce-as-solve methods match or exceed Gurobi's 1-hour reference on every instance, within seconds.

[1] Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press 2006.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.