PaperlayerView exact revision on arXiv

Source-linked AI summary

Nominate-then-Adjudicate: LLM-Assisted One-Pass and Per-Instance MIP Solver Tuning

Yifan Zhao, Qianyang Zhao, Xinyu Guan, Kai Wei, Yuming Deng

arXiv:2610.29391v1cs.LG

TL;DR

Per-instance MIP configuration is difficult because solver parameters vary in effectiveness across instances, while a fixed feature map can erase structural distinctions. The paper nominates candidates from a fixed portfolio and uses a foundation model to adjudicate them in one call without an inference-time solver call. The complete adjudicator records 538 wins and 185 losses against the top nominee for comparisons above the 20% practical-difference threshold.

  • Problem

    Solver parameters can have different best settings across instances, while feature-only selectors may lose distinctions between structurally different instances.

    Source: §I · p. 1

  • Method

    A learned performance model nominates a shortlist from a fixed portfolio, and a foundation model adjudicates using compressed matrix and textual-memory inputs in one call without online solver work.

    Source: §IV · p. 3, C. Step 3: Nomination by an EPM · p. 4

  • Results

    538 wins and 185 losses against the top nominee were recorded for comparisons exceeding the 20% practical-difference threshold.

    Source: §VI · p. 10

  • Takeaways & Limitations

    The complete adjudicator improves over feature-only top-1 selection and leads the best-performing evaluated per-instance baseline in the matched study.

    Source: §VI · p. 10

    Near-universal coverage by the sampled portfolio remains untested on the evaluated families.

    Source: C. Ablations · p. 7, §VI · p. 10

Abstract

from arXiv · show

Mixed-integer programming solvers expose hundreds or even thousands of parameters whose best setting varies per instance, yet per-instance search is prohibitively expensive. We frame this as configuration for heterogeneous Big Data optimization workloads and propose a nominate-then-adjudicate pipeline built around two design choices. First, a fixed portfolio is sampled once and reused across instances, removing per-instance configuration search at inference; on the evaluated families, the resulting shortlist retains substantial oracle headroom, making selection within it the empirical focus. Second, the fixed 20-feature representation can map structurally different instances to the same vector, preventing a feature-only selector from distinguishing them even when they prefer different configurations. The foundation model receives no task-specific weight updates, and selection is one-pass: one model call and no solver calls at inference. The study represents structural Variety through distinct formulation families and decision Value through solver-performance outcomes; the one-call, zero-solve protocol specifies the decision interface and leaves end-to-end latency unmeasured. Among comparisons exceeding a 20% practical-difference threshold, the complete adjudicator records 538 wins and 185 losses against the top nominee, while its win rate against the default rises from 84.9% to 90.2%. Against per-instance configuration baselines under a matched one-pass protocol it leads the cluster-level methods and the best-performing evaluated per-instance baseline, ISAC+.

I. INTRODUCTION

Per-instance MIP tuning must choose among configurations whose best settings vary by instance, while feature-only selection can miss structural distinctions. The paper proposes a fixed-portfolio nomination stage followed by structure-aware adjudication in one model call and without solver calls at inference.

I. INTRODUCTION

  • Thousands of solver parameters can vary in effectiveness across instances, motivating per-instance configuration for large-scale combinatorial decision-making.Routing, assignment, and supply-chain optimization are cited as MIP applications.Source: §I · p. 1
  • The complete system combines a learned performance model over a fixed portfolio with foundation-model adjudication using matrix and textual-memory inputs, without weight updates or solver calls at inference.The adjudicator makes a bounded choice among measured candidates; the foundation model does not generate parameter values.Source: §I · pp. 1–2
  • A fixed aggregate feature map can give structurally different instances the same vector, so a feature-only selector may be unable to choose their different preferred configurations.The paper uses an independent-set/vertex-cover pair to illustrate a collision under its 20-feature representation.Source: §I · pp. 1–2
  • The pipeline nominates the top k configurations from a reusable portfolio, then adjudicates them using a compressed constraint matrix and textual skill memory.The instance is read through distinct feature and matrix channels; portfolio, EPM, and skill memory are built offline.Source: §I · p. 2, Figure 1 · p. 2
  • The evaluation treats Variety as cross-family structural heterogeneity and Value as solver performance, while one model call and zero solver calls define the decision interface.End-to-end latency is not measured.Source: §I · pp. 1–2

II. RELATED WORK

Prior configuration methods differ in decision granularity, inference-time solver work, and whether the selector is fitted. The paper locates its contribution in per-instance, solver-free adjudication with structural and textual information.

a) Granularity

  • Classical configurators tune distribution-wide settings, while per-instance methods select configurations using clusters, pooled portfolios, or learned mappings.The related work includes SMAC, irace, GGA, ISAC, ISAC+, and Hydra-MIP.Source: §II · p. 2

