Résolution du problème du multi-sac-à-dos quadratique en variables entières
Institution:
Paris 9Disciplines:
Directors:
Abstract EN:
This thesis deals with the integer quadratic multi-knapsack problem (QMKP). This problem is NP-hard. We first study a special case of (QMKP): the integer quadratic multi-knapsack problem where the objective function is concave and separable. In this context, we develop a branch-and-bound algorithm to solve (QMKP) to optimality. This method is based on the computation of a tight upper bound for (QMKP) which is derived from a linearization and a surrogate relaxation. Our branch-and-bound also incorporates pre-processing procedures. The computational performance of our branch-and-bound is compared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization method originally applied to the separable quadratic knapsack problem with a single constraint that we extend to the case of m constraints, a standard branch-and-bound algorithm (Cplex9. 0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints in 5 minutes). Finally, we suggest a theoretical approach to solve the problem (QMKP) where the objective function is concave and non separable. We transform the non separable problem into a separable in order to be able to apply our branch-and-bound for the separable case in this context.
Abstract FR:
L’objet de cette thèse est la résolution d’un problème d’optimisation combinatoire discrète, le problème du multi-sac-à-dos quadratique en variables entières, que nous notons (QMKP). Ce problème est NP-difficile. Nous étudions, dans un premier temps, un cas particulier du problème (QMKP) : le problème du multi-sac-à-dos quadratique en variables entières dont la fonction économique est concave et séparable. Dans ce contexte, nous élaborons une méthode exacte de recherche arborescente par séparation et évaluation pour le résoudre. Cette dernière repose sur le calcul d’un majorant fin de la valeur optimale de (QMKP). Ce majorant provient d’une méthode basée sur une linéarisation et une relaxation agrégée du problème initial. Notre branch-and-bound incorpore également des procédures de pré-traitement en amont. Nous comparons les performances, en terme de temps de calcul et de qualité, de notre approche avec trois autres méthodes existantes : un algorithme de branch-and-bound développé par Djerdjour et al. (1988), une formulation linéarisée en variables 0-1 (initialement utilisée pour résoudre le sac-à-dos quadratique mono-contraint en variables entières que nous avons étendu au cas multi-contraint), un branch-and-bound classique (optimisation quadratique Cplex9. 0). Notre branch-and-bound est clairement le plus performant nous permettant de résoudre des problèmes de grandes tailles (jusqu’à 2000 variables et contraintes) en moins de 5 minutes en moyenne. Dans un deuxième temps, nous étendons nos recherches au cas où la fonction économique du problème (QMKP) est concave et non séparable. Nous proposons alors une voie théorique de résolution de ce problème basée sur une transformation du problème non séparable en un problème séparable. Nous sommes alors en mesure de lui appliquer notre algorithme développé pour résoudre (QMKP) séparable et ainsi de fournir l’optimum entier de ce problème.