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

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

Um pouco mais de prazo realmente ajudaria muito. Tivemos muitas provas e nosso
fim de semestre esta bastante corrido. Ainda havera duas provas amanha, sub de 
proglin na quinta, sub de calculo na sexta, sub de estocasticos na segunda, e
a terceira fase do ep de labprog e pra esta segunda, alem de e claro, o ep de 
proglin para sexta. Assim sendo, gostariamos se possivel de um prazo um pouco
maior para a entrega do EP. Obrigado!

On Mon, Jun 24, 2002 at 11:08:14PM -0300, Guilherme Tozo de Carvalho wrote:
> 
> 
> 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
> > >
> > 
> > 
> 

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