[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

Re: Heurísticas!!??? (EP3)



Sou mais um que concorda com o e-mail do Cabral e dos demais
colegas... acho que este ep está complexo demais e incrivelmente obscuro 
para ser entregue em um prazo tão curto, e acho que se tivessemos 1 semana
extra ia ajudar pacas :)

Guilherme  <gui@linux.ime.usp.br>










On Mon, 24 Jun 2002, Juliana Barby Simão wrote:

> Apesar da resposta do carlinhos para o email do Cabral, continuo com dúvidas
> em relação às heurísticas para um problema de programação inteira (variáveis
> binárias) genérico...
> 
> > Um bom jeito de achar uma solução viável, quando você não conhece
> > soluções heurísticas, é percorrer a árvore de busca em profundidade,
> > até achar uma solução.
> >
> 
> Quanto a percorrer a árvore em profundidade, tudo bem. Ao chegarmos a uma
> folha teremos um possível "lower bound", certo?
> Agora... não vejo uma outra maneira imediata de obtenção de lower bound...
> 
> > Mas, o resultado da relaxação linear deve indicar um bom caminho. Por
> > exemplo, que tal usar o valor trucado das variáveis. Isso não dá uma
> > solução viável?
> 
> Nem sempre, certo?  Como estamos lidando com variáveis binárias, poderíamos
> tentar arrendondá-las... Mas pode ocorrer de as restrições de igualdade
> deixarem de ser satisfeitas, não pode?
> Seria preciso verificar factibilidade... Vale a pena? Seria uma boa
> heurística?
> 
> Ah.. e outro problema: o prof. ernesto pediu para q implementássemos os 3
> tipos de busca pela árvore... Mas se não existir uma heurística (isto é, se
> um lower bound só for obtido quando chegarmos a uma folha...),  acho que não
> faz sentido percorrer a árvore de outra maneira q não seja em
> profundidade...
> 
> Oh, vida... qts dúvidas para um ep a ser entregue daqui a 4 dias... ;-)
> 
> Juliana
> 
> ----- Original Message -----
> From: "Carlos Eduardo Ferreira" <cef@ime.usp.br>
> To: "Cleiton Cabral" <ccabrals@uol.com.br>; <egbirgin-mac315@ime.usp.br>
> Sent: Monday, June 17, 2002 5:30 PM
> Subject: Re: Heurísticas??? (EP3)
> 
> 
> > On Sunday 16 June 2002 19:06, Cleiton Cabral wrote:
> > > Estou fazendo o EP3 de ProgLin mas não sei como desenvolver uma
> > > heurística para problemas gerais de programação inteira. Na aula do
> > > Carlinhos aprendemos algumas heurísticas simples para o problema de 1
> > > mochila. O que fazer quando o problema é geral, envolve várias
> > > restrições, etc? Existe alguma heurística que utilize o próprio
> > > pacote que nós escolhemos ou teremos que desenvolver uma rotina
> > > totalmente à parte para isso? Alguém poderia dar uma luz nesse
> > > sentido?
> > >
> > > Cabral.
> >
> > Um bom jeito de achar uma solução viável, quando você não conhece
> > soluções heurísticas, é percorrer a árvore de busca em profundidade,
> > até achar uma solução.
> >
> > Mas, o resultado da relaxação linear deve indicar um bom caminho. Por
> > exemplo, que tal usar o valor trucado das variáveis. Isso não dá uma
> > solução viável?
> >
> > --
> > carlinhos
> >
> 
>