Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Column generation (en)
- Génération de colonnes (fr)
- Генерация столбцов (ru)
|
| rdfs:comment
| - En informatique théorique et en recherche opérationnelle, la génération de colonnes est une méthode pour résoudre efficacement les problèmes d'optimisation linéaire de grande taille. Elle repose sur la (en), qui consiste à décomposer l'ensemble des contraintes en deux sous-ensembles. (fr)
- Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a (en)
- Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования. Общая идея метода заключается в том, что многие задачи линейного программирования слишком велики для явного выписывания всех переменных. Поскольку большинство переменных не будут входить в базис, а потому будут иметь нулевое значение в оптимальном решении, только подмножество переменных необходимо для решения задачи. Генерация столбцов поддерживает эту идею путём генерации только тех переменных, которые имеют потенциальную возможность улучшения целевой функции — то есть ищутся только переменные с отрицательной (предполагаем , что решается задача минимизации). (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a value of zero, so the optimal solution can be found without them. In many cases, this method allows to solve large linear programs that would otherwise be intractable. The classical example of a problem where it is successfully used is the cutting stock problem. One particular technique in linear programming which uses this kind of approach is the Dantzig–Wolfe decomposition algorithm. Additionally, column generation has been applied to many problems such as crew scheduling, vehicle routing, and the . (en)
- En informatique théorique et en recherche opérationnelle, la génération de colonnes est une méthode pour résoudre efficacement les problèmes d'optimisation linéaire de grande taille. Elle repose sur la (en), qui consiste à décomposer l'ensemble des contraintes en deux sous-ensembles. (fr)
- Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования. Общая идея метода заключается в том, что многие задачи линейного программирования слишком велики для явного выписывания всех переменных. Поскольку большинство переменных не будут входить в базис, а потому будут иметь нулевое значение в оптимальном решении, только подмножество переменных необходимо для решения задачи. Генерация столбцов поддерживает эту идею путём генерации только тех переменных, которые имеют потенциальную возможность улучшения целевой функции — то есть ищутся только переменные с отрицательной (предполагаем , что решается задача минимизации). Задача распадается на две — основная задача и подзадача. Основная задача является исходной задачей с предположением, что рассматривается только подмножество переменных. Подзадача же — это новая задача, цель которой — поиск новых переменных. Целевой функцией подзадачи является приведённая цена для текущих двойственных переменных, а ограничения порождаются естественными ограничениями на переменные. Процесс работает следующим образом. Решаем основную задачу, из решения получаем двойственные переменные для каждого ограничения исходной задачи. Эта информация используется в целевой функции подзадачи. Решаем подзадачу. Если целевая функция подзадачи будет отрицательной, переменная с отрицательной приведённой ценой найдена и эту переменную добавляем в основную задачу и производим очередное решение основной задачи. Новое оптимальное решение основной задачи даст новые двойственные переменные, и процесс повторяется, пока решения подзадачи дают отрицательные значения. Когда решение подзадачи даст положительное значение целевой функции, мы можем заключить, что оптимальное решение основной задачи найдено. Во многих случаях такой подход позволяет решать большие задачи линейного программирования. Классическим примером применения метода генерации столбцов является задача раскроя. Одна из техник линейного программирования, использующая тот же подход — разложение Данцига — Вулфа. Кроме того, генерация столбцов используется во многих задачах, таких как , и задача о p-медиане с ограничениями. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)