Artigo 1

Dados do artigo:
- hm2014.pdf
- A Local Search Approach for Binary Programming:
Feasibility Search
Entendimento
i) Abordagem de busca local para a produção rápida de soluções viáveis considerando problemas NP-difíceis expressos como programas binários. ii) A estrutura do problema é representada como um grafo de conflitos e um procedimento sistemático de geração de vizinhos é usada para saltar de uma solução viável para outra usando cadeias de movimentos. iii) Foram realizados experimentos computacionais com 32 problemas binários (que tem uma solução viável) do conjunto de referências MIPLIB para comparação do desempenho da abordagem proposta e de dois solucionadores de programação inteira de código aberto –
CBC e GLPK. Os resultados apontam que a abordagem proposta é mais confiável para a produção de soluções viáveis em quantidades restritas de tempo. iv) Uma vez que é encontrada uma solução viável, esta pode acelerar a produção de soluções de alta qualidade – até melhor que a mesma, através da utilização de métodos como RINS ou local branching.
Sobre Problemas Binários
i) As restrições mais comum são associadas a: restrições de cobertura, restrições de empacotamento e restrições de partição. Abordagem proposta para resolução do problema
i) O resolvedor proposto explora relações entre as variáveis tanto na fase construtiva quanto na fase de busca local por meio de grafos de conflitos. ii) O grafo de conflitos é construído através da detecção de pares de variáveis que não podem ser ativadas ao mesmo tempo. Os conflitos são detectados pelo processamento de cada restrição individualmente, checando pares de variáveis nesta restrição cuja ativação não pode ocorrer ao mesmo tempo, sem violá-la.

Iii) Nós conectados representam variáveis conflitantes.
Linhas tracejadas são desenhadas em grupos de variáveis, onde pelo menos uma variável deve ser ativada (restrições
= ou ⪰).
Perguntas
i) Vocês realmente acham que a abordagem proposta foi melhor que os resolvedores