From parcel delivery routes and factory production schedules to hospital duty rosters, many real-world planning tasks require solutions that satisfy numerous operational constraints. KAIST researchers have developed an artificial intelligence technique that can independently generate feasible plans satisfying all constraints specified in a mathematical optimization problem.
KAIST (President Choongsik Bae) announced on August 3 that a research team led by Professor Min-Soo Kim from the School of Computing has developed RL-SPH (Reinforcement Learning-based Start Primal Heuristic), a reinforcement learning technique that trains AI to independently produce feasible plans without relying on an external solver.
The key feature of the technology is its ability to learn how to produce solutions that satisfy the multiple constraints encoded in an optimization problem. The research team expects the method to serve as an important foundation for AI-based decision-making in fields including logistics, manufacturing, semiconductor production, and workforce management.
Parcel delivery routing, vehicle routing, factory production scheduling, and hospital staff rostering are representative planning problems that can be formulated using integer linear programming, or ILP. ILP is a mathematical optimization technique for 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 example, must do more than simply minimize delivery time. It must also comply with vehicle capacity limits and driver working-hour requirements while ensuring that every destination is visited. A route that violates even one of these conditions cannot be used in practice, regardless of how short or inexpensive it may appear.
Existing learning-based approaches can rapidly generate approximate or partial solutions, but these predictions frequently violate constraints. Consequently, many approaches pass their outputs to specialized ILP solvers, such as Gurobi or SCIP, which are then responsible for obtaining a feasible solution. The paper notes that existing end-to-end learning-based primal heuristics generally struggle to generate feasible solutions independently.
RL-SPH addresses this limitation by iteratively revising a candidate solution rather than attempting to predict the final answer in a single step. At each stage, it selects multiple decision variables that are likely to improve feasibility and determines whether their values should be increased, decreased, or left unchanged. The model then learns from the resulting changes in constraint violations and solution quality.
Notably, the team designed the AI to first find a plan that is actually usable, rather than the single best plan. The overall procedure consists of two stages. In the first stage, the AI prioritizes finding an initial feasible solution that satisfies all constraints. In the second stage, it seeks a higher-quality solution by reducing the objective value, such as cost or processing time, while maintaining feasibility.
For example, in a factory production-planning problem, the method would first identify a schedule that satisfies requirements such as delivery deadlines, equipment capacity, and available labor. It would then attempt to reduce production cost and time without violating those conditions. The research therefore prioritizes finding a plan that can actually be implemented before attempting to optimize it further.
The team also introduced ILP-GT, a new AI model that learns the relationships between variables and constraints, along with a feasibility-aware search strategy that prioritizes revising the variables most effective for resolving the problem, substantially improving computational efficiency.
Across five representative benchmarks, RL-SPH achieved a 100% feasibility rate, successfully finding a usable plan for every problem. It maintained the same performance even on more complex problems involving general (non-binary) integer variables.
Compared with existing techniques, RL-SPH reduced the primal gap — the gap 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 the speed and quality of the search process — by 2.6 times. The time needed to find the first feasible plan was also 2.5 times faster on average.
Among recent AI techniques such as PAS, DDIM, and DiffILO, RL-SPH was the only method to achieve a 100% feasibility rate across three benchmarks compared (SC, CA, IS). Its training also took an average of just 30 minutes — 14.7 times faster than existing techniques and roughly 34 times faster than the most recent unsupervised learning — an AI training method that finds patterns in data without being given the correct answers in advance — based technique.
The technique further demonstrated its generalization potential on MIPLIB, an international benchmark library for mixed-integer programming widely used in academia and industry. It reliably found feasible plans not only for problems up to 67 times larger than those it was trained on, but also for entirely new problem types it had never encountered during training.
"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.
He added, "This research demonstrates that AI can learn to generate feasible solutions without relying on a specialized optimization solver to enforce feasibility. 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 the KAIST School of Computing, participated as the first author, and Professor Min-Soo Kim led the research.
The findings were presented at the 43rd International Conference on Machine Learning, or ICML 2026, held in Seoul from July 6 to 11. ICML is regarded as one of the world's premier international conferences in machine learning.
※ Paper title: RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
※ DOI: https://doi.org/10.48550/arXiv.2411.19517
※ Authors: Tae-Hoon Lee (KAIST, first author), Min-Soo Kim (KAIST, corresponding author)
This research was supported by the Ministry of Science and ICT and the Institute of Information & Communications Technology Planning & Evaluation through related software research and Information Technology Research Center programs, as well as by the National Research Foundation of Korea. The paper's acknowledgements specifically identify NRF and IITP support, including an ITRC grant.
