PaperlayerView exact revision on arXiv

Source-linked AI summary

Autoresearch in Mixed-Integer Linear and Nonlinear Programming

Yuwei Gu, Yaoxin Wu, Tong Guo, Wen Song, Zhiguang Cao

arXiv:2609.39360v1cs.AI

TL;DR

Autoresearch for NP-hard MILP and MINLP problems remains challenging because long research runs must manage competing ideas and experimental trajectories. AutoMIP couples a persistent idea pool with an algorithm tree to organize directions and reusable states. Across MIP and MINLP benchmarks, it reports higher success rates and more final-objective wins among methods, including new best solutions on 31 of 60 MIPLib instances.

  • Problem

    Autoresearch has focused mainly on machine learning and scientific discovery, while MILP and MINLP problems pose expertise-intensive design demands and require joint management of research directions and compatible executable states.

    Source: §1 · p. 1

  • Method

    AutoMIP couples a persistent pool of research directions with an algorithm tree of experimental states, selecting both what to explore and a compatible state from which to proceed.

    Source: §1 · p. 2

  • Results

    Across MIPLIB and MINLPLib, AutoMIP achieves earlier completion, higher success rates, and more final-objective wins among methods; it finds new best solutions for 31 of 60 MIPLib instances.

    Source: §1 · p. 2, §5 · p. 10

  • Takeaways & Limitations

    Ablations show that removing either the idea pool or algorithm tree reduces task completion and final-objective performance, indicating complementary roles in autoresearch.

    Source: §5 · p. 10

Abstract

from arXiv · show

Despite recent progress in autoresearch, applying it to practical operations research problems, typically formulated as NP-hard mixed-integer linear or nonlinear programs (MILPs or MINLPs), remains challenging because effective research requires systematically managing competing ideas and long-horizon experimental trajectories. We introduce AutoMIP, a reusable agent skill for organizing long-horizon autoresearch in mixed-integer programming through idea pooling and algorithm tree search. AutoMIP maintains a persistent pool of complementary candidate ideas while organizing executable experiments into an algorithm tree, enabling the agent to preserve unexplored hypotheses, refine promising algorithms, and switch to alternative methodological directions based on historical states. On MILP and MINLP benchmark cohorts, AutoMIP achieves the highest final success rates among the evaluated autoresearch frameworks. On MIPLib, AutoMIP discovers new best solutions for 31 of 60 instances, surpassing existing autoresearch frameworks. On MINLPLib, it achieves new best solutions for 52 of 60 instances. Ablation studies further demonstrate the complementary contributions of idea pooling and algorithm tree search, highlighting the importance of jointly maintaining diverse research ideas and structured experimental trajectories for long-horizon autoresearch.

1 INTRODUCTION

Autoresearch for NP-hard MILP and MINLP problems has received comparatively little attention, and effective optimization can require expertise-intensive, problem-specific design. AutoMIP jointly manages research directions and executable experimental states, and reports new best solutions across both benchmark cohorts.

  • Autoresearch has focused mainly on machine learning and scientific discovery, while NP-hard MILP and MINLP operations-research problems have received comparatively less attention.Source: §1 · p. 1
  • AutoMIP couples a persistent idea pool with an algorithm tree to manage diverse research directions and their experimental states throughout iterative research.The pool maintains directions, while the tree records experimental states, artifacts, and dependencies.Source: §1 · p. 2
  • When switching directions, AutoMIP selects a compatible historical state, restores its artifacts, and continues experimentation from that state.This supports reuse of accumulated knowledge across research directions.Source: §1 · p. 2
  • 31 of 60 MIPLib instances and 52 of 60 MINLPLib instances received new best solutions from AutoMIP under fixed computational budgets.The evaluation also reports outperforming existing autoresearch frameworks.Source: §1 · p. 2

2 RELATED WORK

