Gerando problemas interessantes de otimização combinatória

9

Estou ministrando um curso sobre meta-heurísticas e preciso gerar instâncias interessantes de problemas combinatórios clássicos para o termo projeto. Vamos nos concentrar no TSP. Estamos lidando com gráficos de dimensão e maiores. Naturalmente, tentei gerar um gráfico com uma matriz de custos com valores retirados de um aleatório e descobri que (como esperado) o histograma para o custo do caminho (desenhado por amostragem de muitos caminhos aleatórios) tem uma distribuição normal muito estreita ( é mas é em torno de ). Isso significa, na minha opinião, que o problema é muito fácil, pois a maioria dos caminhos aleatórios estará abaixo da média e o caminho de custo mínimo está muito próximo de um caminho aleatório.200U(0,1)μ 100σ4

Então, tentei a seguinte abordagem: Depois de gerar a matriz , faça uma longa caminhada aleatória pelo gráfico e aleatoriamente (Bernoulli com ) duplique ou reduza pela metade o valor da aresta. Isso tende a diminuir todos os valores, chegando finalmente a zero, mas se eu seguir o número certo de etapas, posso obter uma distribuição com torno de e torno de .U(0,1)p=0.5μ2σ1

Minha pergunta é: primeiro, essa é mesmo uma boa definição para um problema interessante ? Idealmente, eu gostaria de uma instância que seja altamente multimodal (para as funções de vizinhança mais comuns) e que tenha muito poucos caminhos próximos ao valor mínimo, para que a maioria das soluções aleatórias fique muito longe do ideal. A segunda pergunta é, dada essa descrição, como posso gerar instâncias com essas características?

Alejandro Piad
fonte
3
Procure bibliotecas de benchmarks de TSP, como estudadas em OR (por exemplo, procure trabalhos sobre TSP por Applegate et al., Por exemplo, aqui )?
Neal Young
2
Existe o TSPLIB com muitas instâncias.
Adriann
Obrigado, verifiquei o link e é útil, mas minha pergunta é sobre a geração de instâncias, não porque quero resolver uma instância específica, mas porque busco uma visão do que cria bons problemas combinatórios, uma visão que pode ser estendida posteriormente para outros problemas além do TSP.
27313 Alejandro Piad
post relacionado: cstheory.stackexchange.com/questions/739/…
Neal Young
11
@Alejandro, O problema do clique oculto pode ser um exemplo do que você está procurando. Além disso, você pode pesquisar sobre quais instâncias aleatórias de satisfação são consideradas difíceis.
Neal Young

Respostas:

6

Uma abordagem geral para gerar instâncias mais difíceis é a seguinte:

  • Comece com uma instância de problema aleatório.
  • Incorpore um "backdoor oculto": escolha aleatoriamente uma boa solução (que provavelmente será muito melhor do que qualquer solução que já exista) e modifique a instância do problema para incorporá-la à força na instância do problema.

você(0 0,1 1)você(0 0,c)c<1 1; reduzir o peso existente; ou modifique a aresta existente com alguma probabilidade fixa). Esse procedimento de ajuste garante que a solução ideal seja, com alta probabilidade, o tour especial que você selecionou. Se você tiver sorte e selecionar uma incorporação razoável, também não será tão fácil reconhecer onde você escondeu a solução especial.

Essa abordagem é derivada de idéias gerais em criptografia, nas quais queremos criar problemas de alçapão unidirecional: onde o problema é difícil de resolver sem o conhecimento do alçapão secreto, mas com o conhecimento do alçapão secreto, o problema se torna muito fácil. Houve muitas tentativas de incorporar alçapões secretos em uma variedade de problemas difíceis (enquanto preservava a dureza do problema mesmo após a adição do alçapão), com graus variados de sucesso. Mas essa abordagem geral parece viável, para seus propósitos.

As instâncias de problemas resultantes podem ser difíceis , mas serão interessantes , de qualquer perspectiva prática? Eu não sei. Me bate. Eles parecem bastante artificiais para mim, mas o que eu sei?

