NP-Complentis pour le programme linéaire entier

Question

Ceci est un problème de devoirs, donc je ne veux pas la solution.J'ai besoin d'un indice Quel problème pour réduire les éléments suivants et / ou comment commencer.Nous pensions à TSP ou à un ensemble indépendant mais ne pouvait pas venir avec une solution.

nous avons $ i \ ldots j $ magasins et $ i \ ldots n $ lieux possibles pourconstruire un nouvel entrepôt.Les coûts pour construire un nouvel entrepôt sont $ C_J $ .Entre chaque magasin et entrepôt est un chemin du coût $ d_ {i, j} $ .Chaque magasin doit être connecté à au moins un entrepôt.

Le problème de décision est: existe-t-il un ensemble d'entrepôts et de chemins de sorte que la somme soit inférieure à un nombre donné $ k $

.

.

Answer 1

Ceci est un classique Problème de localisation de l'installation . Cet article de Wikipedia suggère que la dureté de la NP peut être prouvée par la réduction de Set Cover .

---

Étant donné que l'astucieux a maintenant déclaré avoir trouvé une solution en réduisant de couvre-la-Vertex , je vais révéler la réduction de Set Cover :

Pour chaque valeur, créez un magasin; Pour chaque ensemble, créez un entrepôt. Attribuez le coût de chaque entrepôt à être 1. Attribuer le coût de la route à partir d'un entrepôt à un magasin pour être une valeur de manière arbitraire si cet ensemble de l'entrepôt contient la valeur de ce magasin, ou une valeur arbitraire importante autrement. Ensuite, la solution de coûts minimale au problème de l'installation construit précisément l'ensemble des entrepôts correspondant au couvercle de jeu minimal dans le problème d'origine.
de
La valeur $ K $ est utilisée pour activer le problème d'optimisation (minimiser les ensembles / coûts) dans un problème de décision (y a-t-il une solution sans plus que $ K $ ensembles / coût?). La $ k $ de l'instance de couverture de jeu sera identique à la $ k $ dans le problème de l'installation instance Si vous êtes autorisé à définir les valeurs "arbitrairement petites" à 0 - sinon, sinon, vous devrez peut-être fudger la valeur par une certaine quantité, mais moins de 1 aussi longtemps que vous choisissez les poids "arbitrairement petits" pour être suffisamment petit. Vous avez juste besoin du total de chaque coût "arbitrairement petit" pour être inférieur à 1, et chaque coût "arbitrairement large" d'être supérieur à la somme des coûts de tous les entrepôts et de tous les itinéraires "arbitrairement petits".
de
Notez que, si seuls les coûts entier sont autorisés dans le problème des installations, vous pouvez toujours obtenir le même résultat en modifiant tous les coûts par leur multiple le moins commun.