acceptodds
Under review as a conference paper at ICLR 2027

HINTS: GENERATING MIP WARM STARTS VIA AN EVOLVING EXPERIENCE LIBRARY

Abstract

Mixed-integer programming (MIP) solvers provide a general framework for combinatorial optimization, but their performance can depend heavily on how quickly they find a strong incumbent—the best feasible solution found so far. Specialized heuristics can produce good solutions quickly, yet they lack the systematic search and optimality guarantees of MIP solvers. We ask whether LLM-generated heuristics can combine these strengths by providing better starting solutions while leaving the solver unchanged. We propose **HINTS** (**H**euristic **IN**jection of **T**ight **S**tarts), which uses an LLM to generate a construction heuristic that produces a feasible MIP start for each instance. The start is injected into an unchanged solver, which then improves it through its native branch-and-bound search. To adapt construction strategies across heterogeneous instances, HINTS maintains a growing library of scoped experiences that record when a construction applies and how to build the corresponding start. Experiences are evaluated by the solver's progress after injection rather than by the heuristic solution alone. Across eight CO-Bench tasks and 1,611 instances, HINTS reduces the mean MIP gap across three solvers from 0.375 to 0.172 and consistently outperforms fixed textbook warm starts. With HINTS, OR-Tools further outperforms solver-only COPT and approaches solver-only Gurobi. These results show that LLM-generated warm starts can improve MIP solving without modifying the solver itself.

Primary area:
optimization
Keywords:
combinatorial optimization, warm start, large language models

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_vNSaOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents HINTS, an LLM-based framework for generating instance-adaptive MIP warm starts. The LLM generates executable construction heuristics whose solutions are injected into an unchanged MIP solver. A growing experience library records reusable construction strategies and their applicability, with experience selection and updates informed by subsequent solver performance. Experiments cover eight CO-Bench tasks and three solvers, comparing HINTS with solver-only runs and classical heuristic warm starts. The paper also includes component ablations and an evaluation that charges generation and heuristic execution against the same 600-second budget.

Critical strengths
  1. A practical interface between LLM-generated heuristics and established MIP solvers. HINTS supplies an external warm start while preserving the solver’s formulation and native search procedures. Evaluating constructions through downstream solver progress, rather than initial solution quality alone, aligns the framework with the eventual optimization objective.

  2. Useful empirical support for cross-instance experience reuse. The experiments show average improvements across several problem families and solvers, including under the supplementary accounting that includes generation time. The ablation provides evidence for the experience library’s contribution: removing it increases the average Gurobi gap from 0.121 to 0.185. This supports the value of accumulating construction experience beyond independently prompting an LLM for each instance.

Critical weaknesses
  1. The actual LLM overhead is insufficiently characterized. Appendix F is a useful inclusion and shows that benefits remain when generation and heuristic execution are charged against the time budget. However, the paper does not separately report latency distributions, call counts, token consumption, or monetary cost. It is also unclear whether the accounting includes applicability assessment, repair attempts, and amortized library updates. These details matter because the framework invokes the LLM for individual instances, and its practical advantage depends on the complete overhead.

  2. Robustness to instance ordering remains unclear. The experience library evolves using feedback from previously processed instances, but the evaluation uses only one instance ordering. The reported gains may therefore depend on how related instance regimes are arranged in the stream. Additional evidence across different orderings would help establish the reliability of the cross-instance adaptation.

Questions for authors
  1. Could you provide the complete prompt templates and call protocol, together with per-instance latency statistics, call counts, and token or monetary costs? Please clarify which stages are included in Appendix F, particularly applicability assessment, failed attempts and repairs, and library updates, and how shared update costs are amortized.

  2. How was the instance ordering determined? Do the main improvements, particularly the benefit of the experience library, remain stable across multiple randomized orderings?

6 comments
  1. Response to W1/Q1

