Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Метод оптимизации для решения (смешанных) целых линейных программ
Optimization technique for solving (mixed) integer linear programs
В математической оптимизации метод секущих плоскостей – это любой из ряда методов оптимизации, которые итеративно уточняют допустимое множество или целевую функцию посредством линейных неравенств, называемых секущими плоскостями. Такие процедуры обычно используются для нахождения целочисленных решений задач смешанного целочисленного линейного программирования (MILP), а также для решения общих, не обязательно дифференцируемых, выпуклых задач оптимизации. Использование секущих плоскостей для решения MILP было введено Ральфом Э. Гомори. Методы секущих плоскостей для MILP работают путем решения нецелочисленной линейной программы, являющейся линейным релаксом исходной целочисленной программы. Теория линейного программирования утверждает, что при умеренных предположениях (если линейная программа имеет оптимальное решение и если допустимая область не содержит прямую линию), всегда можно найти крайнюю или угловую точку, являющуюся оптимальной. Полученное оптимальное решение проверяется на целочисленность. Если оно не является целочисленным, гарантированно существует линейное неравенство, отделяющее оптимальное решение от выпуклой оболочки истинного допустимого множества. Нахождение такого неравенства – это задача разделения, а само неравенство – секущая плоскость. Секущую плоскость можно добавить к релаксированной линейной программе. Тогда текущее нецелочисленное решение перестает быть допустимым для релаксации. Этот процесс повторяется до тех пор, пока не будет найдено оптимальное целочисленное решение. Методы секущих плоскостей для общей выпуклой непрерывной оптимизации и их варианты известны под различными названиями: метод Келли, метод Келли–Чейни–Голдштейна и методы пучков. Они широко используются для недифференцируемой выпуклой минимизации, где выпуклая целевая функция и ее субградиент могут быть эффективно вычислены, но обычные градиентные методы для дифференцируемой оптимизации неприменимы. Такая ситуация наиболее типична для вогнутой максимизации двойственных функций Лагранжа. Другая распространенная ситуация – применение декомпозиции Данцига–Вольфа к структурированной задаче оптимизации, в результате которой получаются формулировки с экспоненциальным числом переменных. Генерация этих переменных по требованию посредством отложенной генерации столбцов эквивалентна применению секущей плоскости к соответствующей двойственной задаче.
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.
История
Расколотые плоскости были предложены Ральфом Гомори в 1950-х годах как метод решения задач целочисленного и смешанного целочисленного программирования. Однако большинство экспертов, включая самого Гомори, считали их непрактичными из-за численной неустойчивости, а также неэффективными, поскольку для продвижения к решению требовалось множество итераций добавления сечений. Ситуация изменилась в середине 1990-х годов, когда Жерар Корнюжоль и его коллеги показали их высокую эффективность в сочетании с методом ветвей и границ (известным как ветви и отсечения) и способами преодоления численной неустойчивости. В настоящее время все коммерческие решатели MILP используют сечения Гомори в той или иной форме. Сечения Гомори очень эффективно генерируются из симплекс-таблицы, в то время как выделение многих других типов сечений либо вычислительно затратно, либо даже NP-трудно. Среди других общих сечений для MILP, наиболее заметными являются методы "подъёма и проекции", которые превосходят сечения Гомори.
Cutting planes were proposed by Ralph Gomory in the 1950s as a method for solving integer programming and mixed integer programming problems. However, most experts, including Gomory himself, considered them to be impractical due to numerical instability, as well as ineffective because many rounds of cuts were needed to make progress towards the solution. Things turned around when in the mid 1990s Gérard Cornuéjols and co workers showed them to be very effective in combination with branch and bound (called branch and cut) and ways to overcome numerical instabilities. Nowadays, all commercial MILP solvers use Gomory cuts in one way or another. Gomory cuts are very efficiently generated from a simplex tableau, whereas many other types of cuts are either expensive or even NP hard to separate. Among other general cuts for MILP, most notably lift and project dominates Gomory cuts.
Общая идея
Метод заключается в том, что сначала снимается требование, чтобы значения xi были целыми числами, и решается соответствующая задача расслабленного линейного программирования для получения базисного допустимого решения. Геометрически, это решение будет вершиной выпуклого многогранника, состоящего из всех допустимых точек. Если эта вершина не является точкой с целыми координатами, то метод находит гиперплоскость, с одной стороны которой находится вершина, а с другой – все допустимые точки с целыми координатами. Затем это добавляется как дополнительное линейное ограничение для исключения найденной вершины, что приводит к модифицированной задаче линейного программирования. Новая задача затем решается, и процесс повторяется до тех пор, пока не будет найдено целочисленное решение.
The method proceeds by first dropping the requirement that the xi be integers and solving the associated relaxed linear programming problem to obtain a basic feasible solution. Geometrically, this solution will be a vertex of the convex polytope consisting of all feasible points. If this vertex is not an integer point then the method finds a hyperplane with the vertex on one side and all feasible integer points on the other. This is then added as an additional linear constraint to exclude the vertex found, creating a modified linear program. The new program is then solved and the process is repeated until an integer solution is found.