Researchers at MIT and ETH Zurich are turning heads in the tech world after they’ve engineered a smarter way to handle complex optimization problems, which could greatly benefit sectors like logistics and energy. Their innovative method, which utilizes machine learning, promises to accelerate the problem-solving capabilities of algorithms used in planning and operations—something the industry’s heavy hitters like FedEx could capitalize on to optimize global package routing, especially during the peak holiday seasons.
Currently, mixed-integer linear programming (MILP) solvers, which are a staple in solving these large-scale optimization scenarios, work overtime to churn out feasible solutions. The downside, as detailed in a paper set to be presented at the Conference on Neural Information Processing Systems and as explained by a statement obtained by MIT News, can often entail hours or days of computation. The MIT-ETH team, led by Cathy Wu, the Gilbert W. Winslow Career Development Assistant Professor in Civil and Environmental Engineering, appears to have found a way to cut down on those hours significantly.
Wu, along with Siriu Li, Wenbin Ouyang, and Max Paulus, identified an intermediate step in the MILP solver process. It usually represents a gigantic web of potential solutions. By introducing a filtering technique to whittle down this step, the researchers have used machine learning to pinpoint the optimal approach for nuanced problems.
"Sometimes, in a field like optimization, it is very common for folks to think of solutions as either purely machine learning or purely classical. I am a firm believer that we want to get the best of both worlds, and this is a really strong instantiation of that hybrid approach," Cathy Wu told MIT News. The team’s results showed a 30 to 70 percent speed boost in solving times.
Going beyond mere academic theory, this could potentially revolutionize how companies, including ride-hailing services and electric grid operators, tackle their daily resource-allocation conundrums. The MIT-ETH consortium’s method shrinks the solution space by applying a filtration mechanism that trims potential algorithmic combinations from a staggering 130,000 to a mere handful. From there, a machine learning model takes the stage, tailor-made for a company's unique data set, and thus improving solutions even further based on historical data.
The implications of their work, supported by entities such as Mathworks and the National Science Foundation, extend to an array of industries dealing with NP-hard problems—that is, conundrums that traditionally have resisted expedient and effective algorithmic answers. The research team is, according to the MIT News release, looking to push their method to tackle even hairier MILP problems in the future. If their machine-learning model could be adapted from small to large-scale issues, this would decidedly mark a new trajectory in computational problem-solving—one that businesses with an eye on the clock and their bottom line are likely to follow with great interest.