W1:The actual LLM overhead is insufficiently characterized... Q1:Could you provide the complete prompt templates and call protocol, together with per-instance latency statistics, call counts, and token or monetary costs?lease clarify which stages are included in Appendix F, particularly applicability assessment, failed attempts and repairs, and library updates, and how shared update costs are amortized.*

Thank you for your questions.

(1) We added the full prompt templates to Appendix D of the revised manuscript.

(2) We added a detailed breakdown of LLM usage and costs to Appendix H, as shown in the table below.

Table 1. Mean LLM usage and estimated cost by task. Token counts include input and output tokens. LLM wait and preparation are measured per instance. All costs are in US dollars.

TaskLLM wait / instance (s)Preparation / instance (s)Calls / instanceTokens / instanceCost / instance (USD)Tokens / callCost / call (USD)Update API / wave (s)
Bin Packing13.0818.432.1259,2350.0024954,3460.0011747.26
CDD8.909.331.7925,9300.0014803,3100.0008266.29
Container Loading17.0422.452.1259,7200.0031194,5740.0014688.01
Flow Shop7.1012.051.7925,8110.0014313,2430.0007988.31
Job Shop14.1816.761.95810,0170.0027755,1150.0014177.22
Open Shop15.5716.802.12510,6890.0028815,0300.0013567.95
Set Cover13.2433.951.91713,7370.0030357,1670.0015847.02
TSP14.8581.832.12517,9980.0038888,4700.0018308.76
Overall12.9926.451.99510,3920.0026385,2100.0013227.60

For each instance, LLM wait time is the sum of the time spent on applicability assessment, heuristic code generation, and repair requests. Preparation time includes this wait and the time spent executing the heuristic code. We allocate an equal share of each wave’s library update call, token usage, and estimated cost to every instance in that wave. We compute per-call averages by dividing total token usage and estimated cost by the total number of calls. The API time for library updates averages less than one second per instance after amortization.

We estimated costs from recorded token usage using public off-peak rates of USD 0.003 per million cached input tokens, USD 0.15 per million uncached input tokens, and USD 0.60 per million output tokens.

(3) We expanded the description in Appendix I (formerly Appendix F). In the main experiments, each run uses a 600-second solver time limit. When warm-start preparation is counted toward the 600-second total budget, we first deduct the time spent on LLM-based applicability assessment, heuristic code generation, code execution, and any LLM repair calls. Code execution time includes failed attempts and reruns of repaired code.We also split the cost of updating the experience library evenly among the instances in each wave.The MIP solver then uses the remaining time.

  1. Response to W2/Q2

W2: Robustness to instance ordering remains unclear. Q2: How was the instance ordering determined? Do the main improvements, particularly the benefit of the experience library, remain stable across multiple randomized orderings?

Thank you for pointing this out. The original experiments followed the dataset’s default instance order. To assess HINTS’s robustness to changes in that order, we reran HINTS with Gurobi on all eight tasks, shuffling the instances within each task. The seeds in the table below specify the shuffle order for each rerun.

Table 2. HINTS performance with Gurobi under three online instance orders, with each metric shown as average gap and auc.

Instance orderBin (160)CDD (70)Cont. (762)Flow (120)Job (80)Open (60)Set (87)TSP (272)Average
Original order0.003 / 0.0150.066 / 0.0750.252 / 0.2620.113 / 0.1360.323 / 0.3860.158 / 0.1810.031 / 0.0450.021 / 0.0380.121 / 0.142
Seed 11090.003 / 0.0180.051 / 0.0580.250 / 0.2580.113 / 0.1360.313 / 0.3450.155 / 0.1770.033 / 0.0570.025 / 0.0440.118 / 0.137
Seed 12010.003 / 0.0190.050 / 0.0540.251 / 0.2600.113 / 0.1380.314 / 0.3480.156 / 0.1780.032 / 0.0480.022 / 0.0390.118 / 0.136

