Méthodes exactes : Branche et Liée

Description

Cette séance de cours traite de l'algorithme Branch and Bound en optimisation discrète, qui relève le défi d'explorer un vaste ensemble de solutions réalisables en le divisant en sous-ensembles plus petits et en sélectionnant la meilleure solution. L'algorithme trouve efficacement des solutions optimales en calculant des limites inférieures sur des sous-ensembles, évitant ainsi la nécessité de résoudre exactement tous les sous-problèmes. En tirant parti de ces limites inférieures, l'algorithme Branch and Bound s'avère optimal sans résoudre tous les sous-problèmes, ce qui le rend particulièrement utile pour les grands ensembles réalisables. Dans le contexte de problèmes linéaires entiers mixtes, les limites inférieures peuvent être calculées en résolvant le problème de relaxation à laide de lalgorithme simplex.

Connectez-vous pour regarder la vidéo

Dans MOOCs (6)

Enseignant

Source officielle

https://mediaspace.epfl.ch/media/0_493dih1p

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Séances de cours associées (45)

Concepts associés (19)

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.

Séparation et évaluation

Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum.

Feasible region

In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.