Prior work reuses execution experience, structures alternative search paths, or allocates experiments among candidate designs. AutoMIP distinguishes itself by jointly managing untried hypotheses and the compatible executable states needed to pursue them.

  • Experience-reuse methods organize prior trajectories, reflections, code edits, or memories, while interleaving reasoning, action, and reflection lets agents adapt using execution feedback.Source: §2 · p. 2
  • Explicit search methods structure alternative paths, but long-running research also needs the code and artifacts associated with a selected path to resume it.Source: §2 · p. 3
  • Execution-guided evolution reuses evaluated implementations, whereas AutoMIP also preserves untested hypotheses and couples each direction to a compatible experimental state.Source: §2 · p. 3

3 AUTOMIP

AutoMIP organizes research around complementary directions and executable experimental states. Its layers generate candidate directions, select refinements or switches with suitable starting states, and verify experiments to update the exploration state.

3 AUTOMIP

  • AutoMIP couples a persistent idea pool of complementary research directions with an algorithm tree that preserves dependencies among directions and executable states.Together, they support deepening a productive direction, pursuing alternatives, and reusing earlier work.Source: §3 · p. 3

3.1 OVERVIEW

  • The overview divides AutoMIP into review-and-ideation, algorithm-search, and verification layers, with experimental feedback returning to the pool and tree.The workflow supports MILP and MINLP optimization.Source: §3.1 · p. 4, Figure 1 · p. 4

3.2 REVIEW-AND-IDEATION LAYER

  • PoolThink reviews task evidence, generates and screens complementary executable directions, and maintains them in a persistent idea pool separate from active search.Initial pools contain five to ten directions; at least five used or completed candidates may trigger a refresh that preserves history.Source: §3.2 · pp. 4–5

3.3 ALGORITHM SEARCH LAYER

  • The algorithm tree records executable states and their ancestry, while search either refines the current direction or selects an unused direction for a new branch.L edges denote local refinements and R edges denote direction switches.Source: §3.3 · pp. 5–6
  • Search switches directions when the current direction stagnates, its assumption is refuted, or no admissible refinement remains.Source: §3.3 · p. 6
  • For a direction switch, AutoMIP selects a compatible historical parent whose artifacts meet the direction’s starting requirements and registers the new experiment from that state.The selected parent determines the executable state of the experiment.Source: §3.3 · p. 6

3.4 VERIFICATION LAYER

  • Verification executes candidates from restored states, assesses feasibility, objective value, runtime, and task-specific criteria, then updates evidence, artifacts, pool status, and the search frontier.Research stops when the computational budget is exhausted or the stopping predicate is met.Source: §3.4 · p. 6

4 EXPERIMENTS

Experiments compare AutoMIP with four autoresearch baselines on Open and Hard MIPLib cohorts, MINLPLib, and a shared-instance ablation and cross-agent evaluation. AutoMIP achieves strong results across these settings, while the ablation results show benefits from the combined design.

4 EXPERIMENTS

  • The experiments assess incumbent improvement, fixed-target attainment, and nonlinear optimization under the specified time horizons, comparing AutoMIP with Codex, Loop, AutoEoH, and EvoX.The configurations ran on an Apple M4 Pro; Codex-based runs used GPT-5.5 and the Claude Code interface used Claude Sonnet 5.Source: §4 · p. 7

4.1 RESULTS ON MIPLIB

  • 31 of 60 Open instances reach new best-known solutions with AutoMIP, more than with any evaluated baseline.AutoMIP completes 24 tasks within 3,600 seconds, compared with 13 for Codex, 15 for Loop, 12 for AutoEoH, and 6 for EvoX.Source: §4.1 · p. 7, Table 1 · p. 8
  • On 28 jointly completed Open instances, AutoMIP is faster than Codex in 24 (85.7%), with an average speedup of ×2.18, and has the best objective on 18 instances.The best-objective counts are 5 for Codex, 4 for Loop, 3 for AutoEoH, and 1 for EvoX.Source: §4.1 · p. 7
  • On Hard, AutoMIP reaches 14 fixed targets within 600 seconds and 27 within 1,800 seconds, versus Codex’s 6 and 17.AutoMIP records 30 successes by the one-hour limit, compared with Codex’s 29; the cumulative-success figure tracks task completion over time.Source: §4.1 · pp. 7–8, Table 2 · p. 8, Figure 3 · p. 8

