Problème: la vente de Bob

Question

Note: ceci est un résumé, une reformulation d'un problème de la vie réelle concernant les commandes d'enregistrements dans un fichier SWF. Une solution va m'aider à améliorer une application open-source.

Bob a un magasin, et veut faire une vente. Son magasin porte un certain nombre de produits, et il y a un certain entier quantité d'unités de chaque produit en stock. Il a également un certain nombre de plateau monté sur des étiquettes de prix (autant que le nombre de produits), avec les prix déjà imprimé sur eux. Il peut placer n'importe quel prix étiquette sur un produit (prix unitaire d'un article pour l'ensemble de son stock de ce produit), toutefois, certains produits ont une restriction supplémentaire - ce produit peut ne pas être moins cher que celui d'un autre produit.

Vous devez trouver comment organiser les étiquettes de prix, tels que le coût total de l'ensemble de Bob marchandises est aussi faible que possible. Le coût total est la somme de chaque produit de l'étiquette de prix multiplié par la quantité de ce produit en stock.

---

Donnée:

• N – le nombre de produits et des étiquettes de prix
• S_i, 0≤i<N – la quantité en stock du produit avec l'indice i (entier)
• P_j, 0≤j<N – le prix sur l'étiquette de prix avec l'indice j (entier)
• K – le nombre de contrainte supplémentaire paires
• A_k, B_k, 0≤k<K – produit des indices pour la contrainte supplémentaire
  • Tout produit de l'indice peut apparaître plus d'une fois dans B. Ainsi, le graphe formé par cette liste d'adjacence est en fait un ensemble de dirigé les arbres.

Le programme doit trouver:

• M_i, 0≤i<N – cartographie à partir du produit de l'indice de prix étiquette de l'indice (P_Mi est le prix du produit i)

Pour satisfaire les conditions suivantes:

1. P_MUnk ≤ P_MBkpour 0≤k<K
2. Σ(S_i × P_Mi) pour 0≤i<N est minime

---

Notez que si ce n'est pour la première condition, la solution serait tout simplement de tri des étiquettes de prix et les produits en quantité, et correspondant à la fois directement.

Les valeurs typiques pour l'entrée sera N,K<10000. Dans le problème de la vie réelle, il y a seulement plusieurs étiquettes de prix (1,2,3,4).

---

Voici un exemple de pourquoi la plupart des solutions simples (y compris le tri topologique) ne fonctionne pas:

Vous disposez de 10 éléments avec les quantités de 1 à 10, et 10 étiquettes de prix avec le prix de $1 à $10. Il y a une condition: le point avec la quantité de 10 ne doit pas être moins cher que l'élément avec la quantité 1.

La solution optimale est:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

avec un coût total de $249. Si vous placez le 1,10 paire près de l'extrême, le coût total sera plus élevé.

Answer 1

Le problème est NP-complet dans le cas général. Cette situation peut être illustrée par une réduction de 3-partition (ce qui est encore forte NP-complet version de bin packing).

Laissez w₁, ..., w_n être le poids des objets de la 3-partition d'exemple, permettez - b soit la taille de sa corbeille, et k = n/3 le nombre de bacs qui sont autorisés à être rempli. Donc, il y a un 3-partition si les objets peuvent être partitionnés telle qu'il y a exactement 3 objets par bin.

