Le probl?e du sac ?dos multidimensionnel

Le probl?me du sac ? dos ? plusieurs contraintes est un probl?me classique de l'optimisation appartenant ? la classe des probl?mes NP-difficiles. On le retrouve notamment sous la forme de sous-probl?me de nombreux probl?mes d'optimisation combinatoire. Les m?thodes classiques de r?solution exacte telles que la programmation dynamique ou le branch-and-bound ont ?t? trait?es abondamment dans la litt?rature. Elles pr?sentent n?anmoins des faiblesses si elles sont utilis?es telles quelles, d'o? l'id?e de faire coop?rer ces m?thodes en tirant profit de leurs sp?cificit?s afin de proposer soit des m?thodes heuristiques performantes, soit des m?thodes exactes plus efficaces. Les approches heuristiques que nous proposons sont compar?es ? d'autres heuristiques de la litt?rature. Notre m?thode coop?rative est, quant ? elle, compar?e ? un algorithme de branch-and-bound. L'ensemble de ces tests num?riques ont ?t? men?s pour diverses instances plus ou moins difficiles de la litt?rature ainsi que sur des instances engendr?es al?atoirement.

Author: Collectif

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 124 pages

Binding: Paperback or Softback

ISBN-10: 6131509964

ISBN-13: 9786131509964