4.2 ABLATION STUDY

  • On 20 shared instances, AutoMIP completes 15 tasks (75.0%), versus 12 (60.0%) for NoPool and 10 (50.0%) for NoTree.Both ablations also have fewer best-final-objective instances, while the joint design completes 13 tasks in the first three hours and uses 1,070,460 tokens overall, versus 1,558,655 for NoPool and 1,683,805 for NoTree.Source: §4.2 · p. 9, Table 3 · p. 9

4.3 RESULTS ON MINLPLIB

  • AutoMIP completes 52 of 60 MINLPLib instances (86.7%), compared with 45 for Codex, and has the best objective on 16 instances versus Codex’s 11.Table 4 covers the common 60-instance nonlinear cohort.Source: §4.3 · p. 9, Table 4 · p. 10

4.4 RESEARCH AGENT COMPARISON

  • With AutoMIP, Codex completes 15 of 20 tasks and Claude Code completes 12; all 12 Claude Code successes are also completed under Codex.The final-objective comparison yields 9 wins for Codex versus 6 for Claude Code; the attempted DeepSeek Harness, Gemini CLI, and DeerFlow runs did not sustain the required twelve-hour runs and are excluded.Source: §4.4 · p. 9, Table 5 · p. 10

5 CONCLUSION

AutoMIP couples a persistent idea pool with an algorithm tree to manage diverse research directions and reusable experimental states. Its empirical scope is MIPLib and MINLPLib, while broader-domain extensions remain future work.

5 CONCLUSION

  • AutoMIP combines a persistent idea pool with an Algorithm Tree to manage research directions and reusable experimental states in MILP and MINLP autoresearch.The conclusion reports experiments on MIPLib and MINLPLib and identifies other research domains as an extension area requiring adjustments.Source: §5 · p. 10

A COMPLETE SKILL PROTOCOL

  • The appendix specifies a reusable skill protocol covering the primary task skill, PoolThink, algorithm-tree search, decision defaults, verification and recovery, and ablations.The protocol distinguishes experiment-selection and memory controls from the primary task skill's candidate construction, execution, and evaluation.Source: A COMPLETE SKILL PROTOCOL · p. 15

A.1 PRIMARY TASK SKILL: OPT

The skill defines instance-specific objectives and a reproducible task workflow, then maintains alternative research directions and experimental states. Search decisions distinguish refinements from evidence-supported switches, with verification and persistent state updates closing the loop.

A.1 PRIMARY TASK SKILL: OPT

  • For each MPS instance, the primary skill sets an objective, selects methods from instance structure, and imposes task-specific stopping and time budgets.Open tasks seek a feasible strict improvement; Hard or Solved tasks seek the known-best or optimal objective faster or more reproducibly, without requiring an optimality proof.Source: §A.1 · p. 15

A.2 POOL CONSTRUCTION AND LIFECYCLE

  • PoolThink maintains five to ten complementary research directions, screens redundant or infeasible proposals, and records their hypotheses, evidence, requirements, risks, and lifecycle status.Pool refresh follows at least five distinct candidates being used or completed and preserves pool history.Source: §A.2 · pp. 16–17

A.3 BRANCHING EXPLORATION TREE PROTOCOL

  • The multiway algorithm tree records research directions, observations, artifacts, and dependencies; L edges refine a direction, while R edges switch its core hypothesis or strategy.Direction switches require evidence such as repeated stagnation, a refuted hypothesis, no actionable refinement, or a complementary unused candidate.Source: §A.3 · p. 17
  • Before an R switch, the agent samples an unused candidate and selects a compatible historical parent rather than defaulting automatically to the current leaf.Parent selection weighs candidate applicability, artifact dependencies, evidence value, complementary directions, and frontier priority.Source: §A.3 · p. 17