b) Solver calls at inference

  • Methods that use solver probes, close a configuration-selection loop, or run a model during search incur solver work at decision time.The passage also describes language-model approaches that evaluate candidates through solver runs or repeated optimization.Source: §II · p. 2

c) Whether a selector is fitted

  • The paper keeps foundation-model weights fixed, using an offline-trained EPM and textual experience tied to measured selection outcomes instead.The related-work taxonomy distinguishes this from fine-tuned models and selectors built from model embeddings.Source: §II · pp. 2–3

III. PRELIMINARIES

The paper defines a bounded score for comparing configurations with the default and describes an inference pipeline that selects from a fixed portfolio without running a solver online.

III. PRELIMINARIES

  • The system represents an instance as a MIP and a configuration as values for 30 SCIP parameters, whose combined space has approximately 7.9 × 10^18 possibilities.Solve time is measured under a fixed time limit, and speedup is relative to the default configuration.Source: §III · p. 3
  • The score in [-1, 1] compares a configuration with the default by lexicographic priority: feasibility first, then proven optimality, then performance.Timeouts are scored rather than dropped; the bounded score is averaged, with shifted geometric mean speedup reported alongside it.Source: §III · p. 3

IV. METHOD

  • Inference extracts features, scores a fixed numbered portfolio with an EPM, and makes one language-model call to select an index from the top k, with no solver run.Portfolio construction, EPM fitting, and skill-memory revision occur offline.Source: §IV · p. 3

A. Step 1: Static Features

The method uses cheap static aggregates for nomination and a reusable random portfolio of measured configurations, avoiding solver-dependent features and per-instance portfolio construction at inference.

A. Step 1: Static Features

  • The 20 static features are cheap, solver-agnostic, solve-independent, and permutation-invariant aggregates of the coefficient matrix.The method excludes root-relaxation features because obtaining them requires running the solver at inference.Source: A. Step 1: Static Features · p. 3

B. Step 2: A Fixed Random Portfolio

  • The tuned space contains 30 SCIP parameters with finite candidate lists, selected by consensus from a much larger parameter listing.The passage says the 30 parameters span presolving, separation, cut selection, primal heuristics, branching, and conflict analysis.Source: B. Step 2: A Fixed Random Portfolio · p. 3
  • The method samples 1,000 configurations once and reuses that fixed portfolio across instances, without a guarantee of near-optimal coverage.The pool is built from a seed-disjoint batch and its fixed numbering keeps rules and accumulated experience attached to configurations.Source: B. Step 2: A Fixed Random Portfolio · pp. 3–4

C. Step 3: Nomination by an EPM

A learned performance model nominates a fixed portfolio shortlist, then a foundation model selects from it using both aggregate features and a compressed matrix representation. The adjudicator makes a bounded one-call choice without solver calls or foundation-model weight updates.

C. Step 3: Nomination by an EPM

  • The EPM scores every instance–configuration pair by predicted log-speedup and forwards the top k from the fixed portfolio, using k = 10 in the study.It retains configurations slower than the default as negative training targets.Source: C. Step 3: Nomination by an EPM · p. 4

D. Step 4: Foundation-Model Adjudication without Weight Updates

  • The adjudicator makes one foundation-model call to return a shortlist index and is the only component that reads the compressed matrix rendering.The nominator uses aggregate features; the adjudicator also receives the structural channel.Source: D. Step 4: Foundation-Model… · p. 4
  • Identical 20-feature vectors can conceal instances that prefer different configurations, a limitation specific to the chosen representation.The independent-set and vertex-cover pair demonstrates one such collision; alternative representations may retain the distinction.Source: D. Step 4: Foundation-Model… · p. 4
  • The adjudicator receives a compressed matrix rendering, features, default, candidates, and skill memory, then returns a bounded shortlist choice rather than inventing parameter values.A parse failure falls back to the top nominee.Source: D. Step 4: Foundation-Model… · p. 4
  • The matrix rendering groups constraints and preserves their senses and bounds, while summarizing long objectives by coefficient range when needed.The rendering includes variable-type counts and uses structural grouping out of distribution.Source: D. Step 4: Foundation-Model… · p. 5
  • The prompt prioritizes avoiding candidates plausibly slower than default and requires concrete experience-backed evidence before deviating from the top nominee.Choosing the top nominee incurs no additional solve because it is the solve the nominator would have made.Source: D. Step 4: Foundation-Model… · p. 5
  • A solved shortlist batch yields runtime and hindsight-winner profiles, rules, and a checklist for the textual skill memory while foundation-model weights stay fixed.Later rounds revise family-specific rules using measured outcomes; only the prompt changes.Source: D. Step 4: Foundation-Model… · p. 5

