AI accelerates problem solving in complex scenarios

Even though Santa Claus has a magical sleigh and nine brave reindeer to assist him deliver presents, the optimization problem of efficiently routing holiday packages is so complicated for firms like FedEx that they often use specialized software to seek out an answer.

This software, MILP (Mixed-Integer Linear Programming) solver, breaks a big optimization problem into smaller parts and uses generic algorithms to seek out the very best solution. However, it could take hours and even days for the solver to reach at an answer.

The process is so laborious that an organization often has to stop the software midway through and accept an answer that, while not ideal, is the very best that may very well be generated in a given period of time.

Researchers from MIT and ETH Zurich used machine learning to hurry things up.

They identified a very important intermediate step in MILP solvers that provides so many potential solutions that deciphering them takes an infinite period of time, slowing down the complete process. To simplify this step, the researchers used a filtering technique after which used machine learning to seek out the optimal solution for a selected kind of problem.

Their data-driven approach allows an organization to make use of its own data to tailor a general-purpose MILP solver to the issue at hand.

This latest technique accelerated MILP solvers by 30 to 70 percent without sacrificing accuracy. This method may very well be used to reach at an optimal solution more quickly or, within the case of particularly complex problems, to a greater solution in a manageable period of time.

This approach may very well be used anywhere MILP solvers are deployed, akin to ride-hailing services, electric grid operators, vaccination distributors, or other firms facing a thorny resource allocation problem.

“In a field like optimization, it sometimes happens that solutions are regarded as either purely machine learning or purely classical. I’m an enormous believer in wanting to get the very best of each worlds, and this can be a really strong implementation of that hybrid approach,” says lead writer Cathy Wu, the Gilbert W. Winslow Career Development Assistant Professor in Civil and Environmental Engineering ( CEE) and member of a member of the Laboratory for Information and Decision Systems (LIDS) and the Institute for Data, Systems, and Society (IDSS).

Wu wrote this Paper with co-lead authors Sirui Li, an IDSS doctoral student, and Wenbin Ouyang, a CEE doctoral student; and Max Paulus, a doctoral student at ETH Zurich. The research will likely be presented on the Conference on Neural Information Processing Systems.

Difficult to resolve

MILP problems have an exponential variety of possible solutions. Suppose a traveling salesman desires to visit several cities via the shortest route after which return to his home city. If there have been many cities that may very well be visited in any order, the variety of possible solutions may very well be greater than the variety of atoms within the universe.

“These problems are called NP-hard, meaning that it is vitally unlikely that there may be an efficient algorithm to resolve them. If the issue is large enough, we will only hope to attain suboptimal performance,” Wu explains.

A MILP solver uses a series of techniques and handy tricks that may produce meaningful solutions in a manageable period of time.

A typical solver uses a divide-and-conquer approach, where the space of potential solutions is first divided into smaller pieces using a way called bifurcation. Then the solver uses a way called “cutting” to streamline these smaller pieces in order that they may be searched more quickly.

Slicing uses a algorithm that reduce the search space without removing possible solutions. These rules are generated by a number of dozen algorithms, called separators, created for various kinds of MILP problems.

Wu and her team found that the means of identifying the best combination of separation algorithms is itself an issue with an exponential variety of solutions.

“Separator management is a core a part of any solver, but that is an underappreciated aspect of the issue space. One of the contributions of this work is to first discover the issue of separator management as a machine learning task,” she says.

Reduction of the answer space

She and her colleagues have developed a filtering mechanism that reduces this separation search space from greater than 130,000 possible combos to about 20 options. This filtering mechanism relies on the principle of diminishing marginal returns, which states that the best profit would come from a small set of algorithms and adding additional algorithms wouldn’t provide much additional improvement.

They then use a machine learning model to pick out the very best combination of algorithms from the 20 remaining options.

This model is trained on an information set specifically tailored to the user’s optimization problem, learning to pick out algorithms which might be best suited to the user’s specific task. Since an organization like FedEx has solved routing problems again and again, using real data from previous experiences should lead to higher solutions than ranging from scratch each time.

The model’s iterative learning process, often known as contextual bandits, a type of reinforcement learning, involves choosing a possible solution, getting feedback on how good it was, after which trying again to seek out a greater solution.

This data-driven approach accelerated MILP solvers by 30 to 70 percent without sacrificing accuracy. Furthermore, the speedup was similar when applied to a less complicated open source solver and a more powerful business solver.

In the longer term, Wu and her collaborators need to apply this approach to much more complex MILP problems, where collecting labeled data to coach the model may very well be particularly difficult. Maybe they will train the model on a smaller data set after which tune it to tackle a much larger optimization problem, she says. Researchers are also thinking about interpreting the learned model to higher understand the effectiveness of various separation algorithms.

This research is supported partly by Mathworks, the National Science Foundation (NSF), the MIT Amazon Science Hub, and MIT’s Research Support Committee.