Research Brief: Operations Research
Project Brief
Type of Research: Operations Research
Motivation for Research: Large combinatorial optimization problems involve an exponentially growing decision space, where finding a good solution often becomes extremely difficult using traditional optimization approaches, such as Mixed Integer Linear Programming (MILP), Evolutionary Algorithms and Handcrafted Heuristics, etc. Unfortunately, many real-world problems fall under the exponential decision space category. These range from planning for search and rescue missions to reconnaissance missions to holiday tours, among others. The recent advances in Artificial Intelligence (AI) instill hope to overcome some of these issues that are prevalent with existing approaches for solving combinatorial problems.
Machine Learning (ML), which is essentially a path to attain AI, involves learning heuristics and hidden representations from a large labeled or unlabeled dataset (often referred to as model training). In the last decade, ML approaches have gained huge traction owing to its success in a wide variety of tasks ranging from image classification to playing games at a superhuman level. Further, the recent breakthrough of ML approaches in Natural Language Processing (NLP) problems, such as language translation and image captioning, have inspired several ML approaches for real-world combinatorial optimization problems. Some of these approaches have also yielded better results in comparison to traditional heuristics.
Now, although the direct implementation of ML approaches to combinatorial problems can be a major game-changer considering the impressive compute time (few seconds) required at inferencing, they do have drawbacks. Firstly, in contrast to traditional optimization solver, ML models do not offer a measure of optimality, which makes it harder to assess the solution quality. Next, improving ML solutions using existing heuristic approaches only offer marginal improvements and does not guarantee the desired optimality gap. Lastly, ML solution tends to degrade on problem sizes far from training configuration. Therefore, ML models are unreliable in such situations. These are some of the issues believed to hinder progress for the wider adoption of ML approaches to solving real-world combinatorial optimization problems.
Research Approach
To address the existing shortcomings of ML and MILP optimization solvers, Prashant and Dr. Katie McConky developed a hybrid framework where ML and traditional state of the art MILP optimization solvers can coexist and complement each other to derive the desired solution quality and computing performance.
Further, they evaluated the developed framework on a variant of the team orienteering problem (TOP) using a new ML model architecture developed specifically to address the TOP instance and the results obtained are promising.
Now, they plan to evaluate the developed framework on other combinatorial optimization problems such as job scheduling and job assignment, among others. Lastly, they will perform a comparative study to determine the overall effectiveness of the framework against other traditional approaches.
Research Highlights
Some key observations from the preliminary study on a variant of the Team Orienteering Problem with the new ML model architecture include:
- The proposed ML model is robust to different problem configurations at inferencing.
- Warm starting MILP (Mixed Integer Linear Programming) solvers using ML significantly improves overall performance.
- The developed architecture successfully integrates ML with traditional MILP for improved solutions.
- The proposed architecture provides a fast-efficient solver for combinatorial optimization problems.