DecompPilot: Long-Horizon Agentic Discovery of Decomposition Strategies for Large-Scale Mixed-Integer Linear Programs

Large-scale mixed-integer linear programs (MILPs) are computationally intensive due to the combinatorial complexity introduced by discrete decisions. Decomposition-based optimization reduces this complexity by partitioning the original program into smaller subproblems and coordinating the subproblem solutions to satisfy coupling constraints and maintain consistency among linking variables. We propose **DecompPilot**, an LLM-agent framework that uses the semantics of decision variables and constraints to automatically design and execute partitioning and coordination strategies tailored to different problem structures. We formulate decomposition design as a long-horizon experimental search problem rather than a one-shot partitioning task, and study whether LLM agents can discover decomposition operators that can be reused across problem instances. This setting introduces two challenges: preserving useful evidence from successful and failed solver trials over long search histories, and accumulating reusable design knowledge from instance-specific experience. To address these challenges, we propose two complementary mechanisms: a *Trial Memory Tree* that preserves instance-level trial evidence for refinement and backtracking, and *Decomposition Operator Induction* that identifies and validates reusable algorithmic components across instances and triggers targeted trials when further evidence is needed. Across four benchmark suites spanning unit commitment and bin packing, the reusable decomposition operators discovered by DecompPilot achieve a 94.5% feasibility rate on unseen instances, including 73 million-scale PEGASE instances. They reduce total solving wall-time by 52.7% on average relative to Gurobi while keeping the average relative objective gap to the Gurobi reference at 0.95%.