Shuffling the instances led to only modest changes in HINTS’s performance, with improvements on some tasks. Although HINTS showed some sensitivity to instance order, its gains persisted across the tested sequences. This suggests that the gains extend beyond the original ordering and supports the reliability of HINTS across different sequences of instances.

Apologies for the delayed reply; it’s been a busy week. Thank you for the detailed response and the additional experiments. The cost breakdown and shuffled-order results address my main concerns, and I continue to support acceptance.

I have one clarification about the new metaheuristic baseline. In the row labeled “Meta-Heuristic (30s) → Gurobi (600s),” is the 30-second preparation included in the 600 seconds, or is the total budget 630 seconds? If you already have results with both methods under the same 600-second total budget, I’d be interested to see them. The two average gaps are quite close, so this would help me interpret what is otherwise an encouraging comparison.

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

HINTS uses an LLM to generate heuristic programs based on instance features, construct feasible initial solutions, and pass them to an unchanged MIP solver for further optimization. Its core is an evolving experience library that records when to use which construction method and updates experiences based on solver progress after warm-start injection. Experiments across eight tasks and three solvers show that HINTS substantially reduces the mean terminal MIP gap under a fixed time limit.

Critical strengths

1, The standard MIP-start interface connects the LLM and the solver, exploiting the heuristic’s construction capability while retaining the solver’s search and optimality certification mechanisms.

2, The overall effectiveness and component contributions are supported by reasonably comprehensive evidence.

3, The ablation clearly shows that the experience library provides the main benefit, while routing yields an additional improvement.

Critical weaknesses

1, Warm starts, LLM-based heuristic generation, and experience routing all have precedents.

2, The experiments lack direct comparisons with the closest LLM–MIP methods or strong algorithm portfolios.

3, The solver trajectories show substantial improvement after warm-start injection, but do not establish that this improvement arises from the structure of the start.

Questions for authors

1, The ablation evaluates only the experience library as a whole and the router, without separately examining creation, patching, promotion, and retirement. Are the specific experience evolution rules necessary?

2, Easier instances naturally receive higher utility scores, could the feedback be confounded by instance difficulty?

4 comments
  1. Respone to W1

W1:Warm starts, LLM-based heuristic generation, and experience routing all have precedents.

Thank you for raising this question. Prior work has explored LLM-generated heuristics and experience reuse. HINTS brings these ideas together by using an evolving experience library to guide the LLM in constructing better warm starts, helping an unchanged MIP solver make faster progress. To our knowledge, HINTS is the first to study this combination in an online evaluation setting. We hope this approach motivates further work on using LLMs to accelerate combinatorial optimization.

  1. Response to W2

W2:The experiments lack direct comparisons with the closest LLM–MIP methods or strong algorithm portfolios.

Thank you for suggesting stronger baselines. Our experiments follow an online evaluation protocol. FunSearch and EoH use a train–test protocol, so adapting them directly to our setting would make it difficult to preserve how they evolve and evaluate heuristics. We also found few baselines in the recent literature designed for online evaluation of combinatorial optimization methods. We therefore added stronger, hand-designed metaheuristics as baselines.

We designed these metaheuristics to exploit the structure of each problem class and find high-quality feasible solutions within a limited time budget. For each class, we chose an established search framework and tailored its search operators to the solution representation, constraints, and objective.

For example, In one-dimensional bin packing, freeing a bin often requires moving several items. We use variable neighborhood search to repack groups of bins and subset-sum dynamic programming to fill spare capacity. Each algorithm quickly builds a feasible solution for the current instance and improves it within the time budget, making it suitable for online evaluation. Appendix G describes the metaheuristics for all eight tasks.

We added results for two settings: a standalone metaheuristic run with a 600-second budget, and a 30-second metaheuristic run whose best feasible solution is passed to Gurobi as a warm start. We chose 30 seconds to make the warm-start preparation budgets comparable, since HINTS spends about 26 seconds per instance on average on LLM calls and heuristic execution combined.

