Researchers have devised a new data-driven machine-learning technique that accelerates software programs used to handle large optimization problems with potentially millions of solutions. Their method could be used to a variety of difficult logistical problems, including package routing, vaccine distribution, and power grid management.
While Santa Claus has a wonderful sleigh and nine brave reindeer to help him deliver presents, the optimization challenge of properly routing holiday shipments is so complex that firms like FedEx frequently use specialist algorithms to find a solution.
This software, called a mixed-integer linear programming (MILP) solver, splits a massive optimization problem into smaller pieces and uses generic algorithms to try and find the best solution. However, the solver could take hours — or even days — to arrive at a solution.
The procedure is so time-consuming that companies frequently have to halt the software mid-stream, accepting a solution that isn’t ideal but is the best that could be achieved in a certain length of time.
Separator management is a core part of every solver, but this is an underappreciated aspect of the problem space. One of the contributions of this work is identifying the problem of separator management as a machine learning task to begin with.
Cathy Wu
Machine learning was utilized by researchers from MIT and ETH Zurich to accelerate the process. They identified a critical intermediary stage in MILP solvers that has so many potential solutions that unraveling it takes a tremendous amount of time, slowing the entire process. To simplify this procedure, the researchers applied a filtering strategy, followed by machine learning to determine the best answer for a given type of problem.
Their data-driven approach enables a company to use its own data to tailor a general-purpose MILP solver to the problem at hand. This new technique sped up MILP solvers between 30 and 70 percent, without any drop in accuracy. One could use this method to obtain an optimal solution more quickly or, for especially complex problems, a better solution in a tractable amount of time.
This approach could be used wherever MILP solvers are employed, such as by ride-hailing services, electric grid operators, vaccination distributors, or any entity faced with a thorny resource-allocation problem.
“Sometimes, in a field like optimization, it is very common for folks to think of solutions as either purely machine learning or purely classical. I am a firm believer that we want to get the best of both worlds, and this is a really strong instantiation of that hybrid approach,” says senior author Cathy Wu, the Gilbert W. Winslow Career Development Assistant Professor in Civil and Environmental Engineering (CEE), and a member of a member of the Laboratory for Information and Decision Systems (LIDS) and the Institute for Data, Systems, and Society (IDSS).
Wu wrote the paper with co-lead authors Siriu Li, an IDSS graduate student, and Wenbin Ouyang, a CEE graduate student; as well as Max Paulus, a graduate student at ETH Zurich. The research will be presented at the Conference on Neural Information Processing Systems.
Tough to solve
MILP problems have an infinite number of possible solutions. For example, suppose a traveling salesperson wishes to discover the fastest route to visit numerous places and then return to their starting point. If there are numerous cities that can be visited in any order, the number of viable solutions may exceed the number of atoms in the universe.
“These issues are referred to as NP-hard, which suggests that an efficient solution to solve them is extremely unlikely. When the task is large enough, we can only hope for suboptimal results,” Wu explains.
An MILP solver uses a variety of approaches and practical tricks to arrive at suitable solutions in a fair amount of time.
A typical solver uses a divide-and-conquer approach, first splitting the space of potential solutions into smaller pieces with a technique called branching. Then, the solver employs a technique called cutting to tighten up these smaller pieces so they can be searched faster.
Cutting uses a set of rules that tighten the search space without removing any feasible solutions. These rules are generated by a few dozen algorithms, known as separators, that have been created for different kinds of MILP problems.
Wu and her team found that the process of identifying the ideal combination of separator algorithms to use is, in itself, a problem with an exponential number of solutions.
“Separator management is a core part of every solver, but this is an underappreciated aspect of the problem space. One of the contributions of this work is identifying the problem of separator management as a machine learning task to begin with,” she says.
Shrinking the solution space
She and her collaborators devised a filtering mechanism that reduces this separator search space from more than 130,000 potential combinations to around 20 options. This filtering mechanism draws on the principle of diminishing marginal returns, which says that the most benefit would come from a small set of algorithms, and adding additional algorithms won’t bring much extra improvement.
Then, from the 20 remaining alternatives, they apply a machine-learning model to select the optimum combination of methods. This model is trained using a dataset tailored to the user’s optimization problem, and it learns to select methods that are best suited to the user’s individual task. Because a corporation like FedEx has addressed routing difficulties before, using real data acquired from previous experience should result in better solutions than starting from scratch each time.
The model’s iterative learning process, known as contextual bandits, a type of reinforcement learning, entails selecting a probable solution, receiving input on how good it was, and then attempting to discover a better answer again.
This data-driven technique sped up MILP solvers by 30 to 70% while maintaining accuracy. Furthermore, the speedup was comparable when applied to a simpler, open-source solution as well as a more capable, commercial solver.
Wu and her colleagues hope to apply this strategy to even more complex MILP problems in the future, where getting labeled data to train the model could be particularly difficult. She suggests that they train the model on a smaller dataset and then adapt it to solve a much larger optimization challenge. The researchers want to interpret the learned model to better understand the performance of various separation methods.
