Re: Heurísticas??? (EP3)

[Ricardo Drizin <ricardo@linux.ime.usp.br>]

O que eu entendi do enunciado original, é que é um problema
de PL "binária mista" (é isso?), ou seja, algumas variáveis
serão binárias (0,1) e outras serão contínuas. Pelo segundo email,
entendo que podemos esquecer as contínuas e fazer todas como sendo
binárias.

Pelos meus testes, basta fazer "contínuas e inteiras", e quando
for binária você adiciona a restrição Xi<=1 (como ela é inteira, e
também é >=0, só resta 0 e 1). Então acaba ficando um caso mais geral,
e dá pra resolver contínua, binária, inteira, e suas
combinações.

O que eu não entendi (perdi as aulas, alguma boa alma me explica?) é
quais são os 3 modos que devemos percorrer a árvore binária. Percorrer em
profundidade e largura seria percorrer todos nós, independentemente
daquela coisa de "se já tivermos uma solução inteira melhor que este
nó e qualquer de seus descendentes"? Ou também devemos usar esse
limitante que citei, e a única diferença dos 3 métodos seria "qual o
próximo nó" ?

O melhor limitante (heap) nao seria nada mais do que um heap usado como
fila de prioridade, usado para trabalharmos sempre em cima dos nós mais
promissores (com melhor custo)? 

Rodei a net inteira, e só vi resoluções desse tipo que eu falei (escolher
sempre o nó mais "promissor", e ao achar uma solução inteira
descartar qualquer solução fracionária cujo custo não é melhor), por
lógica deduzo que isso seja o tal do método do melhor limitante /
heap...  (?)
http://mat.gsia.cmu.edu/orclass/integer/integer.html

Se for pra usarmos sempre esse limitante de "já temos solução
melhor", ao descer em profundidade, é pra descer na ordem
"cega" e simétrica (ou seja, ignorando os custos de cada nó,
empilhando sempre esquerdo e direito na mesma ordem) ou devemos empilhar
por último (e obter primeiro) o nó de melhor custo, na esperança de que
acharemos mais rápido uma solução inteira "boa" que vai
eliminar a pesquisa em outros nós que estariam na pilha? (No caso de
percorrer em largura, nao faria muita diferença a ordem de enfileirar os
nós, pois estariamos sempre trabalhando no mesmo nível na
árvore.)

Espero não estar viajando muito.. é que nao encontrei nenhum exemplo por
aí de largura (breadth-first) ou profundidade (depth-first), apenas
encontrei o tal do best-first (que é o metodo do heap)..
obrigado.



At 14:14 23/06/02 -0300, you wrote:
> >Para quem quiser, podem fazer o
> EP3 para variaveis 0-1 no lugar de variaveis inteiras. 
>
> Fiquei com uma dúvida ao ler este email: no enunciado original do EP3, a
> restrição que diz "alguns x_i pertencentes a {0,1}"
> significa:
>
> a) que há variáveis inteiras e contínuas, sendo as inteiras limitadas a 0
> ou 1 (como aquele bienst)
> b) que todas as variáveis são inteiras, algumas das quais limitadas a 0
> ou 1, outras apenas a serem >= 0
> c) n.d.a.
>
> Dependendo da resposta, a frase acima (o "relaxamento do EP
> original") muda de sentido... Ela quer dizer que podemos assumir que
> *todas* as varíaveis serão inteiras e limitadas a 0-1, ou que serão
> mistas, inteiras e contínuas, mas que todas as inteiras são do tipo
> 0-1?
>
> Espero que alguém tenha entendido, porque agora fiquei completamente
> confuso com meu próprio email...
>
> Rubens