SailSearch: Agent-Assisted Discovery in Combinatorial Optimization
Organizations: IBM Research, Yorktown Heights, NY, USA
Abstract
We present SailSearch, a human-guided workflow for algorithmic research with two language-model agents, and report results on Market Split and maximum independent set (MIS). For Market Split, our randomized algorithm searches across multiple lattice bases, dividing computation between enumeration and continued basis reduction. Across ten random seeds per instance, it found the first reported CPU-only solutions to 18 of 33 previously open QOBLIB instances, solving 130 to 133 of the 156 benchmark instances per seed with a 24-hour cutoff on two CPU cores. For MIS, our generator encodes planted XOR constraints as graphs with certified optima; on seven instances with 1,752 to 3,996 vertices, the best solutions returned by the tested solvers in eight-hour runs were 5 to 15 vertices below the optimum.
Figures & tables
| Vertices | Edges | Optimum | Runs | Best | Shortfall |
|---|---|---|---|---|---|
| 960 | 5,280 | 240 | 24 | 239 | 1 |
| 1,356 | 7,458 | 339 | 20 | 336 | 3 |
| 1,752 | 9,636 | 438 | 20 | 433 | 5 |
| 2,160 | 11,880 | 540 | 15 | 533 | 7 |
| 2,556 | 14,058 | 639 | 15 | 630 | 9 |
| 2,952 | 16,236 | 738 | 15 | 729 | 9 |
| CPLEX | Kempke–Koch | solvediophant | Lattice algorithm | |||||
|---|---|---|---|---|---|---|---|---|
| Solved | Mean SD | Solved | Mean SD | Solved | Mean SD | Solved | Mean SD | |
| 100/50 | 0 † | — | 4 | 4 | 4 | |||
| 100/100 | 0 † | — | 0 | — | 2 | 4 | ||
| 100/200 | 0 † | — | 0 | — | 1 | 4 | ||
| 110/50 | 0 † | — | 0 † | — | 4 | 4 | ||
| 110/100 | 0 † | — | 0 † | — | 2 | 4 | ||
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
| Vertices | ||||||||
|---|---|---|---|---|---|---|---|---|
| Solver | 1,752 | 2,160 | 2,556 | 2,952 | 3,360 | 3,756 | 3,996 | Mean shortfall (%) |
| MetaVC (DIMACS) | 5 | 7 | 9 | 11 | 12 | 15 | 16 | 1.4 |
| NuMVC | 5 | 7 | 9 | 11 | 13 | 15 | 15 | 1.4 |
| MetaVC (BHOSLIB) | 5 | 8 | 9 | 9 | 13 | 15 | 17 | 1.4 |
| MetaVC (default) | 6 | 7 | 9 | 11 | 13 | 15 | 16 | 1.5 |
| ReduMIS | 6 | 8 | 10 | 12 | 13 | 15 | 16 | 1.5 |
| NuMVC | MetaVC | ||||
|---|---|---|---|---|---|
| Vertices | Incidence | Path | All pairs | Path | All pairs |
| 960 | Quasi-cyclic | ||||
| 960 | Random regular | ||||
| 1,752 | Quasi-cyclic | ||||
| 1,752 | Random regular | ||||
| Vertices | Edges | Optimum | Runs | Best | Shortfall | Patterns | ||
|---|---|---|---|---|---|---|---|---|
| 960 | 5,280 | 240 | 86 | 0.36 | 24 | 239 | 1 | |
| 1,356 | 7,458 | 339 | 122 | 0.36 | 20 | 336 | 3 | |
| 1,752 | 9,636 | 438 | 164 | 0.37 | 20 | 433 | 5 | |
| 2,160 | 11,880 | 540 | 212 | 0.39 | 15 | 533 | 7 | |
| 2,556 | 14,058 | 639 | 256 | 0.40 | 15 | 630 | 9 | |
| 2,952 | 16,236 | 738 | 286 | 0.39 | 15 | 729 | 9 |
| Instance | Successes | 95% interval (%) | Mean SD (h) | |
|---|---|---|---|---|
| ms_12_100_003 | 10/10 | 69.2–100.0 | ||
| ms_12_200_000 | 10/10 | 69.2–100.0 | ||
| ms_12_200_001 | 8/10 | 44.4–97.5 | ||
| ms_12_200_002 | 9/10 | 55.5–99.7 | ||
| ms_12_200_003 | 10/10 | 69.2–100.0 | ||
| ms_13_100_000 | 2/10 | 2.5–55.6 |
| CPLEX | Kempke–Koch | solvediophant | Lattice algorithm | |||||
|---|---|---|---|---|---|---|---|---|
| Solved | Mean SD | Solved | Mean SD | Solved | Mean SD | Solved | Mean SD | |
| 20/50 | 4 | 4 | 4 | 4 | ||||
| 20/100 | 4 | 4 | 4 | 4 | ||||
| 20/200 | 4 | 4 | 4 | 4 | ||||
| 30/50 | 4 | 4 | 4 | 4 | ||||
| 30/100 | 4 | 4 | 4 | 4 | ||||
| All 156 instances | Previously open 33 | |||
|---|---|---|---|---|
| Algorithm | Range | Mean SD | Range | Mean SD |
| Full algorithm | 130–133 | 7–10 | ||
| One basis per process | 126–131 | 3–8 | ||
| No continued reduction | 125–129 | 3–7 | ||
| Rank cost only | 128–131 | 6–8 | ||
| Gaussian cost only | 126–131 | 7–10 | ||
| Comparison variant | Mean difference | 95% interval |
|---|---|---|
| One basis per process | 3.0 | |
| No continued reduction | 4.4 | |
| Rank cost only | 2.0 | |
| Gaussian cost only | 3.4 |
| Common instances | solvediophant median (h) | Lattice algorithm median (h) | |||
|---|---|---|---|---|---|
| 11 | 100 | 50 | 4 | ||
| 11 | 100 | 100 | 2 | 3.41 | 0.08 |
| 11 | 100 | 200 | 1 | 1.66 | 1.24 |
| 12 | 110 | 50 | 4 | 0.15 | 0.03 |
| 13 | 120 | 50 | 4 | 1.20 | 0.27 |
| 14 | 130 | 50 | 2 | 10.06 | 2.86 |
| Proposal or question | Test outcome | Subsequent decision |
|---|---|---|
| Ideator proposes quasi-cyclic lifts and a concatenation of small parity modules | The tested parity-module instances were solved. | Worker implemented the quasi-cyclic alternative from the same proposal. |
| Worker makes early hardness claims for quasi-cyclic instances | Repeated seeds and corrected resource allocation overturned several claims. | Worker withdrew the claims and retained the generator for further testing. |
| Ideator proposes keeping local choices ambiguous after a vertex is fixed | Four instances reached the target ambiguity but were solved within ten minutes. | Worker rejected the generator built on this ambiguity measure. |
| Human requires resistance to both CPLEX and local search | CPLEX solved the candidate in 42.5 seconds; two of three fresh ReduMIS seeds also solved it. | Candidate selection required tests with both solvers. |
| Ideator proposes replacing some XOR constraints with exactly-one constraints | CPLEX solved the resulting instances in 0.0–6.9 seconds. | Worker rejected the mixed-constraint generator. |
| Human asks which retained generator is strongest | Stored comparisons identified quasi-cyclic instances as promising for the revised size target. | Worker returned to the quasi-cyclic generator and scaled it. |
| Proposal or question | Test outcome | Subsequent decision |
|---|---|---|
| Ideator proposes equivalent lattice bases | A known-solution diagnostic showed large variation in search cost across bases. | Following ideator feedback, worker tested search and selection using only problem data. |
| Worker ranks bases by an entropy score computed before search | The three solving bases and all candidate bases had similar mean scores, 11.8 and 11.7. | Worker rejected the ranking rule; human requested a more informative search assessment. |
| Human asks how search behavior varies across bases | Short searches solved the smaller of two instances on eight of 114 bases and the larger on none of 27. | Worker continued testing node-limited searches and later revised its interpretation of the failure on the larger instance. |
| Worker interprets a small comparison of adaptive and random reduction settings as a general limit | In small samples, adaptive and random choices of reduction settings gave similar best results. | After further challenge, worker withdrew the limit claim and implemented a stronger solver. |
| Worker allocates search by smallest observed violation | One basis consumed more than five million candidate checks without a solution. | Worker adopted iterative deepening with equal node budgets for all bases, keeping violation only as a tie-break. |
| Phase | Human records | Tool calls | Worker model |
|---|---|---|---|
| MIS early investigation | 36 | 379 | Opus 4.8 |
| MIS discovery and first release | 86 | 634 | Opus 4.8, 5 |
| MIS larger instances | 23 | 356 | Opus 5, 5.5 |
| Market Split first approach | 15 | 138 | Opus 4.8 |
| Market Split discovery | 9 | 84 | Opus 4.8 |
| Market Split scaling | 55 | 548 | Opus 4.8 |
| Code | Definition | Records |
|---|---|---|
| Objective | Research goals and scope | 19 |
| Evidence | Acceptance criteria, validity and fairness checks | 49 |
| Conduct | Interpretation of results and research procedure | 14 |
| Compute | Computational budgets and run control | 14 |
| Mechanism | Human-originated methods or design constraints | 6 |
| Selection | Endorsement of an agent proposal | 5 |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 417 papers