Seminário de Teoria da Computação

          Uso de cortes canônicos no  método de 
    ramificação local para problemas inteiros 0--1 mistos 

                 Cid Carvalho de Souza

            Segunda-feira, 6 de dezembro de 2004 <---- ATENÇÃO
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

               Auditório do IC (IC1), 13:00hs


Resumo:


Em sua  maioria, os problemas  de Programação Inteira Mista  (MIP) são
NP-difíceis e,  apesar do notável  avanço dos resolvedores de  MIP, em
muitos casos, a simples obtenção  de uma solução de boa qualidade, não
necessariamente ótima, em um  tempo computacional aceitável ainda é um
desafio.   Nesta  situação  é  comum  que  se  recorra  a  heurísticas
especificamente desenvolvidas  para o problema particular  que se está
resolvendo.   Contudo, este  trabalho de  desenvolvimento  raramente é
replicável a outros problemas.

Em artigo recente  de Fischetti e Lodi propôs-se  um método heurístico
para MIPs 0--1 que pode ser inserido no contexto geral de um algoritmo
Branch-and-Bound  de  um  resolvedor  comercial.  O  método  tem  como
objetivo  acelerar  a  busca  por soluções  sub-ótimas,  explorando  a
eficiência dos resolvedores no tratamento de ``pequenos'' subproblemas
de  MIP.   Isso é  feito  introduzindo-se  desigualdades inválidas  no
modelo original,  as quais são denominadas de  ramificações locais.  O
conjunto de soluções originais  que satisfazem a estas desigualdades é
suficientemente  restrito  para   que  o  resolvedor  possa  encontrar
rapidamente o ótimo neste subespaço ou concluir que ele é vazio.  Caso
o ótimo exista,  a melhor solução conhecida é  atualizada.  O método é
aplicado  então ao  problema que  resta ao  excluir as  soluções deste
subproblema.

Analisando-se  o   método  de  ramificação  local,   nota-se  que  ele
acrescenta planos  de cortes muito  ``superficiais'' (descartam poucas
soluções contínuas da relaxação) e que estes cortes ocorrem com grande
freqüência.   Assim,  é  possível  que  a introdução  de  cortes  mais
``profundos'' (descartam mais soluções contínuas da relaxação), possam
melhorar  a eficiência  do método,  mesmo que  isso implique  em maior
esforço para resolver os subproblemas.

Ocorre que os cortes de  ramificações locais propostos por Fischetti e
Lodi são casos especiais dos  cortes canônicos para MIPs com variáveis
binárias introduzidos por Balas  e Jeroslowem 1972. 

Nesta apresentação serão discutidas idéias que tivemos para estender o
método de  ramificação local incorporando  a ele cortes  canônicos que
sejam  mais profundos  do que  aqueles usados  na versão  proposta por
Fischetti   e   Lodi.

Este trabalho  faz parte da  pesquisa realizada pelo  Mestrando Rafael
Santos do IC.