Table 1.Mean terminal gaps across eight tasks for solver-only Gurobi, standalone metaheuristics, and Gurobi with metaheuristic or HINTS warm starts.

MethodBin PackingCDDContainerFlow ShopJob ShopOpen ShopSet CoverTSPAverage
Gurobi Baseline0.0150.3590.4450.2250.4010.1820.0350.0580.215
Meta-Heuristic0.0220.0710.2570.1150.2900.1810.0490.0470.129
Meta-Heuristic → Gurobi0.0060.0660.2790.1140.3110.1600.0320.0190.123
Gurobi + HINTS0.0030.0660.2520.1130.3230.1580.0310.0210.121
Gurobi + HINTS (total 600s)0.0030.0670.2520.1130.3240.1590.0310.0270.122

As shown in the table, the standalone metaheuristics achieve lower final gaps than solver-only Gurobi on several tasks under the same 600-second budget. HINTS achieves a lower average final gap than the metaheuristics even when the budget includes LLM calls and heuristic execution (the last row). HINTS also outperforms Gurobi warm-started with a metaheuristic solution on several tasks. This comparison supports the effectiveness of HINTS when all methods are given the same time budget.

  1. Response to W3

W3:The solver trajectories show substantial improvement after warm-start injection, but do not establish that this improvement arises from the structure of the start.

Thank you for pointing this out. We understand your concern and agree that our discussion of this point needs to be more rigorous. Our current experiments provide insufficient evidence to attribute the gains specifically to the structure of the warm start. We will revise the manuscript to make this limitation explicit.

However, we have supplemented the main results table with an Initial row for each solver, as shown below. This row reports the gap of the injected warm start before solver search.

Table 2. Mean optimality gaps for HINTS before and after solver search, with solver-only terminal gaps as baselines.

SolverMethodBin PackingCDDContainerFlow ShopJob ShopOpen ShopSet CoverTSPAverage
GurobiBaseline0.0150.3590.4450.2250.4010.1820.0350.0580.215
GurobiInitial0.0110.0860.2990.1160.4490.2150.0930.1960.183
GurobiHINTS0.0030.0660.2520.1130.3230.1580.0310.0210.121
COPTBaseline0.2260.3610.7590.1070.6210.3780.0480.8170.415
COPTInitial0.2810.1140.2610.0990.3610.2390.1340.1790.209
COPTHINTS0.0640.0930.2390.0760.3310.2130.0440.0890.144
OR-ToolsBaseline0.1390.4560.9930.4130.9200.5800.1030.3440.494
OR-ToolsInitial0.2550.1560.3500.4060.5300.5140.1470.2440.325
OR-ToolsHINTS0.1040.0660.3100.3770.4980.4830.0990.0590.250

Part of HINTS’s gains comes from the quality of the heuristic solutions. This suggests that, during online evaluation, the LLM identified effective patterns for constructing better solutions. However, the heuristic solutions account for only part of the gains. The solvers’ continued search after warm-start injection contributes further improvements. For example, all three solvers substantially reduced the gap after injection on bin packing. Clear improvements are also evident on CDD, set cover, TSP, and job shop.

Even when the injected solution has a larger gap than the final solution from a solver-only run, continued search from that warm start can yield a smaller final gap. This additional improvement is the contribution of the solver’s search that we intended to highlight. We will revise the manuscript to make this point more rigorously.

  1. Responese to Q1

Q1:The ablation evaluates only the experience library as a whole and the router, without separately examining creation, patching, promotion, and retirement. Are the specific experience evolution rules necessary?

Thank you for pointing this out. To address this question, we added ablation experiments on four tasks: bin packing, open shop, common due-date scheduling (CDD), and TSP. We disabled createing,patching, promotion, and retirement one at a time to assess the effect of each component.Notably, disabling the experience creation component is equivalent to removing the experience library, so we cite the paper's w/o experience results here.

