Predicting the Solution Time for Optimization Problems Using Machine Learning

In organizations that use optimization and other computer-related problem-solving techniques, a better understanding of the required computational time is essential for efficient decision-making and resource allocation which also directly affects productivity and operational effectiveness. This study proposes the application of various Machine Learning (ML) methods to predict the computation time needed to solve job shop problems. Specifically, we implemented 11 ML models, including the Deep Neural Network (DNN), which delivered the most accurate results. The proposed approach involves utilizing a DNN algorithm to predict computation time for Integer Programming (IP) job shop problems, trained on synthetically generated data that indicate the gap-time correlation in a branch and bound tree. The developed model in this study estimates the total computation time with an accuracy of 92%. The model development process involves collecting data from a set of solved problems using the branch and bound method and training the ML models to estimate the computational time required to reach the optimal solution in unsolved similar problems.