Decision Making Under Uncertainty Using Machine Learning

RESUME : Nous proposons un algorithme base sur l’apprentissage supervise pour obtenir de bonnes solutions primales pour les programmes stochastiques en deux etapes en nombres entiers (en anglais, two-stage stochastic integer programs - 2SIP). Le but de l’algorithme est de predire un scenario representatif (en anglais, representative scenario - RS) pour le probleme tel qu’en resolvant de maniere deterministe le 2SIP avec la realisation aleatoire egale au scenario representatif (en anglais, representative scenario (RS)), l’algorithme donne une solution quasi optimale au 2SIP original. Predire un RS, au lieu de predire directement une solution, garantit la faisabilite de la solution de premiere etape. Si le probleme possede un recours complet, la realisabilite de la deuxieme etape est egalement garantie. Nous effectuons des experiences sur deux problemes: le probleme de localisation d’entrepots avec capacite stochastique (en anglais, Stochastic Capacitated Facility Location Problem (S-CFLP)) et probleme d’affectation generalisee stochastique (en anglais, Stochastic Generalized Assignment Problem (S-GAP)). Les deux problemes ont des variables entieres et des contraintes lineaires dans les premiere et deuxieme etapes. La methode proposee est capable de produire de bonnes solutions primales pour le S-CFLP lorsqu’elle est testee sur les tailles sur lesquelles elle a ete entrainee. De plus, notre temps de calcul est competitif par rapport a celui pris par Gurobi pour obtenir une qualite de solution similaire. Cependant, nos modeles ne sont pas capables de generaliser et de produire de bonnes solutions primales lorsqu’ils sont testes sur les tailles sur lesquelles ils n’ont pas ete entraines. Dans le cas de S-GAP, jusqu’a maintenant, notre methode peine a trouver de bonnes solutions primales. Nous discutons des defis 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.