Méthode des plans sécants

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique théorique
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plan method, est une méthode utilisée pour trouver une solution entière d'un problème d'optimisation linéaire. Elle fut introduite par Ralph E. Gomory (en) puis étudié par Gomory et Václav Chvátal.

Principe[modifier | modifier le code]

Le principe de la méthode est d'ajouter des contraintes au programme linéaire pour le raffiner, et le rapprocher des solutions intégrales[1]. Plus précisément, étant donné un ensemble de contrainte, et une solution optimale x* au problème d'optimisation linéaire, la méthode consiste à créer de nouvelles contraintes, telle que la solution entière optimale est conservé, mais x* viole l'une des nouvelles contraintes[2].

Notes et références[modifier | modifier le code]

  1. « Integer Programming : Cutting Planes », dans Applied Mathematical Programming,‎ (lire en ligne).
  2. Michela Milano et Michael Trick, Constraint and integer programming, Springer,‎ (lire en ligne), p. 20

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]