Séance de cours

Méthodes exactes pour l'optimisation d'entier

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente le concept de méthodes exactes pour l'optimisation des entiers, en se concentrant sur Branch et Bound. Il couvre des sujets tels que la formulation de problèmes d'optimisation d'entiers, la recherche de limites supérieures et inférieures, la division du problème en sous-problèmes et la représentation de l'arbre de solutions. À travers des exemples et des explications étape par étape, l'instructeur illustre comment Branch et Bound peuvent être appliqués pour résoudre efficacement les problèmes d'optimisation d'entiers.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Introduction au concept mathématique des réseaux et à deux importants problèmes d'optimisation sur les réseaux : le problème du transbordement et le problème du chemin le plus court. Brève introduction à la puissance de modélisation de l'optimisation discrète, avec référence à des problèmes classiques. Introduction à l'algorithme branch and bound et au concept de coupes.

Source officielle

Concepts associés (21)

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

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.

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.

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

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.

Afficher plus

Séances de cours associées (43)

Propriétés thermodynamiques : équations et modèles

Explique les propriétés thermodynamiques, les équations d'état et les règles de mélange pour la modélisation des systèmes énergétiques.

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 des systèmes de conversion d'énergie

Explore l'optimisation des systèmes de conversion d'énergie grâce à la récupération de chaleur et à la programmation linéaire mixte.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Physique statistique: Lunettes de spin et optimisation

Explore le modèle Curie-Weiss, les lunettes de spin et les problèmes d'optimisation en physique statistique.

Afficher plus

Concepts associés (21)

Optimisation (mathématiques)

Optimisation linéaire

Optimisation linéaire en nombres entiers

Optimisation combinatoire

Séparation et évaluation

Afficher plus