Machine learning to support cutting plane selection in two-stage robust optimization problems using a column-and-constraint-generation algorithm

Abstract

The field of robust optimization deals with problems where uncertainty influences the optimal decision. Some of these problems can be formulated in a ‘two-stage’ formulation, such as the location transportation problem. To solve such a problem, a column-and-constraint-generation algorithm has been introduced in which constraints are iteratively added to mixed-integer pro- gram based on different uncertain scenarios. However, if these scenarios are randomly chosen, this problem can grow too large to efficiently solve for. For most problems, there is some mini- mal set of scenarios needed to find the optimal solution, and it is important to find the ‘right’ scenarios early. In this study, we attempt to predict these scenarios for a location transportation using machine learning. Using customer demand data for different instances of the problem, we train a logistic regression classifier, a neural network and a random forest classifier to predict important scenarios for newly generated problems. We find that when applying these machine learning tools, we reach an average reduction of scenarios added to the problem ranging from 8% to 24%. Even though we do not spend much effort on training perfect models, we see that there is a strong indication that machine learning can be used to increase the efficiency of the algorithm.