Uma Metodologia de Feixes e Benders Aplicado a um Problema Linear Inteiro de Grande Porte
Autores
|
1691 |
288,303
|
|
|
1692 |
288,303
|
Informações:
Publicações do PESC
Título
Uma Metodologia de Feixes e Benders Aplicado a um Problema Linear Inteiro de Grande Porte
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
17/3/1998
Resumo
Consideremos um problema linear inteiro de grande porte, caracterizado por possuir a seguinte estrutura: a matriz de restrições e esparsa, possuindo uma estrutura bloco-diagonal, juntamente com variáveis e restrições de acoplamento. Um dos grupos de restrições dificulta a aplicação do esquema de decomposição de Benders.
Propomos o seguinte esquema algoritmo. Uma relaxação Lagrangeana é feita sobre o citado conjunto de restrições. Apresentamos um processo heurístico para o cálculo do multiplicador através da resolução do problema dual, estruturado a partir do método de feixes. Em cada iteração do algoritmo, propomos uma decomposição de Benders onde são fornecidos cotas para o valor da função e um e-subgradiente.
Abstract
We consider a large mixed linear integer problem. The structure of the constraint matrix is sparse, with independent blocks, and coupling constraints and variables. One of the groups of constraints to make difficult the application of Benders scheme decomposition.
In this work we propose the following algorithm. A Lagrangian Relaxation is made on the mentioned set of constraints; we presented a process heuristic for the calculation of the multiplier through the resolution of the dual problem, structured starting from the method of bundle. For each iterations of that multiplier, we propose a Benders decomposition scheme where is supplied quotas for the value of the function and an e-subgradient.
Arquivo