The AI ​​approach offers solutions to tricky optimization problems, from global package routing to power grid operation.

While Santa has a magical sleigh and nine brave reindeer to help him deliver the presents, for companies like FedEx, the problem of optimizing the efficient delivery of holiday packages is so complex that they often use specialized software to find a solution.

This software, called a mixed integer linear programming (MILP) solver, breaks a massive optimization problem into smaller pieces and uses generic algorithms to try to find the best solution. However, the solver can take hours or even days to arrive at a solution.

The process is so expensive that a company often has to shut down the software midstream, accepting a solution that is not ideal but the best that can be generated within a set amount of 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 potential solutions that it takes an enormous amount of time to untangle, slowing down the entire process. The researchers used a filtering technique to simplify this step, then used machine learning to find the optimal solution to a specific type of problem.

Their 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 accelerated MILP solvers by between 30 and 70 percent, without any loss of accuracy. This method could be used to obtain an optimal solution more quickly or, for particularly complex problems, a better solution within a reasonable amount of time.

This approach could be used anywhere MILP solvers are used, for example by ride-sharing services, power grid operators, vaccine 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 purely machine learning or purely classical. I firmly believe that we want to get the best of both worlds, and this is a very strong instantiation of that hybrid approach,” says lead author Cathy Wu, Gilbert W. Winslow Career Development Assistant Professor of Civil Engineering. and Environmental (CEE), and 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, 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, suppose a traveling salesman wants to find the shortest route to visit several cities and then return to his original city. If there are many cities that could 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 uses a range of practical techniques and tricks that achieve reasonable solutions in a reasonable amount of time.

A typical solver uses a divide-and-conquer approach, first dividing the space of potential solutions into smaller pieces through a technique called branching. Then the solver uses a technique called slicing to squeeze these smaller pieces together so they can be searched more quickly.

Cutting uses a set of rules that narrows the search space without removing any feasible solutions. These rules are generated by a few dozen algorithms, called separators, created for different types of MILP problems.

Wu and his team discovered that the process of identifying the ideal combination of separation algorithms to use is, itself, a problem with an exponential number of solutions.

“Handling separators is an essential part of any solver, but it is an underappreciated aspect of the problem space. One of the contributions of this work is identifying the problem of handling separators as a machine learning task,” she says.

Reduce solution space

She and her collaborators designed a filtering mechanism that reduces this separator search space from more than 130,000 potential combinations to about 20 options. This filtering mechanism relies on the principle of diminishing marginal returns, which states that the greatest benefit would come from a small set of algorithms, and adding additional algorithms would not provide 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 dataset specific to the user’s optimization problem, so it learns to choose the algorithms best suited to the user’s particular task. Since a company like FedEx has solved routing problems many times before, using real data from past experience should lead to better solutions than starting from scratch each time.

The model’s iterative learning process, known as contextual bandits, a form of reinforcement learning, involves choosing a potential solution, getting feedback on its quality, and then trying again to find a better solution.

This data-driven approach accelerated MILP solvers between 30 and 70% without any loss of accuracy. Additionally, the speedup was similar when they applied it 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 prove particularly difficult. Perhaps they could train the model on a smaller data set and then modify it to solve a much larger optimization problem, she says. Researchers also want to interpret the learned model to better understand the effectiveness of different separation algorithms.

The work is published on the arXiv preprint server.

This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and education.