Supposons que l'on a un budget destiné à investir sur un ensemble de projets. Chaque projet est caractérisé par deux facteurs : le coût et le profit que le projet pourrait apporter. Le problème est de choisir un sous-ensemble de projets maximisant le profit total tel que le coût total soit inférieur ou égal au budget. On suppose en plus que le coût donné d'un projet n'est qu'une estimation du coût final qui pourrait être différent à l'achèvement du projet. Ce problème peut être considéré comme un problème de sac-à-dos stochastique où on a un ensemble N={1,2,…,n} de n éléments (projets) dont chacun a une utilité (profit) fixe mais de poids (coût) aléatoire. Etant donné un seuil de probabilité ϵ et pour S⊆N, soit P(S) la probabilté que poids total des éléments sélectionnés dépasse la capacité du sac-à-dos. Le problème de sac-à-dos stochastique est de choisir un sous-ensemble S de N maximisant le profit total tel que P(S)< ϵ.
Nous considérons le cas où le poids de l’élément j suit la loi normale avec une moyenne a_j et une variance σ_j indépendamment des autres éléments. Dans ce cas le problème peut être modélisé comme
soit un programme 0/1 sur le cône du second ordre,
soit un programme 0/1 sous contrainte quadratique.
Le premier dont la relaxation continue est convexe, peut être résolu directement avec Gurobi. Le deuxième dont relaxation continue n’est pas convexe, nécessite une linéarisation de la contrainte quadratique pour être résolu directement avec Gurobi.
Le projet consiste en
Génération un jeu d’instances du problème sac-à-dos stochastique
Ecrire un programme de résolution du modèle programme 0/1 sur le cône du second ordre avec Gurobi. Vous n'avez pas à comprendre la programmation du second ordre, juste à spécifier la contrainte et donner à Gurobi.
Ecrire un programme effectuant la linéarisation de la contrainte quadratique avec au moins deux méthode alternatives : la linéarisation de Fortet et celle de Sherali-Smith et résolvant le programme linéaire 0/1 obtenu avec Gurobi
Comparaisons par expériences numériques les différentes approches de résolution ci-dessus.
Effectif demandé : 2 étudiants.
Langage de programmation : à choisir entre C++, Java et Python.
Références :
Pour la définition du problème : Chance constrained knapsack problem with random item sizes,
V. Goyal, R. Ravi, technical report, Tepper School of Business, CMU, 2009.
Pour les méthods de linéarisation : Voir avec l’encadrant.
Contact : Hung.Nguyen@lip6.fr