Table 3.Ablation of experience evolution rules. Each cell reports Gap / AUC. The numbers in parentheses are instance counts. Lower is better.

MethodBin Packing (160)Open Shop (60)CDD (70)TSP (272)
HINTS (ours)0.003 / 0.0150.158 / 0.1810.066 / 0.0750.021 / 0.038
w/o experience0.009 / 0.0400.167 / 0.2040.171 / 0.2010.095 / 0.124
w/o patch0.004 / 0.0220.159 / 0.1820.068 / 0.0800.054 / 0.076
w/o promotion0.004 / 0.0230.159 / 0.1820.067 / 0.0790.048 / 0.081
w/o retirement0.005 / 0.0230.160 / 0.1850.068 / 0.0810.040 / 0.058

As shown in the table, patching, promotion, and retirement have relatively small effects overall. Most of the gains come from reusing experience itself. Nevertheless, each of the three components contributes positively in our ablations.

The results show that experience creation contributes the most, while the other three components also play a role. Patching limits large, potentially destabilizing changes to existing experiences. The promotion mechanism gives newly created experiences enough opportunities to be tried early on, reducing the risk that a single experience dominates selection. Retirement appears to have the smallest effect, possibly because weaker experiences are gradually displaced by better-performing ones as the library evolves. Together, patching, promotion, and retirement primarily help keep experience accumulation stable.

  1. Responese to Q2

Q2:Easier instances naturally receive higher utility scores, could the feedback be confounded by instance difficulty?

Thank you for raising this important question. Easier instances generally yield better solver outcomes, although this pattern is not universal. They tend to have smaller search spaces and are therefore easier to solve to optimality. However, reaching optimality does not necessarily mean that the gap closed quickly throughout the run. Our utility includes the area under the gap curve (gap-AUC), which captures progress over the full time horizon. An easier instance can therefore receive a lower absolute utility than a harder one.

Comparing HINTS with the solver-only baseline on the same instances provides a complementary view of the gains.The learned experience library contains distinct construction strategies for different instance sizes.

We also computed HINTS’s gains over the solver-only baseline on four tasks, as shown below. We define hard instances as those for which the baseline solver failed to prove optimality within 100 seconds.

In contrast to the pattern in absolute utility, HINTS achieves greater relative improvements on hard instances. The baseline already performs well on easy instances, leaving little room for improvement, while its weaker performance on hard instances leaves more room for gains. These larger gains are an encouraging signal for accumulating and refining experience on hard instances. Strong performance on easy instances does not prevent HINTS from continuing to improve on hard ones.

Instance difficultyBin (160)CDD (70)Cont. (762)Flow (120)
Easy0.00380.00130.01110.0006
Hard0.01790.02270.22810.1792

Thanks for response, your rebuttal addressed most of my concerns.

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

The paper combines an LLM with solvers to solve MIPs: the LLM writes a small program to generate a valid solution for the given MIP, which the solver then uses as a warm start. HINTS keeps an experience library of short notes on combinatorial problems and obtained solutions. Each note records when a strategy applies and how to build the start. A small statistical router (a Thompson-sampling bandit) picks which note to use for each new instance or generates a fresh strategy if none fits. A strategy is judged by how well the solver does after receiving it, not by how good the starting solution looked on its own. Notes are created, refined, promoted, or retired based on those results.

Critical strengths

The positive points of the paper are: a) a practically relevant idea is explored; b) a starting warm solution is judged by the outcome rather than the initial gain; and c) it covers three solvers, eight problem families, and over 1,611 instances, and it compares against classic heuristics.

Critical weaknesses

The negative points of the paper are: a) the gains shrink when LLM time is counted, and the headline uses the friendlier setting; b) no train/test separation; c) no variance or repeated runs; d) baselines are weak; and e) cost of LLM not reported.

Questions for authors

