An expandable machine learning-optimization framework to sequential decision-making

Dogacan Yilmaz, Esra Büyüktahtakın

Research output: Contribution to journalArticlepeer-review

Abstract

We present an integrated prediction-optimization (PredOpt) framework to efficiently solve sequential decision-making problems by predicting the values of binary decision variables in an optimal solution. We address the key issues of sequential dependence, infeasibility, and generalization in machine learning (ML) to make predictions for optimal solutions to combinatorial problems. The sequential nature of the combinatorial optimization problems considered is captured with recurrent neural networks and a sliding-attention window. We integrate an attention-based encoder–decoder neural network architecture with an infeasibility-elimination and generalization framework to learn high-quality feasible solutions to time-dependent optimization problems. In this framework, the required level of predictions is optimized to eliminate the infeasibility of the ML predictions. These predictions are then fixed in mixed-integer programming (MIP) problems to solve them quickly with the aid of a commercial solver. We demonstrate our approach to tackling the two well-known dynamic NP-Hard optimization problems: multi-item capacitated lot-sizing (MCLSP) and multi-dimensional knapsack (MSMK). Our results show that models trained on shorter and smaller-dimensional instances can be successfully used to predict longer and larger-dimensional problems. The solution time can be reduced by three orders of magnitude with an average optimality gap below 0.1%. We compare PredOpt with various specially designed heuristics and show that our framework outperforms them. PredOpt can be advantageous for solving dynamic MIP problems that need to be solved instantly and repetitively.

Original languageEnglish (US)
Pages (from-to)280-296
Number of pages17
JournalEuropean Journal of Operational Research
Volume314
Issue number1
DOIs
StateAccepted/In press - 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • (R) Machine learning
  • Capacitated lot-sizing
  • Combinatorial optimization
  • Encoder–decoder
  • Knapsack

Fingerprint

Dive into the research topics of 'An expandable machine learning-optimization framework to sequential decision-making'. Together they form a unique fingerprint.

Cite this