Skip to Main content Skip to Navigation

Approches hybrides pour des variantes du sac à dos et applications

Abstract : In this thesis, we propose new methods hybridizing dynamic programming and integer programming exact methods to solve bilevel knapsack problems. The numerical experiments show that our algorithms are robust and surpass significantly the algorithms of the literature. Iterative hybrid heuristics based on relaxations are designed for solving multiple-choice multidimensional knapsack problem. These heuristics converge theoretically towards an optimal solution of the problem by solving a series of sub problems of small size produced by exploiting the information of relaxations. Our methods are enriched by using fixation and by the addition of cuts and pseudo-cuts induced by local search and relaxations. These added constraints are used to reduce the search space. The results show that the heuristics converge quickly to good solutions and provide 13 new better values from 33 instances of the literature. Lastly, an oscillation strategy combining the mathematical programming and constructive and destructive heuristics is proposed to solve a real problem for the management of disruptions in the air industry. Our approach was ranked second of an international challenge.
Complete list of metadata
Contributor : Julie Cagniard Connect in order to contact the contributor
Submitted on : Tuesday, December 8, 2020 - 12:06:36 PM
Last modification on : Tuesday, November 23, 2021 - 9:44:53 AM
Long-term archiving on: : Tuesday, March 9, 2021 - 7:10:56 PM


Files produced by the author(s)


  • HAL Id : tel-03046120, version 1


Raïd Mansi. Approches hybrides pour des variantes du sac à dos et applications. Informatique [cs]. Université de Valenciennes et du Hainaut-Cambrésis, 2009. Français. ⟨NNT : 2009VALE0026⟩. ⟨tel-03046120⟩



Record views


Files downloads