The detailed comments are given below.

  1. The train/test separation is missing, as the library learns on the same instances it is scored on, using a single instance ordering.
  2. The statistics are not validated. Seeds aren’t set for COPT or SCIP, and results come from one run with one LLM (DeepSeek-V4-Flash). The main tables lack error bars, so small differences like the router’s gain are hard to trust.
  3. The baselines used for comparison are weak. Instead, the comparison should include other LLM heuristic-design methods (EoH, ReEvo, FunSearch) used as warm starts, stronger classical heuristics (local search, metaheuristics) given the same time, and learned warm-start methods like Neural Diving or Predict-and-Search.
  4. The paper doesn’t report the gain added purely by the LLM heuristic’s solution on its own. On some tasks, much of the gain in results may come from the heuristic rather than from the cooperation between the LLM and solver.
  5. The cost figures are not reported for LLM calls, tokens, or dollar cost per instance.
5 comments
  1. Response to W1

W1: The gains shrink when LLM time is counted, and the headline uses the friendlier setting.

Thank you for pointing this out. The headline reduction in mean terminal gap from 0.375 to 0.172 uses a 600-second solver time limit.

HINTS's gains decrease somewhat when LLM calls and heuristic execution count toward the same 600-second budget as solver search. However, HINTS still reduces the mean terminal gap relative to the solver-only baseline on all three solvers, from 0.215 to 0.122 on Gurobi, from 0.415 to 0.187 on COPT, and from 0.494 to 0.288 on OR-Tools. These results show that HINTS improves solver performance even after accounting for the time spent on LLM calls.

To further clarify where HINTS's gains come from,we revised the abstract to clarify that HINTS also improves performance when LLM calls and heuristic execution count toward the time budget.

  1. Response to W2/Q1

W2: no train/test separation; Q1: The train/test separation is missing, as the library learns on the same instances it is scored on, using a single instance ordering.

Thank you for raising this question. HINTS is evaluated online, so the protocol requires no separate training and test sets. Our experiments directly measure HINTS’s performance in this setting.

To assess how instance order affects performance, we ran additional experiments with Gurobi on all eight tasks, shuffling the instance order within each task. The results are shown below.

Table 1. HINTS performance with Gurobi under three online instance orders,with each metric shown as average gap and auc.

Instance orderBin (160)CDD (70)Cont. (762)Flow (120)Job (80)Open (60)Set (87)TSP (272)Average
Original order0.003 / 0.0150.066 / 0.0750.252 / 0.2620.113 / 0.1360.323 / 0.3860.158 / 0.1810.031 / 0.0450.021 / 0.0380.121 / 0.142
Seed 11090.003 / 0.0180.051 / 0.0580.250 / 0.2580.113 / 0.1360.313 / 0.3450.155 / 0.1770.033 / 0.0570.025 / 0.0440.118 / 0.137
Seed 12010.003 / 0.0190.050 / 0.0540.251 / 0.2600.113 / 0.1380.314 / 0.3480.156 / 0.1780.032 / 0.0480.022 / 0.0390.118 / 0.136

Shuffling the instance order led to modest changes in HINTS’s performance across the eight tasks, with improvements on some tasks. Overall performance remained stable across the tested orders, indicating that HINTS is robust to changes in instance order.

  1. Response to W3/Q2

W3: no variance or repeated runs; Q2:The main tables lack error bars, so small differences like the router’s gain are hard to trust. Seeds aren't set for COPT or SCIP,Results come from one run with one LLM (DeepSeek-V4-Flash).

Thank you for pointing this out. Please see the Table2.

• Due to time constraints, we were only able to estimate the mean and standard deviation of solver performance for Gurobi using results from three different seeds*. Table 2 reports the results. As shown in Table 2, HINTS's average performance varied little across the three Gurobi runs. HINTS still outperformed solver-only Gurobi, with a mean terminal gap of 0.1190 versus 0.215 and a mean gap-AUC of 0.1383 versus 0.268.We will extend the experiments and report the corresponding error bars in follow-up work.

