M?hodes de R?olution Hybrides Pour Les Probl?es de Type Knapsack

Dans cette th?se, nous nous int?ressons aux probl?mes du knapsack multidimensionnel ? choix multiple. Ils interviennent essentiellement en t?l?communication. Nous proposons de nouvelles m?thodes hybrides de r?solution exacte et approch?e. Dans un premier temps, nous proposons des m?thodes heuristiques en se basant sur les techniques de g?n?ration de colonnes et d'arrondi. Ensuite, nous abordons une m?thode de recherche locale, dite m?thode de branchement local, o? des contraintes lin?aires sont introduites pour intensifier et diversifier la recherche. Cette m?thode est ensuite hybrid?e avec la g?n?ration de colonnes et une technique d'arrondi. Concernant la r?solution exacte, nous nous basons sur une m?thode de "Branch and cut." Nous commen?ons par proposer de nouvelles contraintes valides pour le probl?me. Ensuite, nous les associons ? des contraintes de couverture locales et globales dans un sch?ma ?num?ratif. Les approches heuristiques et l'algorithme exact que nous proposons sont compar?s ? d'autres heuristiques de la litt?rature et au Solveur de programmes lin?aires Cplex.

Author: Cherfi-N

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 144 pages

Binding: Paperback or Softback

ISBN-10: 6131552207

ISBN-13: 9786131552205