Decision Making Under Uncertainty Using Machine Learning

Nous proposons un algorithme basé sur l'apprentissage supervisé pour obtenir de bonnes solutions primales pour les programmes stochastiques en deux étapes en nombres entiers (en anglais, two-stage stochastic integer programs - 2SIP). Le but de l'algorithme est de prédire un scénario représentatif (en anglais, representative scenario - RS) pour le problème tel qu'en résolvant de manière déterministe le 2SIP avec la réalisation aléatoire égale au scénario représentatif (en anglais, representative scenario (RS)), l'algorithme donne une solution quasi optimale au 2SIP original. Prédire un RS, au lieu de prédire directement une solution, garantit la faisabilité de la solution de première étape. Si le problème possède un recours complet, la réalisabilité de la deuxième étape est également garantie. Nous effectuons des expériences sur deux problèmes: le problème de localisation d'entrepôts avec capacité stochastique (en anglais, Stochastic Capacitated Facility Location Problem (S-CFLP)) et problème d'affectation généralisée stochastique (en anglais, Stochastic Generalized Assignment Problem (S-GAP)). Les deux problèmes ont des variables entières et des contraintes linéaires dans les première et deuxième étapes. La méthode proposée est capable de produire de bonnes solutions primales pour le S-CFLP lorsqu'elle est testée sur les tailles sur lesquelles elle a été entraînée. De plus, notre temps de calcul est compétitif par rapport à celui pris par Gurobi pour obtenir une qualité de solution similaire. Cependant, nos modèles ne sont pas capables de généraliser et de produire de bonnes solutions primales lorsqu'ils sont testés sur les tailles sur lesquelles ils n'ont pas été entraînés. Dans le cas de S-GAP, jusqu'à maintenant, notre méthode peine à trouver de bonnes solutions primales. Nous discutons des défis et des solutions potentielles que nous pourrions utiliser pour leur faire face.

Abstract

We propose a supervised learning based algorithm to obtain good primal solutions for twostage stochastic integer programming (2SIP) problems with constraints in the first and second stages. The goal of the algorithm is to predict a representative scenario for the problem such that, deterministically solving a two-stage stochastic integer program with the random realization equal to a representative scenario, gives a near-optimal solution to the original 2SIP. Predicting a representative scenario, instead of directly predicting a solution ensures first-stage feasibility of the solution. If the problem is known to have complete recourse, second-stage feasibility is also guaranteed. We perform computational tests on two problems, namely, the stochastic capacitated facility location problem (S-CFLP) and stochastic generalized assignment problem (S-GAP). Both the problems have integer variables and linear constraints in the first and second stages. The proposed method is able to produce good primal solutions for the S-CFLP when tested on the sizes on which it was trained. Also, our computing time is competitive to that taken by Gurobi to achieve a similar solution quality. However, our models are not able to generalize and produce good primal solutions when tested on the sizes on which they were not trained. In the case of stochastic generalized assignment problem, as of now, our method struggles to find good primal solutions. We discuss the challenges and the potential solutions we would be pursuing to alleviate them.