• For COPT and OR-Tools , we used the default solver settings for COPT and OR-Tools and inadvertently omitted explicit seed settings. We will explicitly set the random seeds in follow-up experiments.

• Given the long solver runtimes, we commit to evaluating HINTS with additional LLM backbones in follow-up experiments.

Table 2. HINTS results from three Gurobi runs. Terminal gap and gap-AUC are reported as mean ± sample SD.

Metric (Mean ± SD)Bin (160)CDD (70)Cont. (762)Flow (120)Job (80)Open (60)Set (87)TSP (272)Average
Gap0.0030 ± 0.00000.0557 ± 0.00900.2510 ± 0.00100.1130 ± 0.00000.3167 ± 0.00550.1563 ± 0.00150.0320 ± 0.00100.0227 ± 0.00210.1190 ± 0.0017
AUC0.0173 ± 0.00210.0623 ± 0.01120.2600 ± 0.00200.1367 ± 0.00120.3597 ± 0.02290.1787 ± 0.00210.0500 ± 0.00620.0403 ± 0.00320.1383 ± 0.0032

* Wording revised on November 19, 2026.

  1. Response to W4/Q3

W4:baselines are weak; Q3: The baselines used for comparison are weak. Instead, the comparison should include other LLM heuristic-design methods (EoH, ReEvo, FunSearch) used as warm starts, stronger classical heuristics (local search, metaheuristics) given the same time, and learned warm-start methods like Neural Diving or Predict-and-Search.*

Thank you for your suggestion. Our experiments follow an online evaluation protocol. FunSearch and EoH use a train–test protocol, and adapting them directly to our setting would require changing key aspects of how they evolve and evaluate heuristics. Neural Diving and Predict-and-Search also require prior training.Our review of recent literature identified few combinatorial optimization baselines designed for this online setting.

We therefore added stronger metaheuristics as baselines.We designed these metaheuristics to exploit the structure of each problem class and find high-quality feasible solutions within a limited time budget. For each class, we chose an established search framework and tailored its search operators to the solution representation, constraints, and objective. For example, In one-dimensional bin packing, freeing a bin often requires moving several items. We use variable neighborhood search to repack groups of bins and subset-sum dynamic programming to fill spare capacity. Each algorithm quickly builds a feasible solution for the current instance and improves it within the time budget, making it suitable for online evaluation.Appendix G describes the algorithms for all eight tasks.

We added results for two settings: a standalone metaheuristic run with a 600-second budget, and a 30-second metaheuristic run whose best feasible solution is passed to Gurobi as a warm start. We chose 30 seconds to make the warm-start preparation budgets comparable, since HINTS spends about 26 seconds per instance on average on LLM calls and heuristic execution combined.

Table 3.Mean terminal gaps across eight tasks for solver-only Gurobi, standalone metaheuristics, and Gurobi with metaheuristic or HINTS warm starts.

MethodBin PackingCDDContainerFlow ShopJob ShopOpen ShopSet CoverTSPAverage
Gurobi Baseline0.0150.3590.4450.2250.4010.1820.0350.0580.215
Meta-Heuristic0.0220.0710.2570.1150.2900.1810.0490.0470.129
Meta-Heuristic (30s) → Gurobi (600s)0.0060.0660.2790.1140.3110.1600.0320.0190.123
Gurobi + HINTS0.0030.0660.2520.1130.3230.1580.0310.0210.121
Gurobi + HINTS (total 600s)0.0030.0670.2520.1130.3240.1590.0310.0270.122

As shown in the Table 3, the standalone metaheuristics achieve lower final gaps than solver-only Gurobi on several tasks under the same 600-second budget. HINTS achieves a lower average final gap than the metaheuristics even when the budget includes LLM calls and heuristic execution (the last row). On several tasks, HINTS also outperforms the baseline in which the solver continues its search from a metaheuristic solution.This comparison supports the effectiveness of HINTS when all methods are given the same time budget.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.