Contribution à la résolution du sac-à-dos à contraintes disjonctives
Mohamed Elhavedh Ould Ahmed Mounir · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
The disjunctively constrained Knapsak problem (DCKP) is a variant of the KnapSack problem with some sets of incompatible items. DCKP, a integer linear program, is an NP-hard combinatorial optimization problem, it arises either as stand alone problem or as a component of more difficult combinatorial optmization problems. Its induced structure in complex problems allows the computation of upper bounds and the design of heuristic and exact methods for these complex instances.