Skip to Main content Skip to Navigation
Theses

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 metadatas

https://hal-uphf.archives-ouvertes.fr/tel-03046120
Contributor : Julie Cagniard <>
Submitted on : Tuesday, December 8, 2020 - 12:06:36 PM
Last modification on : Tuesday, December 15, 2020 - 3:31:58 AM

File

2009VALE0026_MANSI_RAID.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03046120, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

8