Heurísticas!!??? (EP3)

[Juliana Barby Simão <julianab@linux.ime.usp.br>]

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
>