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

[Ivan Bittencourt de Araujo e Silva Neto <ivanneto@linux.ime.usp.br>]

Concordo com o que foi dito no e-mail do Cabral. Eu sou um dentre os muitos
que não sabem nem por onde começar a fazer o EP3. Obrigado!

On Mon, Jun 24, 2002 at 09:23:41PM -0300, Cleiton Cabral wrote:
> 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
> > >
> >
> >
> 
> 

-- 
 Ivan Bittencourt de Araujo e S Neto   <ivanneto@linux.ime.usp.br>