While Santa may have a magical sleigh and nine charismatic reindeer to help him deliver presents, for companies like FedEx, the problem of optimizing the efficient routing of holiday packages is so complex that they often use specialized software to solve it.
This software, called a mixed-integer linear programming (MILP) solver, breaks a huge optimization problem into smaller pieces and uses general algorithms to try to find the best solution. However, the solver could take hours – or even days – to arrive at a solution.
The process is so burdensome that a company often has to stop the software part way through, accepting a solution that is not ideal but the best that could be created in a given time.
Researchers from MIT and ETH Zurich used machine learning to speed things up.
They identified a key intermediate step in MILP solvers that has so many possible solutions that it takes an enormous amount of time to unravel, which slows down the whole process. The researchers used a filtering technique to simplify this step and then used machine learning to find the optimal solution for a particular type of problem.
Their data-driven approach allows a company to use its own data to adapt 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 achieve an optimal solution more quickly or, for particularly complex problems, a better solution in a reasonable amount of time.
This approach could be used anywhere MILP solvers are used, such as by ride-hailing services, electric grid operators, vaccination distributors, or any entity facing a thorny resource allocation problem.
“Sometimes in a field like optimization, it’s very common for people to think of solutions as either purely machine learning or purely classical. I strongly believe that we want to get the best of both worlds, and this is a really strong example of this hybrid approach,” says senior author Cathy Wu, the Gilbert W. Winslow Assistant Career Development Professor in Civil and Environmental Engineering (CEE) , and a fellow of the Laboratory for Information and Decision Systems (LIDS) and the Institute for Data, Systems and Society (IDSS).
Wu wrote it paper with co-lead authors Sirui Li, IDSS graduate student, and Wenbin Ouyang, CEE graduate student. as well as Max Paulus, graduate student at ETH Zurich. The research will be presented at the Conference on Neural Information Processing Systems.
Hard to solve
MILP problems have an exponential number of possible solutions. For example, say a traveling salesman wants to find the shortest path to visit several cities and then return to his home city. If there are many cities you could visit in any order, the number of possible solutions may be greater than the number of people in the universe.
“These problems are called NP-hard, which means that it is highly unlikely that there will be an efficient algorithm to solve them. When the problem is big enough, we can only hope to achieve some suboptimal performance,” explains Wu.
A MILP solver uses a number of techniques and practical tricks that can achieve reasonable solutions in a reasonable amount of time.
A typical solver uses a divide-and-conquer approach, first dividing the space of possible solutions into smaller pieces with a technique called branching. The solver then uses a technique called clipping to compress these smaller pieces so they can be searched more quickly.
Cutting uses a set of rules that limit the search space without eliminating any feasible solutions. These rules are generated by a few dozen algorithms, known as classifiers, that have been created for different kinds of MILP problems.
Wu and her team found that the process of determining the ideal combination of partitioning algorithms to use is, in itself, a problem with an exponential number of solutions.
“Separator management is a key part of any solution, but this is an underappreciated aspect of the problem space. One of the contributions of this work is identifying the splitter management problem as a machine learning task at the outset,” he says.
Shrinking the solution space
She and her colleagues devised a filtering mechanism that reduces this separator search space from more than 130,000 possible combinations to about 20 choices. This filtering mechanism is based on the principle of diminishing marginal returns, which says that the greatest benefit would come from a small set of algorithms, and adding more algorithms would not bring much additional improvement.
They then use a machine learning model to select the best combination of algorithms from the remaining 20 options.
This model is trained with a data set specific to the user’s optimization problem, so it learns to choose algorithms best suited to the user’s specific task. Since a company like FedEx has solved routing problems many times in the past, using real data gathered from past experience should lead to better solutions than starting from scratch each time.
The model’s iterative learning process, known as context bandits, a form of reinforcement learning, involves choosing a possible solution, getting feedback on how good it was, and then trying again to find a better solution.
This data-driven approach sped up the MILP solvers between 30 and 70 percent without any drop in accuracy. Furthermore, the speedup was similar when applied to a simpler open source solver and a more powerful, commercial solver.
In the future, Wu and her colleagues want to apply this approach to even more complex MILP problems, where collecting labeled data for model training could be especially difficult. Perhaps they can train the model on a smaller data set and then modify it to tackle a much larger optimization problem, he says. Researchers are also interested in interpreting the learned model to better understand the effectiveness of different segmentation algorithms.
This research is supported, in part, by Mathworks, the National Science Foundation (NSF), the MIT Amazon Science Hub, and the MIT Research Support Committee.