An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm.

Property Value
dbo:abstract
  • Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm. Dantzig–Wolfe decomposition relies on delayed column generation for improving the tractability of large-scale linear programs. For most linear programs solved via the revised simplex algorithm, at each step, most columns (variables) are not in the basis. In such a scheme, a master problem containing at least the currently active columns (the basis) uses a subproblem or subproblems to generate columns for entry into the basis such that their inclusion improves the objective function. (en)
  • O princípio da decomposição de Dantzig-Wolfe, originalmente desenvolvida pelos matemáticos norte-amercianos George Dantzig e , foi publicado em 1960 dando início a um intenso trabalho de pesquisa na área de programação matemática em larga escala. Este procedimento é mais adequado quando aplicado à problemas lineares cuja matriz de coeficientes tem uma estrutura angular, isto é, um ou mais blocos independentes lincados por equações acopladas. Ele opera formando um ``problema mestre`` equivalente, com poucas linhas, mas com número muito maior de colunas. Este problema é então resolvido sem tabular todas as colunas, gerando elas sempre que o método simplex precisa, usando uma tecnica conhecida com geração de coluna. O algoritmo envolve iterações entre um conjunto de subproblemas cujo função objetivo contém parâmetros variáveis e um problema mestre. O subproblema recebe um conjunto de parâmetros do problema mestre e então envia suas soluções para o problema mestre, que combina esta solução com a solução anterior e computa novos parâmetros. (pt)
  • Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода. В 1960 г. Джордж Данциг и Филип Вулф разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений. Этот метод оказался наиболее эффективным для решения задач, матрица ограничений которых имеет блочно-диагональный вид с небольшим числом переменных. Однако, как показали дальнейшие исследования, метод применим также и для задач линейного программирования с матрицей общего вида. Соответствующий метод предложен Д. Б. Юдиным и Э. Г. Гольштейном и называется блочным программированием. Отличительной особенностью метода декомпозиции является использование координирующей задачи, которая имеет, по сравнению с исходной, небольшое число строк и большое число столбцов. (ru)
dbo:thumbnail
dbo:wikiPageID
  • 17885310 (xsd:integer)
dbo:wikiPageLength
  • 7312 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1070050047 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm. (en)
  • O princípio da decomposição de Dantzig-Wolfe, originalmente desenvolvida pelos matemáticos norte-amercianos George Dantzig e , foi publicado em 1960 dando início a um intenso trabalho de pesquisa na área de programação matemática em larga escala. Este procedimento é mais adequado quando aplicado à problemas lineares cuja matriz de coeficientes tem uma estrutura angular, isto é, um ou mais blocos independentes lincados por equações acopladas. O algoritmo envolve iterações entre um conjunto de subproblemas cujo função objetivo contém parâmetros variáveis e um problema mestre. (pt)
  • Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода. В 1960 г. Джордж Данциг и Филип Вулф разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений. Отличительной особенностью метода декомпозиции является использование координирующей задачи, которая имеет, по сравнению с исходной, небольшое число строк и большое число столбцов. (ru)
rdfs:label
  • Dantzig–Wolfe decomposition (en)
  • Разложение Данцига — Вулфа (ru)
  • Decomposição de Dantzig-Wolfe (pt)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License