Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Branche et culot : Description officielle

Dans cours

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

Cette séance de cours porte sur l'algorithme Branch et Bound, en mettant l'accent sur la description officielle et les étapes de mise en oeuvre. Il explique comment initier et itérer l'algorithme, en trouvant des solutions entières optimales dans un polyèdre délimité. L'instructeur démontre comment Branch et Bound explorent efficacement l'espace de la solution, ce qui mène à la découverte de solutions entières approximatives.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Concepts associés (22)

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.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

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.

Polyèdre

Un polyèdre est une forme géométrique à trois dimensions (un solide géométrique) ayant des faces planes polygonales qui se rencontrent selon des segments de droite qu'on appelle arêtes. Le mot polyèdre, signifiant à plusieurs faces, provient des racines grecques πολύς (polys), « beaucoup » et ἕδρα (hedra), « base », « siège » ou « face ». Un polyèdre est un solide dont toutes les faces sont des polygones. Les côtés de ces polygones sont appelés arêtes. Les extrémités des arêtes sont des points appelés sommets.

Afficher plus

Séances de cours associées (31)

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Optimisation : Problèmes classiques

Couvre les problèmes classiques d'optimisation, les algorithmes de force brute et l'optimisation linéaire entière.

Algorithmes et croissance des fonctions

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Méthodes exactes : Branche et Liée MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore l'algorithme Branch et Bound dans une optimisation discrète, en trouvant efficacement des solutions optimales en calculant des limites inférieures sur des sous-ensembles.

Sans titre

Afficher plus

Concepts associés (22)

Séparation et évaluation

Feasible region

Algorithme

Optimisation linéaire en nombres entiers

Polyèdre

Afficher plus