A.4 DECISION RULES AND DEFAULTS

  • Switching rules require evidence, including two related L attempts with the same stagnation or failure pattern; a timeout or appealing new idea alone is insufficient.After repeated R edges, the protocol prioritizes compatible earlier states and limits another switch from the current node absent a strong artifact dependency.Source: §A.4 · p. 18

A.5 VERIFICATION, STATE UPDATE, AND RECOVERY

  • The verification layer evaluates candidates against the original instance, records validated results and artifacts in the registered node, and updates the pool, frontier, and best verified result.On interruption, the agent restores state and required artifacts before choosing another attempt.Source: §A.5 · p. 19

A.6 ABLATION DEFINITIONS

The appendix defines complementary ablations that isolate persistent pool management and branching state management, alongside standardized task prompts and illustrative convergence trajectories. The examples connect refinement and direction-switch decisions to patterns observed during search.

A.6 ABLATION DEFINITIONS

  • NoPool retains tree-based branching and historical-state reuse but generates directions on demand, whereas NoTree retains the candidate pool but runs experiments in a linear sequence.The two ablations remove different components while retaining the primary task skill's execution, evaluation, budget, and stopping conditions.Source: §A.6 · pp. 19–20

B TASK PROMPTS

  • The Open prompt seeks a verified feasible strict improvement within up to 43,200 seconds, while the Hard prompt targets a historical best-known objective within up to 3,600 seconds.Neither task requires an optimality proof.Source: B TASK PROMPTS · p. 21

C ILLUSTRATIVE INSTANCE-LEVEL CONVERGENCE

  • Across the illustrated instances, AutoMIP trajectories show early drops, successive gains after plateaus, or gradual declines, while both curves retain positive terminal values on the longest example.The longest panel extends to 43,200 seconds; the described patterns motivate continued refinement and evidence-supported switching between directions.Source: C ILLUSTRATIVE INSTANCE-LEVEL… · p. 22

D PER-INSTANCE OPEN RESULTS

The supplied passages identify two panels of per-instance Open results and specify how outcomes and timestamps are interpreted; they do not provide per-instance values.

D PER-INSTANCE OPEN RESULTS

  • The per-instance tables retain YES and NO outcome labels, and a dash after NO indicates that no successful result or corresponding time or token value was recorded.All reported times are in seconds.Source: D PER-INSTANCE OPEN RESULTS · p. 23
  • The main analysis counts Open successes within the 43,200-second horizon using the per-instance timestamps.Figure 3's Open cutoff agrees with the tables, according to its caption.Source: D PER-INSTANCE OPEN RESULTS · p. 23
  • Tables 7 and 8 present the per-instance Open results in two panels.The supplied table captions do not report cell values.Source: Table 7 · p. 23, Table 8 · p. 24

E PER-INSTANCE HARD RESULTS

The Hard results tables report per-instance fixed-target outcomes, with success counted within 3,600 seconds.

E PER-INSTANCE HARD RESULTS

F PER-INSTANCE ABLATION RESULTS

The per-instance ablation results cover 20 shared identities across the full skill, NoPool, and NoTree.

F PER-INSTANCE ABLATION RESULTS

G PER-INSTANCE INTERFACE RESULTS

The per-instance interface results record AutoMIP under Codex and Claude Code at a 43,200-second horizon.

G PER-INSTANCE INTERFACE RESULTS

H PER-INSTANCE MINLPLIB RESULTS

The per-instance MINLPLib results cover a retained common 60-instance nonlinear cohort across five methods.

H PER-INSTANCE MINLPLIB RESULTS

Loading 2609.39360v1…