Se seu objetivo principal é selecionar instâncias de problemas que sejam praticamente relevantes e representativas dos aplicativos do TSP no mundo real, minha sugestão seria adotar uma abordagem totalmente diferente. Em vez disso, comece pesquisando aplicativos do TSP do mundo real, procurando instâncias representativas desses problemas e convertendo-os na instância de problema do TSP correspondente - para trabalhar com instâncias de problemas derivadas de um problema do mundo real.

DW
fonte
Eu gosto muito dessa abordagem, na verdade é muito próxima do que eu estava tentando criar e parece bastante adaptável a diferentes problemas. Minha motivação inicial era criar problemas de teste para os alunos, por isso, embora eu receba os problemas da palavra real, mas me sirva bem para essa situação bastante artificial (tentando avaliar os algoritmos dos alunos). De qualquer forma, procurarei adaptá-lo também para minhas necessidades de pesquisa, mas isso precisará de uma análise mais detalhada, como você diz, para determinar se as instâncias criadas são representativas o suficiente. Muito obrigado, você recebeu meu +1 e aceitação.
Alejandro Piad
3

Uma abordagem que geralmente oferece alto controle sobre a natureza das soluções é a conversão de um problema completo de NP para outro. agora você define "interessante" em sua pergunta de maneira estatística, mas outra abordagem interessante é usar problemas clássicos do campo. meu favorito é fatorar / SAT. é trivial encontrar números "suaves" com muitos fatores ou números primos com apenas dois "fatores" (um e o primo). crie a instância SAT para resolver o fatoração, e as soluções são os fatores (na verdade permutações de fatores, mas também que não são difíceis de contar antecipadamente).

sob essa abordagem, existe uma definição natural de "interessante" - instâncias difíceis que não podem ser resolvidas no tempo P. e é garantido que essa abordagem produz instâncias difíceis para fatorar números não suaves, caso contrário, resolveria uma questão em aberto na teoria da complexidade, ou seja, dureza de fatorar .

então, possivelmente converta para o seu problema, neste caso o TSP. Para preencher esta resposta, seria bom ter uma conversão direta de SAT para TSP, acho que eles estão por aí, mas não estou familiarizado com eles. no entanto, aqui estão algumas referências sobre fatoração para SAT nesta pergunta: reduzindo o problema de fatoração de número inteiro para um problema completo de NP

se você não gosta de fatorar, ainda assim pode ser preferível criar as instâncias no SAT primeiro por vários motivos. você pode começar com instâncias SAT aleatórias ajustadas para centralizar no ponto de transição fácil-difícil-fácil, etc. ou você pode trabalhar a partir de instâncias rígidas do DIMACS , geradas pela comunidade. ou crie outros "programas" lógicos no SAT.

vzn
fonte
11
Gosto da abordagem de conversão, embora você não forneça outros links especificamente relacionados ao TSP, mas, de qualquer forma, obrigado pela ideia, vou explorá-la mais profundamente. Você recebeu meu +1.
Alejandro Piad
11
@alejandro thx ok aqui está um link sobre isso. veja, por exemplo, começando no slide 28 aqui [aula de graduação!], CMSC 451: SAT, Coloração, Ciclo Hamiltoniano, TSP Slides Por: Carl Kingsford . conversão SAT → ciclo hamiltoniano (TSP). pode haver abordagens de conversão mais eficientes (com menos sobrecarga) ou com outros aspectos personalizados da literatura, se é o que se deseja. Esperamos ouvir mais do seu trabalho, talvez responder aqui ou no meu blog se você gosta
vzn
11
Eu verifiquei o pdf, nível muito alto, mas compreensível o suficiente. Embora, por enquanto, eu tenha o que preciso com a resposta @DW, sua abordagem parece muito interessante para mim. Vou ter que tentar sozinho. Eu já havia visto a redução anteriormente (em um curso de complexidade), mas não havia pensado em uma implementação real especificamente para criar instâncias difíceis. Tenho um interesse de longo prazo em otimização e metaheurísticas, e uma das minhas áreas de interesse é a criação de problemas interessantes de benchmark. Aliás, acabei de conferir o seu blog, voltarei com certeza !!!
Alejandro Piad