Cortes Disjuntivos para o Problema do Particionamento
Autores
|
3650 |
Ruy Eduardo Campello
|
44,45
|
|
3651 |
44,45
|
Informações:
Publicações do PESC
Diversos problemas de programação matemática, incluindo o de particionamento, podem ser formulados como Problemas de programação Disjuntiva Esta abordagem oferece um meio eficaz de gerar novos e poderosos planos de corte com propriedades convenientes, tirando proveito da estrutura particular do problema.
Para problemas gerais de programação inteira, metodologias baseadas em planos de cortes mostraram-se menos eficientes do que técnicas de enumeração; entretanto, para certas classes de problemas como o de particionamento, planos de corte são considerados eficientes. Visto que os cortes disjuntivos são mais fortes, podemos esperar que sejam mais promissores.
Esta dissertação trata do desenvolvimento teórico e aspectos computacionais dos cortes B(.), para o problema do particionamento, avaliados em termos de recursos computacionais e medidas independentes requeridas para a resolução de problemas teste gerados aleatoriamente sob condições controladas. Estes planos de corte são gerados a partir do princípio básico da Programação Linear Disjuntiva desenvolvido por Balas e Jeroslow.
Mostra-se que os cortes B(.), particularmente os novos, B(4) e sua versão aprofundada B(5), são não somente computacionalmente promissores, mas oferecem linhas novas e produtivas para futuras pesquisas.
Several mathematical programming problems, including the set partitioning, can be formulated as Disjuntive Programming Problems. This appoach offers a powerful procedure for the generation of new and strong cutting planes with desirable properties, taking advantage of particular problem structure.
For general integer programs, the traditional cutting plane methodologies proved less efficient than enumerative techniques; however, on certain classes problems, such as set partitioning, cutting planes are know to be efficient. Since the disjuntive cuts are stronger, they can be expected to be more promissing.
This dissertation deals with the theoretical development and computational aspects of disjunctive B(.) cuts, for the set partitioning problem, evaluated in terms of computer sources and independent measures required to solve specific randomly generated test problems under controlled conditions. These cutting planes are generated from the Basic Principle of Disjunctive Linear Programming posed by Balas and Jerolow.
It is show that B(.) cuts, especially the new B94) and its deeper version B(5), are not olny computationally promissing but offer new and fritful lines for future research.