| dbo:abstract
|
- In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly 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 theory of Linear Programming dictates that under mild assumptions (if the linear program has an optimal solution, and if the feasible region does not contain a line), one can always find an extreme point or a corner point that is optimal. 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. Then, the current non-integer solution is no longer feasible to the relaxation. 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. (en)
- 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-Relaxation (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 später von Egon Balas 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. (de)
- 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 . 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 . Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo solo soluciones en uno de los lados del plano. (es)
- En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plane 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 puis étudiée par Gomory et Václav Chvátal. (fr)
- Em Pesquisa Operacional, o método de planos de corte é um método exato para Programação linear que busca iterativamente refinar um conjunto viável ou função objetivo por meio de inequações lineares, chamadas cortes. Tais procedimentos são utilizados para encontrar soluções inteiras para problemas de Programação Linear Inteira (PLI), bem como para resolver problemas gerais de otimização convexa. O uso de planos de corte para resolver PLI foi introduzido por Ralph Gomory. (pt)
- Алгоритм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм разработан в 1950-х годах американским математиком Ральфом Гомори. (ru)
- 在数学优化中，切割平面法是通过线性不等式对或目标函数进行迭代性优化（即切割）的优化方法的涵盖性术语。该过程通常用来发现（MILP）问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。 MILP 的切割平面法通过将整数问题为非整数线性问题，并对其进行求解，来求解 MILP 问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。 用于普遍的凸连续优化和变体的切割平面法有不同的名称： Kelley 法， Kelley-Cheney-Goldstein 法和捆绑法。它们常用于不可微的凸最小化问题。对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。这种情况最常出现在双拉格朗日函数的凹优化中。另一种常见情形是 Dantzig-Wolfe 分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9328 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
|
- May 2022 (en)
- November 2019 (en)
|
| dbp:reason
|
- First: this is rather technical detail of the simplex algorithm, which cannot be presumed known to readers of this article. Second: this appears to presume an equality Ax=b formulation of the linear program rather than the inequality Ax≤b form used above, and that transformation will introduce extra variables. Do we know those have to be integer-valued? Third: do we even need to distinguish basic and nonbasic variables?? (en)
- An explanation would be interesting, as it would make the statement feel less opinionated. (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plane 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 puis étudiée par Gomory et Václav Chvátal. (fr)
- Em Pesquisa Operacional, o método de planos de corte é um método exato para Programação linear que busca iterativamente refinar um conjunto viável ou função objetivo por meio de inequações lineares, chamadas cortes. Tais procedimentos são utilizados para encontrar soluções inteiras para problemas de Programação Linear Inteira (PLI), bem como para resolver problemas gerais de otimização convexa. O uso de planos de corte para resolver PLI foi introduzido por Ralph Gomory. (pt)
- Алгоритм Го́мори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм разработан в 1950-х годах американским математиком Ральфом Гомори. (ru)
- 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-Relaxation (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. (de)
- In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly 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. (en)
- 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 . 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 . (es)
- 在数学优化中，切割平面法是通过线性不等式对或目标函数进行迭代性优化（即切割）的优化方法的涵盖性术语。该过程通常用来发现（MILP）问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。 MILP 的切割平面法通过将整数问题为非整数线性问题，并对其进行求解，来求解 MILP 问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。 (zh)
|
| rdfs:label
|
- Schnittebenenverfahren (de)
- Método de planos de corte (es)
- Cutting-plane method (en)
- Méthode des plans sécants (fr)
- Алгоритм Гомори (ru)
- Método de planos de corte (pt)
- 切割平面法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