Pour la réduction, on pose N=kb et chaque cellule est représentée par b des étiquettes de prix de la même prix (P_j' augmente chaque bth étiquette). Permettez - t_i, 1≤i≤k, le prix des étiquettes correspondant à la ième bin. Pour chaque w_i nous avons un produit de S_j de la quantité w_i + 1 (appelons cela la racine produit de w_i) et un autre w_i - 1 produits de la quantité 1 qui sont nécessaires pour être moins cher que S_j (appeler ces le congé de produits).

Pour t_i = (2b + 1)ⁱ, 1≤i≤k, il y a un 3-partition si et seulement si Bob peut se vendre pour 2bΣ_1≤i≤kt_i:

• Si il y a une solution de 3-partition, puis tous les b des produits correspondant à des objets w_i, w_j, w_l qui sont affectés à la même cellule peut être étiquetés avec le même prix, sans violer les restrictions. Ainsi, la solution a coûté 2bΣ_1≤i≤kt_i (puisque la quantité totale de produits avec des prix t_i est 2b).
  
• Envisager une solution optimale de Bob Vente. D'abord observer que dans n'importe quelle solution ont été plus de 3 racine de produits partagent le même prix de l'étiquette, pour chaque racine produit qui est "trop", il y a une étiquette de prix plus bas qui colle le sur moins de 3 produits racine. C'est pire que n'importe quelle solution il y a exactement 3 produits racine par le prix de l'étiquette (si existant).
  Maintenant, il peut encore être une solution de Bob Vente avec 3 racine étiquettes par le prix, mais de leur laisser les produits ne portent pas la même des étiquettes de prix (les poubelles de tri de flux de plus). Dire le plus cher de prix étiquette étiquettes de racine produit de w_i qui a un moins cher tagged congé de produit. Cela implique que les 3 racine étiquettes w_i, w_j, w_l marqués le plus cher n'est pas égal à b. Par conséquent, le coût total des produits taggés avec ce prix, c'est au moins 2b+1.
  Par conséquent, une telle solution a coûté t_k(2b+1) + quelques autres coûts d'attribution. Depuis le coût optimal pour un existant 3-partition 2bΣ_1≤i≤kt_i , nous devons montrer que la juste considérés comme des cas est pire. C'est le cas si t_k > 2b Σ_1≤i≤k-1t_i (a noter qu'il est k-1 dans la somme maintenant). Paramètre t_i = (2b + 1)ⁱ, 1≤i≤k, c'est le cas. Ceci vaut également si ce n'est le plus cher de l'étiquette de prix est le "mauvais", mais toutes les autres.

Donc, c'est la destruction de la partie ;-) Toutefois, si le nombre de différentes étiquettes de prix est une constante, vous pouvez utiliser la programmation dynamique pour résoudre en temps polynomial.

Answer 2

Ce problème ressemble à de nombreux problèmes de planification considéré dans la CS de la littérature. Permettez-moi de reformuler ce que l'un.

Problème ("nonpreemptive seul ordinateur dans la planification, la priorité, de poids, et en général des pénalités de retard")

Entrée:

• emplois 1, ..., n

• un "arborescente" la priorité lien prec sur les tâches (diagramme de Hasse est une forêt)

• poids w₁, ..., w_n

• un nondecreasing pénalité de retard de la fonction L(t) à partir de {1, ..., n} de Z₊

Sortie:

• une permutation π {1, ..., n} minimiser ∑_j w_j L(π(j)), sous réserve des restrictions que pour tout i prec j nous avons π(i) < π(j).

Correspondance: travail <=> produit; je prec j <=> je dispose d'un prix inférieur à celui de j; poids <=> quantité; L(t) <=> t^th prix le plus bas

Lorsque L est linéaire, il est efficace d'un polynôme en temps de l'algorithme en raison de la Corne [1]. L'article est derrière un mur à péage, mais l'idée principale est

1. Pour tous j, trouver connecté à l'ensemble des travaux ne contenant que j et de ses successeurs, dont le poids moyen est maximal. Par exemple, si n = 6) et les contraintes de précédence sont 1 prec 2 et 2 prec 3 et 2 prec 4 et 4 prec 5, ensuite, les ensembles, en vertu de la considération pour les 2 {2}, {2, 3}, {2, 4}, {2, 3, 4}, {2, 4, 5}, {2, 3, 4, 5}. Nous avons en fait besoin que de la moyenne maximale de poids, qui peut être calculée de bas en haut par la programmation dynamique.

2. La planification de travaux avidement dans l'ordre de la moyenne du poids de leurs associés ensembles.

Dans CyberShadow de l'exemple, nous avons n = 10 et 1 prec 10 et w_j = j et L(t) = t. Les valeurs calculées dans l'Étape 1 sont

• job 1: 5.5 (moyenne de 1 et 10)

• job 2: 2

• job 3: 3

• job 4: 4

• job 5: 5

• job 6: 6

• job 7: 7

• job 8: 8

• job 9: 9

• job 10: 10

L'ordre optimal est 9, 8, 7, 6, 1, 10, 5, 4, 3, 2.

---

Cet algorithme pourrait bien fonctionner dans la pratique, même pour un choix différent de L, comme la preuve de l'optimalité utilise d'amélioration locale. Sinon, peut-être quelqu'un sur le CS de la Théorie de la Pile d'Échange pour se faire une idée.

[1] W. A. Horn. Une seule Machine de Travail de Séquençage avec Arboriforme Priorité de la Commande Linéaire et Pénalités de Retard. SIAM Journal on Applied Mathematics, Vol. 23, N ° 2 (Sep., 1972), pp. 189-202.

Answer 3

Car je pensais que le problème était amusant, j'ai fait un modèle pour la recherche de solutions utilisant la programmation par contraintes. Le modèle est écrit dans un langage de modélisation appelé MiniZinc.

include "globals.mzn";

%%% Data declaration
% Number of products
int: n;
% Quantity of stock
array[1..n] of int: stock;
% Number of distinct price labels
int: m;
% Labels
array[1..m] of int: labels;
constraint assert(forall(i,j in 1..m where i < j) (labels[i] < labels[j]),
              "All labels must be distinct and ordered");
% Quantity of each label
array[1..m] of int: num_labels;
% Number of precedence constraints
int: k;
% Precedence constraints
array[1..k, 1..2] of 1..n: precedences;

%%% Variables
% Price given to product i
array[1..n] of var min(labels)..max(labels): prices :: is_output;
% Objective to minimize
var int: objective :: is_output;

%%% Constraints
% Each label is used once
constraint global_cardinality_low_up_closed(prices, labels, num_labels, num_labels);

% Prices respect precedences
constraint forall(i in 1..k) (
            prices[precedences[i, 1]] <= prices[precedences[i, 2]]
       );

% Calculate the objective
constraint objective = sum(i in 1..n) (prices[i]*stock[i]);

%%% Find the minimal solution
solve minimize objective;

Données pour un problème donné dans un fichier séparé.

%%% Data definitions
n = 10;
stock = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
m = 10;
labels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
num_labels = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
k = 1;
precedences = [| 1, 10 |];

Le modèle est assez naïf et simple, pas de fantaisie. À l'aide de la Gecode back-end pour résoudre l'exemple, la sortie suivante est générée (en supposant que le modèle est dans le modèle.mzn et les données dans les données.dzn)

$ mzn2fzn -I/usr/local/share/gecode/mznlib/ model.mzn data.dzn
$ fz -mode stat -threads 0 model.fzn 
objective = 265;
prices = array1d(1..10, [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]);
----------
objective = 258;
prices = array1d(1..10, [2, 10, 9, 8, 7, 6, 5, 4, 1, 3]);
----------
objective = 253;
prices = array1d(1..10, [3, 10, 9, 8, 7, 6, 5, 2, 1, 4]);
----------
objective = 250;
prices = array1d(1..10, [4, 10, 9, 8, 7, 6, 3, 2, 1, 5]);
----------
objective = 249;
prices = array1d(1..10, [5, 10, 9, 8, 7, 4, 3, 2, 1, 6]);
----------
==========

%%  runtime:       0.027 (27.471000 ms)
%%  solvetime:     0.027 (27.166000 ms)
%%  solutions:     5
%%  variables:     11
%%  propagators:   3
%%  propagations:  136068
%%  nodes:         47341
%%  failures:      23666
%%  peak depth:    33
%%  peak memory:   237 KB

Pour des problèmes plus importants, il est bien sûr beaucoup plus lent, mais le modèle sera généralement générer successivement les meilleures solutions dans le temps.

Answer 4

Poster quelques pensées comme un wiki de la communauté, n'hésitez pas à modifier.

Ce problème est plus facile à visualiser si vous pensez à des contraintes supplémentaires comme ayant pour aménager ou réaménager une série de haut en bas des arbres de telle manière que chaque nœud doit être à la droite de son parent (produits sur la gauche sont les moins chers et ceux de droite sont plus chers).

Disons que les deux produits sont en conflit si le premier a plus de stock que de la seconde, et pourtant, le premier ne doit pas être moins cher que les autres (alors qu'ils sont en train d'être "tiré" dans différentes directions de prix-sage). De même, un conflit avec un autre groupe de produits est un pays où au moins deux produits sont en conflit, et aucun de ses produits conflits avec n'importe quel produit à l'extérieur du groupe.

Nous pouvons faire quelques observations:

1. Lors de la "mise" (attribution d'une étiquette de prix pour) deux produits en conflit, ils seront toujours à côté les uns des autres.
2. Si vous triez tous les produits en quantité ignorant les contraintes, puis de les organiser de manière optimale, de sorte qu'ils satisfont les contraintes, les positions finales de tous les produits dans un conflit avec un autre groupe sera toujours entre (inclusivement) le plus à gauche et le plus à droite position initiale des produits.
3. Par conséquent, si vous pouvez fractionner une contrainte d'arbre en deux par la suppression d'un droit unique pointant vers le bord de l'arbre, tels que la gamme de produits " positions de départ, à partir du bas de la sous-arborescence et le chemin d'accès à la racine de l'arbre ne se chevauchent pas, vous pouvez en toute sécurité les traiter comme deux distincts contrainte arbres (ou nœuds simples) et d'oublier qu'il y a une dépendance entre eux. (simple exemple)

Un algorithme idée:

1. Tout d'abord, placez tous les produits ne sont pas liés par des restrictions.
2. Pour chaque contrainte de l'arbre:
   1. La découper en sous-arborescences sur tous dirigé vers la droite bords (les arêtes entre les produits en conflit). Nous avons maintenant un ensemble de sous-arbres avec tous bords pointant vers la gauche.
   2. Pour chaque sous-arbre:
      1. Obtenir topologiquement liste triée de
      2. Essayez d'insérer cette liste à chaque position de départ de la plus basse à la plus élevée positions initiales des produits dans ce sous-arbre, de s'installer sur celui qui cède le plus bas prix total
   3. Pour chacune des arêtes enlevées à l'étape 2.1:
      1. Si la création de postes pour les deux sous-arbres sont "contradictoires":
         1. Concaténer la plus élevée avec le bas de la liste (cas particulier de tri topologique)
         2. De même, essayez de trouver la position optimale pour la liste concaténée
         3. Pour l'avenir, de fusion, d'examiner les deux examiné les sous-arborescences comme une sous-arborescence

Le principal problème de cet algorithme est la façon de traiter avec le déplacement de déjà placé contraint paires. J'imagine que de simplement essayer de re-place déplacées chaînes par un processus itératif de recherche pourrait fonctionner, mais l'algorithme semble déjà trop compliqué de travailler à droite.

Dans le cas où le nombre d'agents de prix est faible, vous pouvez utiliser un deque (ou liste à double liaison) pour chaque prix, la tenue de tous les articles avec des prix attribués. Les deques sont classés du plus bas au plus haut prix. L'insertion d'un élément dans un deque décale le dernier élément dans le début de la prochaine deque (pour la prochaine plus distinctes de prix), et ainsi de suite pour tous les deques après.

Une chose à noter à propos de itératif / bubble-tri-ish algorithmes: lorsque vous avez un conflit avec un paire de produits, il n'est pas assez pour goulûment marche dans les deux sens par une position jusqu'à ce que le suivant ne permet pas d'obtenir une amélioration. Voici un test que j'ai obtenu en jouant un peu avec Mathematica l'écriture d'un scénario de test de générateur:

Price, $   1 2 7 9
Qty        3 2 1 4

La contrainte est d'avoir les 4-quantité de l'élément à droite de la 1-quantité de l'élément. Comme indiqué ci-dessus, le prix total est de 50$. Si vous déplacez la paire d'une position vers la gauche ( 3 1 4 2), le total monte à 51$, mais si vous allez une fois de plus (1 4 3 2) il descend à 48 dollars.

Answer 5

C'est un suivi de Gero réponse. L'idée est de modifier sa construction solide NP-dureté.

Au lieu de choisir $t_i=(2b+1)^i$, a choisi de $t_i=i$. Maintenant, vous devez modifier l'argument qu'une solution avec des prix $P=2b\sum_{1\leq i \leq k} t_i$ implique qu'il existe une 3-partition.

Prendre l'arbitraire d'un plateau de commande. Faire la comptabilité de la manière suivante: distribuer $w_i-1$ unités de quantité, de la racine-produit de sa feuille-produits. Ensuite, chaque produit a une quantité de 2. Par définition des contraintes, ce n'est pas le passage à un prix plus élevé. Après ce déplacement, le prix sera exactement $P$. Si le déplacement déplacé une certaine quantité pour un faible prix, le prix original est strictement plus grand que $P$.

Par conséquent, il est seulement possible d'atteindre le prétendu prix, si toutes les feuilles-les produits ont le même prix que leur racine-produit, ce qui signifie qu'il existe une 3-partition.

Citant le résultat d'un SWAT 2010 papier cet argument montre que même avec unaire codage des nombres et $k$ de différentes étiquettes de prix, et un temps de fonctionnement de $f(k)\cdot n^{O(1)}$ violerait "le standard de la complexité des hypothèses". Cela rend l'allusion à la programmation dynamique avec un temps de fonctionnement de $n^{O(k)}$ ne regarde pas si mauvais.

---

C'est faire à partir de la même réponse à cstheory.