Déploiement et mise à jour de coupes de concavité

Dans le cadre de minimisation concave, un type de problème d'optimisation quadratique, nommé bilinéaire disjoint (BILD), peut se reformuler en deux problèmes linéaires symétriques MinMax (LMM). Comme les solutions optimales de BILD et de ses reformulations LMM sont liées par une simple bijection, la question de notre travail de recherche s'agit profiter de cette reformulation pour résoudre BILD. Dans la littérature, une technique de calcul, appelée coupe de concavitée, proposée par Tuy [39] en 1964, s'avère importante afin de résoudre les BILD. L'algorithme basé uniquement sur cette technique n'est pas sûrement de convergence finie. Cela est dû à plusieurs problèmes, parmi lesquels nous citons : le problème de dégénérescene et le problème de cumul des coupes. Depuis, des chercheurs tentent d'améliorer la convergence de l'algorithme des plans coupants. Pour ce faire, ils ont intégré cet algorithme avec d'autres techniques de calcul. En effet, Konno [23] a introduit la technique Mountain Climbing en 1971 pour évaluer à chaque itération une solution locale. Avec l'usage des pseudo-sommets, Marcus [34] a developpé en 1999 des coupes similaires à celles de Tuy en décomposant le cône polyèdral. En 2001, Alarie et al. ont traité le problème de dégénérescence et ont exploité la technique de "Branch and Bound" pour les instances BILD de grande dimension. La recherche proposée dans ce mémoire se situe dans la continuation de ces travaux. Nous proposons deux nouvelles stratégies pour la génération de coupes de concavité. Dans la première, nous avons élaboré une mise à jour dynamique des coupes après qu'une améioration de la valeur objectif soit faite. Dans la seconde, au lieu que les coupes soient associées à des sommets, nous les avons associées aux pseudo-sommets. Ces deux nouvelles stratégies sont testées numériquement sur un ensemble de problèmes tests tirés de la littérature ainsi que sur une collection de problèmes générés aléatoirement.