KAIST’s RL-SPH reinforcement-learning model hits 100% feasibility on ILP benchmarks and trains 14.7x faster — built for logistics and factory scheduling.
Researchers at the Korea Advanced Institute of Science and Technology (KAIST) have developed an AI technique that can independently generate feasible plans for real-world scheduling problems — from parcel delivery routes to factory production schedules to hospital duty rosters — without relying on a separate optimization solver to guarantee those plans actually work.
KAIST announced on August 3, 2026, that a research team led by Professor Min-Soo Kim of the School of Computing had developed RL-SPH (Reinforcement Learning-based Start Primal Heuristic), a reinforcement learning method that trains AI to produce solutions satisfying all the constraints encoded in an optimization problem, rather than approximate answers that need to be corrected afterward.
The Problem: Optimal Isn’t Always Usable
Many real-world planning tasks — parcel delivery routing, vehicle routing, factory production scheduling, hospital staff rostering — can be formulated as integer linear programming (ILP) problems: finding the most efficient solution while satisfying a set of linear constraints and requiring some or all decision variables to take integer values.
A parcel delivery plan, for instance, has to do more than minimize delivery time. It also has to respect vehicle capacity limits and driver working-hour rules while making sure every destination gets visited. A route that breaks even one of those conditions can’t be used, no matter how short or cheap it looks on paper.
Existing learning-based approaches can generate approximate or partial solutions quickly, but according to the research team, these predictions frequently violate constraints. As a result, many such systems hand their output to specialized ILP solvers like Gurobi or SCIP to actually achieve a feasible result — the AI proposes, and a separate solver has to fix it.
How RL-SPH Works
RL-SPH takes a different approach: instead of trying to predict a final answer in one step, it iteratively revises a candidate solution. At each stage, it selects multiple decision variables likely to improve feasibility and decides whether their values should be increased, decreased, or left unchanged, learning from how those changes affect constraint violations and solution quality.
The system works in two stages. First, it prioritizes finding an initial solution that satisfies every constraint. Only after that does it move to the second stage, seeking a higher-quality solution — lower cost, less processing time — while keeping the plan feasible throughout. In a factory production-planning scenario, for example, RL-SPH would first identify a schedule that meets delivery deadlines, equipment capacity, and labor availability, and only then work to reduce production cost and time without breaking those constraints.
The team also introduced ILP-GT, a new model that learns the relationships between variables and constraints, paired with a feasibility-aware search strategy that prioritizes revising the variables most likely to resolve the problem — a combination the researchers say substantially improves computational efficiency.
Results
Across five representative ILP benchmarks, RL-SPH achieved a 100% feasibility rate, successfully producing a usable plan for every problem tested, including more complex cases involving general (non-binary) integer variables.
Compared with existing techniques, RL-SPH reduced the primal gap — the difference between a method’s solution and the best-known solution — by an average of 28.6 times, and improved the primal integral, a measure of search speed and quality, by 2.6 times. It also found its first feasible plan 2.5 times faster on average.
Among recent AI techniques the team compared it against — including PAS, DDIM, and DiffILO — RL-SPH was the only method to achieve a 100% feasibility rate across three shared benchmarks (SC, CA, and IS). Training itself took an average of just 30 minutes: 14.7 times faster than existing learning-based techniques, and roughly 34 times faster than the most recent unsupervised-learning-based approach.
The method also generalized well on MIPLIB, an international benchmark library for mixed-integer programming widely used in academia and industry. RL-SPH reliably found feasible plans for problems up to 67 times larger than those it was trained on, as well as for entirely new problem types it had never seen during training.
What the Researchers Are Saying
“In real-world applications, a plan that can actually be implemented is often more important than a theoretically optimal answer that violates practical constraints,” said Professor Kim.
“This research demonstrates that AI can learn to generate feasible solutions without relying on a specialized optimization solver to enforce feasibility,” he added. “We expect the technology to provide an important foundation for AI-based decision-making in logistics, manufacturing, semiconductor production, workforce management, and other industrial fields.”
Tae-Hoon Lee, a doctoral student in KAIST’s School of Computing, is the paper’s first author; Professor Min-Soo Kim led the research and is the corresponding author. The findings were presented at the 43rd International Conference on Machine Learning (ICML 2026), held in Seoul from July 6 to 11 — regarded as one of the world’s premier machine learning conferences.
The research was supported by South Korea’s Ministry of Science and ICT and the Institute of Information & Communications Technology Planning & Evaluation (IITP) through related software research and Information Technology Research Center (ITRC) programs, as well as by the National Research Foundation of Korea (NRF).