Column generation (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageID | 744589 (xsd:integer) |
| dbo:wikiPageLength | 7649 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1070050050 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cutting_stock_problem dbr:Crew_scheduling dbr:Objective_function dbc:Optimization_algorithms_and_methods dbr:Dual_linear_program dbr:Linear_programming dbr:Dantzig–Wolfe_decomposition dbr:Reduced_cost dbr:Without_loss_of_generality dbr:Combinatorial_algorithms dbr:Vehicle_routing dbr:Capacitated_p-median_problem |
| dbp:wikiPageUsesTemplate | dbt:Short_description dbt:Mathapplied-stub dbt:Optimization_algorithms |
| dcterms:subject | dbc:Optimization_algorithms_and_methods |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatOptimizationAlgorithmsAndMethods yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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) |
| rdfs:label | Column generation (en) Génération de colonnes (fr) Генерация столбцов (ru) |
| owl:sameAs | freebase:Column generation yago-res:Column generation wikidata:Column generation dbpedia-fr:Column generation dbpedia-ru:Column generation https://global.dbpedia.org/id/2tzfF |
| prov:wasDerivedFrom | wikipedia-en:Column_generation?oldid=1070050050&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Column_generation |
| is dbo:wikiPageRedirects of | dbr:Delayed_Column_Generation dbr:Delayed_column-generation dbr:Delayed_column_generation |
| is dbo:wikiPageWikiLink of | dbr:Benders_decomposition dbr:Delayed_Column_Generation dbr:Cutting-plane_method dbr:Cutting_stock_problem dbr:List_of_numerical_analysis_topics dbr:Branch_and_price dbr:Crew_scheduling dbr:Fair_random_assignment dbr:Delayed_column-generation dbr:Delayed_column_generation |
| is foaf:primaryTopic of | wikipedia-en:Column_generation |