V. EXPERIMENTS

The experiments use seed-disjoint evaluation batches and a common solve and model-call protocol, with runtime comparisons filtered by a 20% practical-difference threshold.

A. Setup

  • Evaluation batches are seed-disjoint from pool-building and EPM-training batches, with serial single-threaded solves, a fixed solver seed, and a 10s wall-clock limit.Instances are selected so default solve time falls within 0.5–5s.Source: A. Setup · p. 5
  • Each instance is decided by one Qwen-Max call at temperature 0.1 with a 4096-token output budget, using the same model and settings for reported numbers unless stated otherwise.The model is accessed through an OpenAI-compatible API.Source: A. Setup · p. 5
  • Runtime pairs differing by less than 20% are counted as tied, and the threshold is not treated as evidence about measurement variance or statistical significance.A configuration that aborts the solver receives the timeout score; the reported occurrence was on a never-selected width-sweep member.Source: A. Setup · p. 5

B. Skill Iteration: Select the best k.

The width sweep selects k = 10 as the smallest tested shortlist width where the harvested fraction saturates, balancing headroom against increasing solve and prompt costs. Across refinement rounds, deviations become less frequent without losing precision, but family-level timeout hazards can make performance nonmonotone.

B. Skill Iteration: Select the best k

  • The five width runs each use ten refinement rounds on disjoint 160-instance batches, with each round refining from a fresh batch alone.Table III compares the widths on batches shared by all five runs.Source: B. Skill Iteration: Select the best k · p. 5, Table III · p. 6
  • 27.3%, 27.7% and 27.1% of headroom is harvested at k = 10, 15 and 20, respectively, so k = 10 is the smallest tested saturated width.Doubling width from 10 to 20 adds only +0.007 margin, while prompt-token and solve costs scale linearly with k.Source: B. Skill Iteration: Select the best k · pp. 5–6, Table III · p. 6, Figure 5 · p. 7
  • Across five width runs, deviation rates fall from the first five rounds to the last while precision rises or holds; at k = 10, rates are 73.4% →62.5% and precision is 70.3% →73.0%.Margin peaks around rounds three to five, when deviations remain frequent but are already precise, then eases as refinement favors caution.Source: B. Skill Iteration: Select the best k · p. 6, Figure 4 · p. 6
  • At k = 10, cutting stock swings from +0.091 in round two to −0.177 in round six as timeouts migrate between configurations, leaving family-level risk unresolved by per-identifier vetoes.The skill is frozen at the best mature round selected on a held-out batch.Source: B. Skill Iteration: Select the best k · p. 6
  • Deviation rates should be compared within a fixed k, because widening the shortlist mechanically raises the rate even for a perfectly calibrated selector.The reported rate rises from 49% to 71% across widths.Source: B. Skill Iteration: Select the best k · p. 7

C. Ablations

The ablations assess selection within a fixed shortlist and show that the complete adjudicator bundle beats feature-only top-1 selection. Gains vary by family, with coverage-limited and saturated families offering less improvement.

C. Ablations

  • The same ten-nominee shortlist scores 0.556 under an oracle versus 0.377 for the top nominee, leaving substantial selection headroom while portfolio coverage remains untested.Nominee sets are family-structured, with mean Jaccard overlap 0.518 within families versus 0.090 across them.Source: C. Ablations · p. 7
  • The complete adjudicator beats the top nominee more often than it loses across all ten batches, while harvesting only part of the oracle headroom.The comparison fixes ten nominees, instances and measured outcomes; matrix, skill memory and model contributions are not individually identified.Source: C. Ablations · p. 7, Table IV · p. 7
  • Fourteen of sixteen families are positive on average and eight in every round; independent set is strongest, while facility location and cutting stock are negative.Set covering and job scheduling are saturated, with nearly interchangeable nominees and little room to improve on the top nominee.Source: C. Ablations · p. 7
  • Independent set and vertex cover align with the feature-collision example, consistent with matrix information helping where aggregate features omit structure, though a family-wide causal mechanism is unmeasured.Vertex cover is positive in nine of ten rounds; the collision construction establishes only one IS/VC pair.Source: C. Ablations · p. 7

D. Baseline Comparison

Under a matched one-pass protocol, the complete adjudicator leads the evaluated per-instance baselines, including ISAC+, though the bounded-score margin is small. Results vary across families: cluster-level methods can concentrate many instances on one configuration, while headroom does not consistently predict gains.

