Santa Claus can deliver presents worldwide in one night, but for companies like FedEx, this task isn’t so simple – and it is so complex, dedicated software is often used to solve it. Known as a mixed-integer linear programming (MILP) solver, the software breaks down this vast optimization problem into smaller pieces and then employs algorithms to find the best solution. However, it can still take hours or even days for the software to arrive at a solution, often leading companies to stop it partway and settle for the best solution found within a fixed time limit.
Researchers from MIT and ETH Zurich used machine learning to speed up this process. First, they pinpointed a key intermediate step in the MILP solver that has many potential solutions and slows the whole process down. After that, they applied a filtering technique to simplify this step and then used machine learning to find the optimal solution for a specific type of problem.
The machine learning-driven approach resulted in a 30 to 70% faster performance with the same degree of accuracy, meaning the software can find better solutions more quickly, or at least, more efficiently. The researchers suggest that this approach could be used wherever MILP solvers are employed, including ride-hailing services, electric grid operators, and distributors of vaccinations, to name just a few examples.
The challenging nature of optimization problems can lead some to believe that the solutions are either purely machine learning or classic, but this novel approach combines the best of both worlds for maximum efficiency. The software uses a problem-splitting approach called branching and uses another method, known as cutting, to make the problem pieces ready for efficient searches. The researchers discovered that finding the best combination of algorithms – or separators – to use is a task riddled with an exponential number of solutions.
To conquer this complexity, the team created a filtering mechanism to reduce this search space from over 130,000 potential combinations to around just 20. Then, they used a machine-learning model to select the most effective combination of algorithms from these 20 remaining options. This approach uses a company’s own data to train the model, resulting in highly specific problem-solving born from real-world experience rather than starting from scratch every time.
In future, these researchers aim to apply this hybrid approach to even more complex MILP problems. One possible method is to train the model on a smaller dataset and then adjust it to tackle a larger optimization problem. The more they understand about the effectiveness of various separator algorithms, the better equipped they’ll be to tackle exceedingly complex optimization problems. Funding for this research was provided by several prominent entities, including Mathworks, the National Science Foundation, the MIT Amazon Science Hub, and the MIT Research Support Committee.
