KAIST researchers have developed an artificial intelligence system that can generate workable plans for complex real-world problems without depending on a specialized optimization solver to repair its mistakes. The system, called RL-SPH, is designed for situations in which every decision must satisfy multiple operational rules at once, including parcel delivery routes, factory production schedules, semiconductor manufacturing plans, and hospital staff rosters. In tests, the method produced feasible solutions for every problem it was given, offering a potential new path toward AI systems that can make decisions under strict practical constraints.
The research team, led by Professor Min-Soo Kim of the KAIST School of Computing, developed Reinforcement Learning-based Start Primal Heuristic, or RL-SPH, to address one of the most persistent weaknesses in learning-based optimization. Conventional machine-learning models can often produce an answer quickly, but their predictions may violate essential requirements. A delivery route might exceed a vehicle’s capacity, a factory schedule might assign the same machine to two jobs at once, or a hospital roster might breach staffing rules. In real operations, even a highly efficient plan is unusable if it breaks a single constraint.
Many of these planning challenges are represented mathematically as integer linear programming, or ILP. In an ILP model, decision variables describe choices such as whether a vehicle visits a destination, how many units a factory produces, or which employee works a particular shift. Linear equations and inequalities describe the limits imposed on those choices, while an objective function measures what the system is trying to minimize or maximize, such as cost, delivery time, energy consumption, or production delay. Some variables must be whole numbers, making the problem substantially more difficult than ordinary linear optimization.
Existing AI-based approaches often attempt to predict a final solution in one step. Although this can be fast, the resulting answer may be incomplete or infeasible. To make such outputs usable, researchers commonly pass them to established solvers such as Gurobi or SCIP. Those solvers then search for a valid solution or repair the candidate produced by the AI. While effective, this arrangement means the AI itself has not truly learned how to construct a plan that satisfies the problem’s rules. It also creates a bottleneck when solutions are needed rapidly or when a solver is unavailable.
RL-SPH takes a different approach by treating plan construction as an iterative decision process. Rather than guessing the final answer at once, the system begins with a candidate solution and repeatedly modifies it. At each step, the AI identifies several decision variables that are likely to reduce constraint violations or improve the quality of the plan. It then determines whether each selected variable should be increased, decreased, or left unchanged. After observing the effect of those changes, the model receives feedback and learns which actions are most useful.
This process is based on reinforcement learning, a technique in which an AI improves through repeated interaction with an environment. In RL-SPH, the environment is the mathematical optimization problem, and the feedback reflects both feasibility and performance. Changes that reduce violations are rewarded during the search for a valid plan, while improvements to the objective function become more important after feasibility has been achieved. This distinction is central to the system’s design: it first seeks a plan that can actually be implemented and only then attempts to make that plan cheaper, faster, or more efficient.
The researchers describe the approach as a two-stage strategy. During the first stage, RL-SPH concentrates on satisfying all constraints, even if the resulting plan is far from optimal. Once it reaches a feasible solution, the second stage focuses on improving the objective value without losing feasibility. In a manufacturing scenario, for example, the AI might initially create a schedule that meets delivery deadlines, respects equipment capacity, and fits within available labor. It could then refine that schedule to reduce production costs or processing time while preserving every operational requirement.
To improve the system’s ability to navigate large optimization problems, the team also introduced ILP-GT, a model that learns relationships between variables and constraints. These relationships help the AI determine which decisions are most influential when a plan violates a rule. The researchers combined this model with a feasibility-aware search strategy that prioritizes variables likely to resolve the most serious problems. Instead of spending equal effort on every part of a large mathematical model, the system focuses its computational resources where they are most likely to produce progress.
Across five representative benchmarks, RL-SPH achieved a 100 percent feasibility rate, including on problems containing general integer variables rather than only binary yes-or-no decisions. The method reduced the primal gap, which measures the difference between a generated solution and the best-known solution, by an average factor of 28.6 compared with existing approaches. It also improved the primal integral, a measure that captures how quickly and effectively a method discovers high-quality solutions, by 2.6 times. The time required to find the first feasible plan was 2.5 times shorter on average.
The system also performed strongly against recent AI methods known as PAS, DDIM, and DiffILO. Across three comparison benchmarks, RL-SPH was the only method to achieve a 100 percent feasibility rate. Its training required an average of about 30 minutes, which the team reports was 14.7 times faster than competing methods and approximately 34 times faster than the most recent unsupervised-learning-based technique. The researchers further tested RL-SPH on MIPLIB, an international library of mixed-integer programming problems widely used by academics and industry. The AI generated feasible plans for problems up to 67 times larger than those used during training, as well as for problem types it had not previously encountered.
The findings suggest that AI may be able to learn the structure of constrained decision-making rather than merely imitate answers produced by an optimizer. That distinction could be important in logistics networks, manufacturing systems, workforce management, and other settings where conditions change quickly and a valid response is needed before a perfect solution can be found. “In real-world applications, a plan that can actually be implemented is often more important than a theoretically optimal answer that violates practical constraints,” Professor Kim said. The research, led by doctoral student Tae-Hoon Lee, was presented at the 43rd International Conference on Machine Learning in Seoul. The paper is titled “RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs.”
Subject of Research: Artificial intelligence for feasible integer linear programming solutions and constrained decision-making
Article Title: RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
Web References: https://doi.org/10.48550/arXiv.2411.19517
References: Tae-Hoon Lee and Min-Soo Kim, “RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs”
Image Credits: KAIST
Keywords
Artificial intelligence, reinforcement learning, integer linear programming, optimization, logistics, manufacturing, scheduling, feasible solutions, KAIST, RL-SPH
