Tópicos em otimização com restrições lineares (2008)
- Authors:
- Autor USP: ANDRETTA, MARINA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: PROGRAMAÇÃO MATEMÁTICA; MÉTODOS NUMÉRICOS DE OTIMIZAÇÃO
- Agências de fomento:
- Language: Português
- Abstract: Métodos do tipo Lagrangiano Aumentado são muito utilizados para minimização de funções sujeitas a restrições gerais. Nestes métodos, podemos separar o conjunto de restrições em dois grupos: restrições fáceis e restrições difíceis. Dizemos que uma restrição é fácil se existe um algoritmo disponível e eficiente para resolver problemas restritos a este tipo de restrição. Caso contrário, dizemos que a restrição é difícil. Métodos do tipo Lagrangiano aumentado resolvem, a cada iteração, problemas sujeitos às restrições fáceis, penalizando as restrições difíceis. Problemas de minimização com restrições lineares aparecem com freqüência, muitas vezes como resultados da aproximação de problemas com restrições gerais. Este tipo de problema surge também como subproblema de métodos do tipo Lagrangiano aumentado. Assim, uma implementação eficiente para resolver problemas com restrições lineares é relevante para a implementação eficiente de métodos para resolução de problemas de programação não-linear. Neste trabalho, começamos considerando fáceis as restrições de caixa. Introduzimos BETRA-ESPARSO, uma versão de BETRA para problemas de grande porte. BETRA é um método de restrições ativas que utiliza regiões de confiança para minimização em cada face e gradiente espectral projetado para sair das faces. Utilizamos BETRA (denso ou esparso) na resolução dos subproblemas que surgem a cada iteração de ALGENCAN (um método de lagrangiano aumentado). Para decidir qual algoritmo utilizar pararesolver cada subproblema, desenvolvemos regras que escolhem um método para resolver o subproblema de acordo com suas características. Em seguida, introduzimos dois algoritmos de restrições ativas desenvolvidos para resolver problemas com restrições lineares (BETRALIN e GENLIN). Estes algoritmos utilizam, a cada iteração, o método do Gradiente Espectral Projetado Parcial quando decidem mudar o conjunto de restrições ativas. O método do ) gradiente Espectral Projetado Parcial foi desenvolvido especialmente para este propósito. Neste método, as projeções são computadas apenas em um subconjunto das restrições, com o intuito de torná-las mais eficientes. Por fim, tendo introduzido um método para minimização com restrições lineares, consideramos como fáceis as restrições lineares. Incorporamos BETRALIN e GENLIN ao arcabouço de Lagrangianos aumentados e verificamos experimentalmente a eficiência e eficácia destes métodos que trabalham explicitamente com restrições lineares e penalizam as demais
- Imprenta:
- Data da defesa: 24.07.2008
-
ABNT
ANDRETTA, Marina. Tópicos em otimização com restrições lineares. 2008. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2008. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01092008-114422/. Acesso em: 24 abr. 2024. -
APA
Andretta, M. (2008). Tópicos em otimização com restrições lineares (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01092008-114422/ -
NLM
Andretta M. Tópicos em otimização com restrições lineares [Internet]. 2008 ;[citado 2024 abr. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01092008-114422/ -
Vancouver
Andretta M. Tópicos em otimização com restrições lineares [Internet]. 2008 ;[citado 2024 abr. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01092008-114422/ - Solving irregular strip packing problems with free rotations using separation lines
- Heurísticas para o problema bidimensional de empacotamento irregular com distribuição de peso
- Um método de restrições ativas para minimização em caixas
- Um modelo de programação não-linear inteira mista para o problema de empacotamento de cilindros em níveis
- O BRKGA aplicado em problemas de corte de itens irregulares em um único recipiente
- Métodos heurísticos para o problema de corte de luvas de couro
- Teoria dos grafos e aplicações
- Nesting problems with continuous rotations: a survey
- A genetic algorithm for the nesting problem with continuous rotations
- O problema de corte de itens irregulares: aplicação na indústria de corte de aventais e forros de luva
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
