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.
