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

["Cleiton Cabral" <ccabrals@uol.com.br>]

A verdade é que este EP3 é o mais nebuloso com o qual já nos deparamos. Na
sala de aula, os círculos de discussão sobre esse assunto demonstram que
pouca gente sabe sequer por onde começar e a impressão é que nem o professor
sabe exatamente o que ele quer que se faça neste EP. Entendo que devemos nos
acostumar a pesquisar sozinhos, mas quando vamos atrás dos "Google" da vida
para procurar algo sobre o assunto, deparamo-nos com maneiras muito
complexas de implementar as heurísticas. Acho que precisamos de um pouco
mais de LUZ!

Cabral.



----- Original Message -----
From: "Juliana Barby Simão" <julianab@linux.ime.usp.br>
To: "Carlos Eduardo Ferreira" <cef@ime.usp.br>; "Lista - Mac315"
<egbirgin-mac315@ime.usp.br>
Sent: Monday, June 24, 2002 8:16 PM
Subject: Heurísticas!!??? (EP3)


> 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
> >
>
>