Benders decomposition (original) (raw)
La descomposició de Benders (anomenada en honor de ) és una tècnica en programació matemàtica que permet obtenir la solució de problemes de programació lineal que tenen una estructura de bloc especial. Aquesta estructura sovint ocorre en aplicacions tals com la . A mesura que progressa cap a una solució, la descomposició de Benders afegeix només restriccions, per la qual cosa l'aproximació s'anomena de «generació de files»; contràriament, la utilitza «».
| Property | Value |
|---|---|
| dbo:abstract | La descomposició de Benders (anomenada en honor de ) és una tècnica en programació matemàtica que permet obtenir la solució de problemes de programació lineal que tenen una estructura de bloc especial. Aquesta estructura sovint ocorre en aplicacions tals com la . A mesura que progressa cap a una solució, la descomposició de Benders afegeix només restriccions, per la qual cosa l'aproximació s'anomena de «generació de files»; contràriament, la utilitza «». A mesura que progressa cap a una solució, la descomposició de Benders afegeix noves restriccions: és per això que aquest mètode és de «generació de files», en contrast amb la descomposició de Danzig-Wolfe, que utilitza la «generació de columnes». (ca) Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders. The strategy behind Benders decomposition can be summarized as divide-and-conquer. That is, in Benders decomposition, the variables of the original problem are divided into two subsets so that a first-stage master problem is solved over the first set of variables, and the values for the second set of variables are determined in a second-stage subproblem for a given first-stage solution. If the subproblem determines that the fixed first-stage decisions are in fact infeasible, then so-called Benders cuts are generated and added to the master problem, which is then re-solved until no cuts can be generated. Since Benders decomposition adds new constraints as it progresses towards a solution, the approach is called "row generation". In contrast, Dantzig–Wolfe decomposition uses "column generation". (en) La décomposition de Benders est une technique d'optimisation qui permet de trouver des solutions à des problèmes d'optimisation linéaire de très grande taille ayant une structure de blocs. On rencontre souvent cette structure dans les applications comme la programmation stochastique. Cet algorithme génère des contraintes au fur et à mesure de sa progression vers la solution. La technique porte le nom de Jacques F. Benders. La stratégie derrière la décomposition de Benders peut être résumée ainsi : diviser pour mieux régner. Autrement dit, dans la décomposition de Benders, les variables du problème d'origine sont divisées en deux sous-ensembles de sorte qu'un problème maître de première étape est résolu sur le premier ensemble de variables, et les valeurs du deuxième ensemble de variables sont déterminées dans un second- sous-problème d'étape pour une solution de première étape donnée. Si le sous-problème détermine que les décisions fixes de la première étape sont en fait irréalisables, alors les coupes de Benders sont générées et ajoutées au problème principal, qui est ensuite résolu jusqu'à ce qu'aucune coupe ne puisse être générée. Puisque la décomposition de Benders ajoute de nouvelles contraintes au fur et à mesure qu'elle progresse vers une solution, l'approche est donc considérée comme une approche génération de lignes, ce qui contraste avec l'approche par décomposition de Dantzig-Wolfe basée sur la génération de colonnes. (fr) Decomposição de Benders é uma técnica de programação matemática que permite resolver problemas de programação linear muito grandes, que possuam uma estrutura de blocos. Esta estrutura de blocos, muitas vezes, ocorre em aplicações tais como em programação estocástica, uma vez que a incerteza é geralmente representada através de cenários. A técnica é nomeada em homenagem a Jacques F. de Benders. A decomposição de Benders usa uma estratégia de dividir para conquistar. Na decomposição de Benders as variáveis do problema são divididas em dois subconjuntos, de modo que um problema mestre é resolvido considerando apenas o primeiro conjunto de variáveis e os valores para o segundo conjunto de variáveis são determinados em um segundo estágio (problema escravo) usando os valores encontrados (fixados) para as variáveis do primeiro conjunto. Se o subproblema descobre que os valores fixados para o primeiro conjunto de variáveis é inviável, são gerados cortes de Benders que são adicionados ao problema mestre. O processo é então repetido até que não seja possível gerar mais cortes. Uma vez que a decomposição de Benders adiciona novas restrições à medida que progride em direção a uma solução, a abordagem é chamada de "geração de linhas". Em contraste, com a decomposição de Dantzig–Wolfe decomposição que usa geração de colunas. Geralmente o primeiro conjunto de variáveis é dado pelas variáveis inteiras do problema e o segundo pelas variáveis contínuas. Dessa forma, o problema mestre constitui-se de um problema primal inteiro, já os problemas escravos são problemas duais lineares. (pt) |
| dbo:wikiPageExternalLink | https://link.springer.com/article/10.1007%2FBF01386316 |
| dbo:wikiPageID | 21866881 (xsd:integer) |
| dbo:wikiPageLength | 11230 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1049448896 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Decomposition_methods dbr:Jacques_F._Benders dbr:Numerische_Mathematik dbr:Convex_set dbr:Column_generation dbr:Linear_programming dbr:FortSP dbr:Dantzig–Wolfe_decomposition dbr:Mathematical_programming dbc:Stochastic_optimization dbc:Linear_programming dbr:Block_matrix dbr:Recession_cone dbr:Dover_Publications dbr:Stochastic_programming dbr:Duality_theory |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:More_footnotes dbt:Reflist |
| dcterms:subject | dbc:Decomposition_methods dbc:Stochastic_optimization dbc:Linear_programming |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 yago:WikicatDecompositionMethods |
| rdfs:comment | La descomposició de Benders (anomenada en honor de ) és una tècnica en programació matemàtica que permet obtenir la solució de problemes de programació lineal que tenen una estructura de bloc especial. Aquesta estructura sovint ocorre en aplicacions tals com la . A mesura que progressa cap a una solució, la descomposició de Benders afegeix només restriccions, per la qual cosa l'aproximació s'anomena de «generació de files»; contràriament, la utilitza «». (ca) Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders. (en) La décomposition de Benders est une technique d'optimisation qui permet de trouver des solutions à des problèmes d'optimisation linéaire de très grande taille ayant une structure de blocs. On rencontre souvent cette structure dans les applications comme la programmation stochastique. Cet algorithme génère des contraintes au fur et à mesure de sa progression vers la solution. La technique porte le nom de Jacques F. Benders. (fr) Decomposição de Benders é uma técnica de programação matemática que permite resolver problemas de programação linear muito grandes, que possuam uma estrutura de blocos. Esta estrutura de blocos, muitas vezes, ocorre em aplicações tais como em programação estocástica, uma vez que a incerteza é geralmente representada através de cenários. A técnica é nomeada em homenagem a Jacques F. de Benders. (pt) |
| rdfs:label | Descomposició de Benders (ca) Benders decomposition (en) Décomposition de Benders (fr) Decomposição de Benders (pt) |
| owl:sameAs | freebase:Benders decomposition yago-res:Benders decomposition wikidata:Benders decomposition dbpedia-ca:Benders decomposition dbpedia-fr:Benders decomposition dbpedia-pt:Benders decomposition https://global.dbpedia.org/id/2pNgR |
| prov:wasDerivedFrom | wikipedia-en:Benders_decomposition?oldid=1049448896&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Benders_decomposition |
| is dbo:wikiPageDisambiguates of | dbr:Benders_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Benders'_decomposition |
| is dbo:wikiPageWikiLink of | dbr:Benders'_decomposition dbr:Benders_(disambiguation) dbr:Multiple_sequence_alignment |
| is foaf:primaryTopic of | wikipedia-en:Benders_decomposition |