Estúdio de Optimização
O Estúdio de Optimização é um espaço informal para
a apresentação e discussão de resultados (originais ou conhecidos) sobre
aplicações, algoritmos e teoria de Optimização.
São privilegiadas, sempre que possível, as componentes industriais e
computacionais da Optimização.
Participam no Estúdio de Optimização estudantes de
licenciatura finalistas, estudantes de pós-graduação, mestrado e doutoramento,
investigadores doutorados e quadros empresariais ou industriais.
Sessões Agendadas
-
10ª Sessão (2 de Junho de 2006, 11h45m-11h45m, Sala 2.3 do DM).
Título:
Digressão pelas enumerações de trajectos e de caminhos.
Oradora:
Marta Pascoal (Univ. Coimbra).
Resumo:
A enumeração de trajectos entre um par de nós de uma rede é uma generalização
do problema do trajecto com menor custo em que se pretende listar trajectos
por ordem não decrescente de custo.
Aqui se apresentam as principais classes de métodos para a enumeração de
trajectos.
Mostra-se como estes métodos podem ser utilizados para determinar trajectos
satisfazendo a restrições adicionais e como podem ser adaptados para enumerar
trajectos sem nós repetidos, ou seja, caminhos.
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
9ª Sessão (26 de Maio de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Árvores de suporte com restrição de grau: Propriedades e formulações.
Orador:
Pedro Coimbra Martins (Instituto Politécnico de Coimbra).
Resumo:
Este seminário incide em dois problemas de optimização em grafos.
Para a sua descrição considere-se G=(N,E) um grafo conexo, com N o conjunto de
nodos e E o conjunto de arestas. Considere-se também uma constante d, tomando
valores em {2,...,|N|-1}. No primeiro problema, que designamos por d-MST e
desde há muito conhecido, pretendemos determinar uma árvore de suporte de custo
mínimo em G, com a restrição de que todos os nodos têm grau máximo d.
No segundo problema, recentemente proposto e que designamos por md-MST,
pretendemos também determinar uma árvore de suporte sobre G, porém desta vez a
restrição de grau estabelece que cada nodo ou tem grau mínimo d ou então é um
nodo-folha (grau 1). Na prática estes problemas surgem quando pretendemos
localizar meios com determinada propriedade de conectividade (máxima ou mínima),
ligados por uma estrutura em árvore. Ambos pertencem à classe dos NP-difíceis
(ou duros) para determinados valores de d. Neste seminário são apresentadas propriedades e formulações para estes dois problemas.
Alguns resultados computacionais, obtidos a partir das formulações
consideradas, indicam que o segundo problema (md-MST) deverá ser mais difícil
de caracterizar, do ponto de vista poliédrico, do que o primeiro (d-MST), o que
torna o novo problema bastante mais aliciante.
Co-autores: Ana Maria de Almeida (Univ. Coimbra) e Maurício C. Souza (Univ. Fed.
Minas Gerais, Brasil).
-
8ª Sessão (19 de Maio de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Algoritmos de Encaminhamento Dinâmico e Atribuição de Comprimento de Onda em
Redes WDM Resilientes.
Oradora:
Teresa Martinez Gomes (Univ. Coimbra).
Resumo:
Dada a elevada largura de banda de uma única ligação óptica e a diversidade de
serviços suportados por uma rede WDM (Wavelength Division Multiplexing), a
quantidade de tráfego perdido devido a um único corte de fibra ou à falha de um
comutador de comprimentos de onda é muito superior à que ocorre noutros tipos
de redes em situações de falha isolada. Uma rede deste tipo deve ser capaz de
garantir a conectividade das ligações em situações de falha. Uma forma de
aumentar a resistência da rede a avarias (ou seja sua resiliência) é o
estabelecimento (dinâmico) de dois caminhos (activo e de protecção) disjuntos,
procurando simultaneamente minimizar a utilização de recursos na rede. Caso se
considere que a probabilidade de ocorrência de falhas simultâneas é
desprezável, então basta proteger a rede contra falhas isoladas. Nestas
condições os caminhos de protecção, de dois caminhos activos que não partilhem
nenhum recurso, podem partilhar recursos entre si (protecção partilhada).
O problema da obtenção de pares de caminhos disjuntos numa rede WDM, mesmo na
sua forma mono-objectivo, como por exemplo a minimização da largura de banda
total requerida, é de difícil resolução. Assim, muitos autores propõem
aproximações heurísticas para a resolução do problema.
Nesta apresentação é feita uma descrição do problema de encaminhamento e
atribuição do comprimento de onda em redes WDM. Serão apresentados alguns
mecanismos de protecção e, finalmente, serão referidos alguns algoritmos para
protecção em redes WDM.
Co-autor: Carlos Simões (Instituto Politécnico de Viseu).
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
7ª Sessão (28 de Abril de 2006, 13h00m-14h00m, Sala 2.3 do DM).
Título:
Resolução do problema do caixeiro viajante assimétrico (e uma variante)
através da relaxação Lagrangeana.
Oradora:
Ana Maria Rocha (Univ. do Minho).
Resumo:
Alguns problemas de optimização linear originários de aplicações do mundo real
têm um grande número de variáveis e/ou restrições que dificilmente podem ser
resolvidos por métodos do tipo simplex de uma forma eficiente. Isto é o que
acontece, por exemplo, com o problema do caixeiro viajante.
Nas últimas décadas, emergiu uma nova linha de investigação cujo objectivo é o
desenvolvimento de algoritmos de aproximação para classes de problemas de
programação linear. Pela experiência prática existente, pode-se concluir que é
preferível obter rapidamente uma solução parcialmente exacta a ter que esperar
um tempo excessivamente longo por uma solução exacta.
A técnica do subgradiente, que é baseada na relaxação Lagrangeana, é fácil e
rápida de implementar e produz muito boas soluções duais. O algoritmo
volumétrico, considerado como uma extensão do método do subgradiente, para além
de produzir soluções duais produz também boas aproximações à solução primal.
Este procedimento é muito simples, rápido e requer pequenas quantidades de
memória.
A principal motivação do projecto assenta na aplicação do algoritmo volumétrico
para determinar soluções aproximadas/inteiras de problemas que são difíceis de
resolver. Os problemas que pretendemos resolver são considerados difíceis, quer
pelo número exagerado de variáveis e/ou quer pelo grande número de restrições.
Deste tipo de problemas salientamos o problema do caixeiro viajante assimétrico
e o problema do reparador viajante.
Co-autor: J. L. Soares (Univ. Coimbra).
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
6ª Sessão (21 de Abril de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Optimization with differential equations: Where many large optimization
problems come from.
Orador:
Georg Stadler (Univ. Coimbra).
Resumo:
Using a very simple example I will explain the basic idea behind optimization
problems with differential equations. These problems that are also known as
optimal control problems arise in various applications, for example if hot
tools have to be cooled in a certain way or if a spacecraft shall reach the
moon using the minimum amount of energy.
Optimal control problems are interesting from both, the application and the
mathematical point of view. Since usually the involved differential equations
can only be solved numerically, one has to discretize them (that is,
approximate the equations by a finite-dimensional system). This leads to
optimization problems having a very large number of unknowns, but also a lot of
structure.
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
5ª Sessão (31 de Março de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Optimização Financeira (Estimação da Função de Densidade de Probabilidade de
Risco Neutro para Preços de Opções).
Oradora:
Ana Margarida Monteiro (Univ. Coimbra).
Resumo:
A atribuição de preços a opções é uma das áreas fundamentais da matemática
financeira. O desenvolvimento da teoria dos preços das opções surge na
sequência do trabalho de Black e Scholes, segundo o qual a variação do preço do
activo subjacente a uma opção segue uma lei de probabilidade lognormal.
Uma vez que nem todos os pressupostos desta teoria se adequam às evidências do
mercado financeiro, o problema da determinação de uma medida de probabilidade
de risco neutro tornou-se um problema relevante na teoria dos preços das
opções.
Apresentamos uma nova abordagem numérica para a estimação da função densidade
de probabilidade de risco neutro relativa ao preço futuro do activo subjacente
a uma opção. A estimação é feita recorrendo a funções spline cúbicas, de forma
a garantir a suavidade desejada. O problema de optimização resultante, usado
para inverter os dados e determinar uma função de densidade correspondente, é
um problema convexo de programação quadrática ou semidefinida.
No caso da programação quadrática, a não negatividade da função densidade é
assegurada impondo restrições de desigualdade nos nós das funções spline.
No outro caso, o da programação semidefinida, recorre-se a uma caracterização
matricial de não negatividade de polinómios.
Testámos esta abordagem com preços de opções gerados a partir da fórmula de
Black-Scholes e com preços do Índice S&P 500. Discutiremos os resultados
numéricos, que mostram a eficiência desta abordagem para a estimação da função
de densidade de risco neutro.
Co-autores: R. H. Tütüncü (Carnegie Mellon Univ.) e L. N. Vicente (Univ.
Coimbra).
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
4ª Sessão (24 de Março de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Resolução e Eficiência computacionais: Qui pro quo!
Oradora:
Ana Maria de Almeida (Univ. Coimbra).
Resumo:
Aqui se vai falar sobre algoritmos, resolução computacional, heurísticas,
meta-heurísticas, problemas "duros" e outros que tais.
Documentação:
Ficheiro da apresentação, em
formato PDF.
-
3ª Sessão (17 de Março de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Duas caracterizações equivalentes de poliedros.
Orador:
João Luís Soares (Univ. Coimbra).
Resumo:
José Silva é um 'marine' luso-descendente que trabalha no Pentágono. A sua
tarefa é resolver sistemas de equações lineares usando um software de álgebra
linear numérica e reportar as respectivas soluções ao seu chefe. Acontece que
invariavelmente o software ora produz uma solução, fácil de verificar por
substituição das variáveis, ora produz uma mensagem dizendo 'sistema
impossível'. O seu chefe anda a ficar aborrecido com os 'sistemas impossíveis'
e isso não é nada bom para o Silva
O chefe garante que é 'impossível' o sistema ser impossível.
Ao Silva resta-lhe pôr em causa o software, tanto mais que ouviu dizer que
alguns dos engenheiros que trabalharam na sua implementação são norte-coreanos.
O problema vai agravar-se pois em breve terá de resolver sistemas de inequações
lineares.
-
2ª Sessão (10 de Março de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Um método de procura padrão baseado em colónia de partículas para
optimização não linear com limites nas variáveis.
Orador:
Ismael Vaz (Univ. do Minho).
Resumo:
em formato PDF.
-
1ª Sessão (3 de Março de 2006, 11h45m-12h45m, Sala 2.3 do DM).
Título:
Breve Introdução aos Fundamentos da Optimização sem Derivadas.
Orador:
Luís Nunes Vicente (Univ. Coimbra).
O Estúdio de Optimização é uma iniciativa de
João Luís Soares,
Joaquim João Júdice,
José Luis Santos,
Luís Nunes Vicente e
Marta Pascoal.
Actualmente, a coordenação do programa do
Estúdio de Optimização é da responsabilidade de
Marta Pascoal.