An Expandable Machine Learning-Optimization Framework to Sequential
  Decision-Making
Dogacan Yilmaz İ. Esra Büyüktahtakın
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.