D. Baseline Comparison

  • The comparison uses 400 held-out instances across four Ecole genera, with independent offline artifacts and a shared instance-independent portfolio and protocol.The baseline ladder compares complete systems, not components; ISAC+ is the closest baseline, but portfolio construction and selector design still differ.Source: D. Baseline Comparison · pp. 7–8
  • The ISAC+ gap is +0.19 in SGM speedup (4.48 vs. 4.29) and +3.6 points of default wall-clock removed in uncompressed aggregates.The descriptive win–loss count above the 20% practical-difference threshold is 83:52, with no statistical-significance inference.Source: D. Baseline Comparison · p. 8
  • Ours leads every aggregate metric, with a +0.020 mean-score margin over ISAC+, the best-performing evaluated per-instance baseline.The comparison uses a matched one-pass protocol.Source: D. Baseline Comparison · p. 8, Table V · p. 9
  • Set covering is saturated at 0.031 headroom, while combinatorial auction retains 0.091 but converts little of it; headroom and runtime dispersion incompletely proxy discriminability.Disagreements favor the adjudicator only on facility location; on independent set, they cancel and configuration yields the least benefit.Source: D. Baseline Comparison · p. 9
  • At c = 4, ISAC+ROAR assigns 247 instances, including every independent-set and 95 of 100 combinatorial-auction instances, to one configuration.Combinatorial-auction scores are 0.252 for ISAC+ROAR at c = 4 and 0.463 for ISAC+SMAC at c = 8, against 0.564 for ours.Source: D. Baseline Comparison · p. 9

E. Transfer to Two MIPLIB Instances

The study tests bounded transfer on two feature-range-compatible, unlabeled MIPLIB 2017 instances, applying the systems unchanged. The adjudicator reaches each instance-specific target faster than the default and competitive ISAC-based methods, with rationales traceable to structural cues and recorded memory rules.

E. Transfer to Two MIPLIB Instances

  • The two unlabeled MIPLIB 2017 instances were selected because all 20 features lie within EPM training ranges, and no system was refit on them.The transfer test makes no statistical generalization claim and compares time to attainable instance-specific relative gaps.Source: E. Transfer to Two MIPLIB Instances · p. 9
  • On both instances, ours reaches the target faster than the default and all three competitive ISAC-based methods under the same transfer protocol, by about 2× on mas76 and 3× on 50v-10.Table VI reports wall-clock time to an instance-specific relative gap; lower is better.Source: E. Transfer to Two MIPLIB Instances · p. 9, Table VI · p. 9
  • For mas76, matrix cues map the instance to multidimensional knapsack and memory rules support selecting 48 and vetoing 33; for 50v-10, flow and capacity cues identify lot sizing and network design.The 50v-10 selection of 4 is tied to a core lot-sizing entry, while 0 is rejected under a network-design veto.Source: E. Transfer to Two MIPLIB Instances · p. 9
  • These cases support the narrow conclusion that experience distilled from synthetic classes can transfer to real, unlabeled models through structural reading rather than label matching.This conclusion is limited to the two evaluated cases.Source: E. Transfer to Two MIPLIB Instances · p. 9

VI. DISCUSSION AND CONCLUSION

The conclusion presents nominate-then-adjudicate as a one-pass, solver-free-at-inference architecture whose complete adjudicator outperforms the top nominee and leads evaluated per-instance baselines. Its evidence supports useful shortlist headroom on evaluated families, while broader coverage, deployment latency, and the necessity of a foundation model remain open.

VI. DISCUSSION AND CONCLUSION

  • The realized portfolio and EPM shortlist provide useful oracle headroom on evaluated families, but near-universal portfolio coverage remains untested.The proposed architecture combines fixed-portfolio nomination with semantic adjudication using matrix and memory inputs.Source: §VI · pp. 9–10
  • The one-call, zero-solve interface addresses the decision step, but volume scaling, distributed storage, streaming ingestion, and end-to-end latency remain unmeasured.Deployment accounting must include model-call, serialization, and solver-runtime costs.Source: §VI · p. 10
  • The evidence supports improvement over the specified feature-only top-1 selector, while the necessity or uniqueness of a foundation model remains open.A fair alternative comparison requires a dimension-agnostic architecture and matched supervision and training budgets.Source: §VI · p. 10
  • The stages can accommodate richer feature maps, parameter spaces, and other solvers, or cheap-model nomination followed by semantic tie-breaking.In the matched study, the complete bundle improves over feature-only top-1 selection and leads the best-performing evaluated per-instance baseline.Source: §VI · p. 10
  • Above the 20% practical-difference threshold, the complete adjudicator records 538 wins and 185 losses against the top nominee and leads evaluated per-instance baselines under a matched protocol.The system makes a bounded k-way choice in one frozen-model call, with no online solve or gradient update.Source: §VI · p. 10
Loading 2610.29391v1…