Méthode de Branch and Bound pour la résolution d’un problème de minimisation concave

Abstract

Dans ce mémoire, l’objectif est de présenter une méthode de résolution d’un problème de minimisation concave qui est la méthode de Séparation et d’Evaluation (Branch and Bound method). On a considéré le cas où la fonction objectif est quadratique concave et les contraintes linéaires. Pour ce faire, nous avons commencé par présenter quelques définitions des éléments de base pour la résolution des problèmes d’optimisation, et nous avons aussi présenté la méthode de Branch and Bound. Ensuite, nous nous sommes intéressons à la résolution des problèmes de programmation linéaire en nombres entiers par la méthode de Séparation et d’ évaluation. La dernière partie est consacrée à la minimisation d’une fonction quadratique concave sur un polytope. Enfin, on a présenté l’algorithme de la méthode de Branch and Bound, appliqué à la minimisation concave et nous avons fini par l’appliquer sur un exemple illustratif. The aim of this work is to present a method of solving the problem of concave minimization, the Branch and Bound Method. We consider the case where the objective function is quadratic and the linear constraints. To do this, we begin by presenting some definitions of the basic elements for solving optimization problems, and we also present the Branch and Bound Method. Next, we are interested in solving integer linear programming problems by the method of Branch and Bound. The last part is devoted to the minimization of a concave quadratic function over a polytope. Finally, we present the algorithm of the Branch and Bound applied to concave minimization, and we end up applying it on one illustrative example.