NP-completude para o programa linear inteiro

Question

Este é um problema de lição de casa, então eu não quero a solução.Eu preciso de uma dica que problema para reduzir o seguinte e / ou como começar nele.Nós estávamos pensando em TSP ou conjunto independente, mas não podia chegar a uma solução.

Temos $ i \ ldots j $ lojas e $ i \ ldots n $ possíveis lugares paraconstruir um novo armazém.Custos para construir um novo armazém são $ c_j $ .Entre cada loja e armazém é um caminho de custo $ D_ {I, J} $ .Cada loja precisa ser conectada a pelo menos um armazém.

O problema da decisão é: Existe um conjunto de armazéns e caminhos para que a soma seja menor do que um determinado número $ k $ .

Answer 1

Este é um clássico problema de localização de facilidade . Que o artigo da Wikipedia sugere que a dureza NP pode ser comprovada por redução de conjunto de conjunto .

---

Desde que o Oitador agora afirmou ter encontrado uma solução, reduzindo da tampa do vértice , eu irei em frente e revelará a redução da tampa de conjunto :

Para cada valor, crie uma loja; Para cada conjunto, crie um armazém. Atribuir o custo de cada depósito a ser 1. Atribuir o custo da rota de um depósito para uma loja para ser um valor arbitrariamente pequeno se o conjunto do armazém contiver o valor desse armazenamento, ou um valor arbitrariamente grande caso contrário. Em seguida, a solução mínima de custo para o problema da instalação constrói precisamente o conjunto de armazéns correspondentes à tampa mínima do conjunto no problema original.



A $ k $ valor é usado para ativar o problema de otimização (minimizar conjuntos / custo) em um problema de decisão (há uma solução sem mais do que $ k $ conjuntos / custo?). A $ K $ Na instância de capa definida será a mesma que a $ k $ no problema da instalação Instância Se você for permitido definir os valores "arbitrariamente pequenos" para exatamente 0 - caso contrário, talvez você tenha que impulsionar o valor por algum valor, mas menos de 1 contanto que você escolha os pesos "arbitrariamente pequenos" para serem pequenos o suficiente. Você só precisa do total de cada custo "arbitrariamente pequeno" para ser inferior a 1, e todo custo "arbitrariamente grande" para ser maior do que a soma dos custos de todos os armazéns e todas as rotas "arbitrariamente pequenas".



Observe que, se apenas os custos inteiros forem permitidos no problema das instalações, você ainda pode obter o mesmo resultado, escalonando todos os custos por meio de múltiplos menos comuns.