While Santa may have a magical sleigh and nine brave reindeer to help him deliver gifts, for companies like FedEx, the optimization problem of efficiently routing holiday packages is so complicated that they often employ specialized software to find a solution.
This software, called a mixed integer linear programming (MILP) solver, breaks a massive optimization problem into smaller parts and uses generic algorithms to try to find the best solution. However, it could take hours (or even days) for the solver to arrive at a solution.
The process is so onerous that a company often must stop the software midway, accepting a solution that is not ideal, but the best that could be produced in a given period of time.
Researchers at MIT and eth Zurich used machine learning to speed things up.
They identified a key intermediate step in MILP solvers that has so many potential solutions that it takes an enormous amount of time to unravel them, slowing down the entire process. The researchers employed a filtering technique to simplify this step and then used machine learning to find the optimal solution for a specific type of problem.
Its data-driven approach allows 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 by 30 to 70 percent, without losing accuracy. This method could be used to obtain an optimal solution more quickly or, for especially complex problems, a better solution in a manageable period of time.
This approach could be used wherever MILP solvers are employed, such as ride-hailing services, power grid operators, vaccine distributors, or any entity facing a thorny resource allocation problem.
“Sometimes in a field like optimization, it is very common for people to think that solutions are purely machine learning or purely classical. I firmly believe that we want to get the best of both worlds, and this is a really strong instance of that hybrid approach,” says lead author Cathy Wu, Gilbert W. Winslow Career Development Assistant Professor in Civil and Environmental Engineering (CEE), and member of the Laboratory of Information and Decision Systems (LIDS) and the Institute of Data, Systems and Society (IDSS).
Wu wrote the paper with co-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 Neural Information Processing Systems Conference.
difficult to solve
MILP problems have an exponential number of potential solutions. For example, let's say a traveling salesman wants to find the shortest way to visit several cities and then return to his hometown. If there are many cities that can be visited in any order, the number of potential solutions could be greater than the number of atoms in the universe.
“These problems are called NP-hard, which means that it is very unlikely that there is an efficient algorithm to solve them. When the problem is large enough, we can only hope to achieve suboptimal performance,” explains Wu.
A MILP solver employs a variety of practical techniques and tricks that can achieve reasonable solutions in a manageable period of time.
A typical solver uses a divide and conquer approach, first dividing the space of potential solutions into smaller parts with a technique called branching. The solver then uses a technique called cutting to squeeze these smaller pieces together so they can be searched faster.
Cutting uses a set of rules that reduce the search space without eliminating any feasible solutions. These rules are generated by a few dozen algorithms, known as separators, that have been created for different types of MILP problems.
Wu and his team discovered that the process of identifying the ideal combination of separator algorithms to use is itself a problem with an exponential number of solutions.
“Separator management is a fundamental part of every solver, but it is an underrated aspect of the problem space. One of the contributions of this work is to identify the separator management problem as a machine learning task to begin with,” he states.
Reduce solution space
She and her collaborators devised a filtering mechanism that reduces this separator search space from more than 130,000 potential combinations to about 20 options. 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 additional algorithms will not bring much additional improvement.
They then use a machine learning model to choose 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 the algorithms that best fit the user's particular task. Since a company like FedEx has solved routing problems many times before, using real data gleaned from past experiences should lead to better solutions than starting from scratch every time.
The iterative model learning process, known as contextual bandits, a form of reinforcement learning, involves choosing a potential solution, getting feedback on how good it was, and then trying again to find a better solution.
This data-driven approach sped up MILP solvers by 30 to 70 percent without losing 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 his collaborators want to apply this approach to even more complex MILP problems, where collecting labeled data to train the model could be especially challenging. Maybe they can train the model on a smaller data set and then modify it to address a much larger optimization problem, he says. Researchers are also interested in interpreting the learned model to better understand the effectiveness of different separator 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.
