In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

PropertyValue
dbpprop:abstract
  • In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory. Cutting plane methods for MILP work by solving a non-integer linear program, the linear relaxation of the given integer program. The obtained optimum is tested for being an integer solution. If it is not, there is guaranteed to exist a linear inequality that separates the optimum from the convex hull of the true feasible set. Finding such an inequality is the separation problem, and such an inequality is a cut. A cut can be added to the relaxed linear program to cut off the current non-integer solution. This process is repeated until an optimal integer solution is found. Cutting-plane methods for general convex continuous optimization and variants are known under various names: Kelley's method, Kelley-Cheney-Goldstein method, and bundle methods. They are popularly used for non-differentiable convex minimization, where a convex objective function and its subgradient can be evaluated efficiently but usual gradient methods for differentiable optimization can not be used. This situation is most typical for the concave maximization of Lagrangian dual functions. Another common situation is the application of the Dantzig-Wolfe decomposition to a structured optimization problem in which formulations with an exponential number of variables are obtained. Generating these variables on demand by means of delayed column generation is identical to performing a cutting plane on the respective dual problem.
  • Ein Schnittebenenverfahren (engl. cutting plane algorithm) ist in der angewandten Mathematik ein Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme. Die Grundidee besteht darin, statt eines ganzzahligen linearen Programms seine LP-Relaxierung (also ohne Ganzzahligkeitsbedingungen) zu betrachten und diese durch Hinzufügung weiterer Ungleichungen schrittweise zu verschärfen, bis (im Idealfall) eine ganzzahlige Lösung gefunden wird. Das in den 1950er Jahren u. a. von Delbert Ray Fulkerson, George Dantzig und Ralph Gomory entwickelte Verfahren ist mit seinen Weiterentwicklungen heute eine der Standardmethoden in der ganzzahligen Optimierung und weiterhin Gegenstand aktueller Forschung. Als alleiniges Lösungsverfahren ist es meist nicht ausreichend, liefert aber gute duale Schranken für die zu lösenden Optimierungsprobleme. Daher wird es oft mit Branch-and-Bound zum sogenannten Branch-and-Cut-Verfahren kombiniert.
  • En matemática, y más en concreto en optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory. Funciona resolviendo un programa lineal no entero, después comprobando si la optimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución no entera pero no corta ningún otro punto de la región factible. Esto se repite hasta que se encuentra la solución entera óptima <math>X^*\,</math>. Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano.
  • En mathématiques, et spécialement en optimisation, la méthode des plans sécants est une méthode utilisée pour trouver une solution entière d'un programme linéaire. Elle fut introduite par Ralph E. Gomory.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.
  • Ein Schnittebenenverfahren (engl. cutting plane algorithm) ist in der angewandten Mathematik ein Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme. Die Grundidee besteht darin, statt eines ganzzahligen linearen Programms seine LP-Relaxierung (also ohne Ganzzahligkeitsbedingungen) zu betrachten und diese durch Hinzufügung weiterer Ungleichungen schrittweise zu verschärfen, bis (im Idealfall) eine ganzzahlige Lösung gefunden wird. Das in den 1950er Jahren u. a.
  • En matemática, y más en concreto en optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory. Funciona resolviendo un programa lineal no entero, después comprobando si la optimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución no entera pero no corta ningún otro punto de la región factible.
  • En mathématiques, et spécialement en optimisation, la méthode des plans sécants est une méthode utilisée pour trouver une solution entière d'un programme linéaire. Elle fut introduite par Ralph E. Gomory.
rdfs:label
  • Cutting-plane method
  • Schnittebenenverfahren
  • Método de planos de corte
  • Plans sécants
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of