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.