SEOUL, August 03 (AJP) - Researchers in South Korea have taught an artificial intelligence system to draw up delivery routes, factory schedules and hospital rosters that a company can actually run, without handing the job to the specialist commercial software the industry now relies on to make the numbers work.
In testing, the system produced a legal plan in 100 percent of the problems it was handed, across five benchmark sets used throughout the field. No comparable method that learns end-to-end has managed that on its own.
Korea Advanced Institute of Science and Technology (KAIST) announced the result on Monday. Kim Min-soo, a professor in the school of computing, led the team that built the system, which is called RL-SPH.
The problem it goes after has a formal name in mathematics, integer linear programming, and a very ordinary shape in daily life. A courier company wants the shortest route. It also needs every parcel delivered, no van loaded past its capacity, and no driver kept behind the wheel longer than the law allows. A hospital wants a duty roster that covers every shift, respects rest requirements, and does not put the same nurse in two wards at once. A chip plant wants to hit its delivery dates without asking more of its equipment and its staff than they can give.
Each of those conditions is a constraint. Break one and the plan is worthless, however efficient it looks on paper. A route that shaves 40 minutes off the day is no use if the van cannot physically hold the parcels.
This is where AI has kept stumbling. Recent systems learned to guess at a cheap answer, and often guessed well on cost. They also produced plans that quietly violated a load limit or a working-hours rule. Companies dealt with that by passing the output to a solver, specialist optimization software that grinds through the arithmetic and repairs what the AI broke. The two best known, Gurobi and SCIP, do the heavy lifting in logistics and manufacturing worldwide. The AI never finished the job by itself.
RL-SPH works more like a person redoing a timetable. Instead of predicting a finished answer in one shot, it starts with a plan that breaks the rules and edits it, one variable at a time. Change the number of vans. Change a shift length. See what broke and what got fixed, and learn from the result. The method behind it is reinforcement learning, in which a system improves through repeated trial and error rather than by studying worked examples.
The design choice that matters is the order of priorities. The team told the system to find a legal plan first and a cheap one second. In a factory, that means locking in a schedule that meets every deadline and capacity limit, then squeezing cost and time out of it while keeping it legal. The researchers also proved mathematically that a system trained this way reaches a workable plan within a finite number of edits, rather than wandering indefinitely.
Two other pieces make it faster. One is a model called ILP-GT, designed to catch relationships between variables sitting far apart in a problem, something earlier network designs handled poorly. The other is a search rule that targets the variables turning up most often in broken constraints instead of working through everything in turn.
Across the five benchmarks, RL-SPH found a workable plan every time, including on harder cases involving variables that can take a wide range of values rather than a simple yes or no. Measured against existing methods that also hit a perfect record, it narrowed the distance to the theoretical best answer by 28.6 times on average and reached its first workable plan 2.5 times faster.
Against the newest AI approaches, known as PAS, DDIM and DiffILO, it was the only one to hit 100 percent on all three benchmarks used in the comparison. Training took about 30 minutes, 14.7 times faster than established techniques and roughly 34 times faster than recent methods that learn without being shown correct answers.
The team also ran it against MIPLIB, a public library of optimization problems that serves as a common yardstick for industry and academia. RL-SPH held up on problems as much as 67 times larger than anything in its training, and on problem types it had never encountered.
"In the real world, a plan you can actually carry out matters more than the best possible answer," Kim said. He expects the method to become a foundation for AI-driven decisions in logistics, manufacturing, semiconductor production and workforce planning.
Lee Tae-hoon, a doctoral student at KAIST, is the paper's first author, with Kim as corresponding author. The work was presented at the International Conference on Machine Learning, held from July 6 to 11 at COEX in Seoul.
(Reference Information)
Journal/Source: International Conference on Machine Learning
Title: RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
Link/DOI: https://doi.org/10.48550/arXiv.2411.19517
Copyright ⓒ Aju Press All rights reserved.
