cs.AINov 18, 2026

SailSearch: Agent-Assisted Discovery in Combinatorial Optimization

Authors: Dhriti Verma, Kanthi Sarpatwar, Vinicius Lima, Dzung Phan, Jayant Kalagnanam

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

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Hard Instances on Demand

    Oct 15, 2026Jamie Fravel, Martin Koutecký, Pavlo TsitseiSynthetic Benchmark Generation

  2. Distribution-Aware Programming: Learning Specialized Solvers from Experience

    May 13, 2026Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano +1Large Language Model-Guided OptimizationLLM-Based Program Synthesis

  3. Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances

    Nov 13, 2026Andre Albrecht, Enzo Morosini Frazzon, Leandro C. Coelho +1Job Shop SchedulingAI Coding Agents