Optimiser les demandes cartésiennes avec des coûts affine

https://stackoverflow.com/questions/1403933

05-07-2019
|

Question

J'ai une demande d'optimisation des coûts que je ne sais pas s'il existe de la documentation. C'est un peu difficile à expliquer, je m'excuse par avance pour la longueur de la question.

Il y a un serveur auquel j'accède qui fonctionne de cette façon:

une requête est faite sur les enregistrements (r1, ... rn) et les champs (f1, ... fp)
vous pouvez uniquement demander le produit cartésien (r1, ..., rp) x (f1, ... fp)
Le coût (en temps et en argent) associé à une telle requête est de taille moindre:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Sans perte de généralité (juste en normalisant), nous pouvons supposer que b=1 le coût est donc:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

Je n'ai besoin que de demander un sous-ensemble de paires (r1, f(r1)), ... (rk, f(rk)), une demande qui provient des utilisateurs. Mon programme agit en tant qu'intermédiaire entre l'utilisateur et le serveur (qui est externe). J'ai beaucoup de demandes comme celle-ci (des dizaines de milliers par jour).

Graphiquement, nous pouvons l’imaginer comme une matrice nx p-sparse, pour laquelle je souhaite couvrir les valeurs non nulles avec une sous-matrice rectangulaire:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Avoir:

le nombre de sous-matrices étant maintenu raisonnable en raison du coût constant
tous les 'x' doivent se trouver dans une sous-matrice
la surface totale couverte ne doit pas être trop grande à cause du coût linéaire

Je nommerai g le coefficient de dispersion de mon problème (nombre de paires nécessaires par rapport au nombre total de paires possibles, g = k / (n * p). Je connais le coefficient a.

Il y a des observations évidentes:

si a est petit, la meilleure solution consiste à demander chaque paire (enregistrement, champ) de manière indépendante, et le coût total est: k * (a + 1) = g * n * p * (a + 1)
si a est grand, la meilleure solution est de demander le produit cartésien complet, et le coût total est de: a + n * p
la deuxième solution est meilleure dès que g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
bien sûr, les commandes dans les produits cartésiens n’ayant aucune importance, je peux donc transposer les lignes et les colonnes de ma matrice pour la rendre plus facilement recouvrable, par exemple:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

peut être réorganisé comme

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

Et il existe une solution optimale qui consiste à demander (f1,f3) x (r1,r3) + (f2) x (r2)

Essayer toutes les solutions et rechercher le coût le plus bas n’est pas une option, car la combinatoire explose:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

donc je cherche une solution approximative. J'ai déjà une sorte d'algorithme glouton qui trouve une couverture donnée à une matrice (il commence par des cellules unitaires, puis les fusionne si la proportion de cellules vides dans la fusion est inférieure à un seuil).

Pour ne citer que quelques chiffres, mon n est compris entre 1 et 1000 et mon p entre 1 et 200. Le schéma de couverture est vraiment "bloc", car les enregistrements sont dans des classes pour lesquelles les champs demandés sont similaires. . Malheureusement, je ne peux pas accéder à la classe d'un disque ...

Question 1 : Quelqu'un a-t-il une idée, une simplification astucieuse ou une référence pour un document qui pourrait être utile? Comme je reçois beaucoup de demandes, je cherche un algorithme qui fonctionne bien en moyenne en moyenne (mais je ne peux pas me permettre de le faire très mal dans certains cas extrêmes, par exemple en demandant à l'ensemble matrice lorsque n et p sont volumineux et que la demande est en effet assez rare).

Question 2 : En fait, le problème est encore plus compliqué: le coût ressemble en fait davantage à la forme: a + n * (p^b) + c * n' * p', où b est une constante < 1 (une fois qu'un enregistrement est demandé pour un champ, il n'est pas trop coûteux de demander d'autres champs) et n' * p' = n * p * (1 - g) est le nombre de cellules que je ne souhaite pas demander (car elles sont invalides et entraînent des coûts supplémentaires en demandant des choses invalides). Je ne peux même pas rêver d’une solution rapide à ce problème, mais quand même ... une idée n’importe qui?

La solution

La sélection des sous-matrices pour couvrir les valeurs demandées est une forme du problème de recouvrement et donc NP complète. Votre problème ajoute à ce problème déjà difficile que les coûts des ensembles diffèrent.

Le fait que vous autorisiez la permutation des lignes et des colonnes n’est pas un gros problème, car vous pouvez simplement envisager des sous-matrices déconnectées. Ligne un, colonnes quatre à sept et ligne cinq, colonnes quatre deux sept sont un ensemble valide, car vous pouvez simplement échanger les lignes deux et cinq et obtenir la sous-matrice connectée ligne un, colonne quatre à ligne deux, colonne sept. Bien sûr, cela va ajouter des contraintes - tous les ensembles ne sont pas valables sous toutes les permutations - mais je ne pense pas que ce soit le plus gros problème.

L'article de Wikipedia donne les résultats inapproximables que le problème ne peut pas être résolu en temps polynomial mieux qu'avec un facteur 0.5 * log2(n) où n est le nombre de jeux. Dans votre cas, 2^(n * p) est une limite supérieure (assez pessimiste) pour le nombre d'ensembles et de rendements que vous ne pouvez trouver une solution que dans un facteur 0.5 * n * p en temps polynomial (outre N = NP et en ignorant les coûts variables) .

Une limite inférieure optimiste pour le nombre de jeux ignorant les permutations de lignes et de colonnes est 0.5 * n^2 * p^2 donnant un bien meilleur facteur de log2(n) + log2(p) - 0.5. En conséquence, vous ne pouvez espérer trouver une solution que dans le pire des cas n = 1000 et p = 200 jusqu’à un facteur d’environ 17 dans le cas optimiste et jusqu’à un facteur d’environ 100.000 dans le cas pessimiste ( toujours en ignorant les coûts variables).

Le mieux que vous puissiez faire est donc d’utiliser un algorithme heuristique (l’article de Wikipédia mentionne un algorithme glouton presque optimal) et d’accepter le fait que l’algorithme sera (très) mauvais. Sinon, vous utilisez un algorithme d'optimisation et essayez de trouver une bonne solution en utilisant plus de temps. Dans ce cas, je suggérerais d'essayer d'utiliser la recherche A * .

Autres conseils

Je suis sûr qu'il existe un très bon algorithme pour cela quelque part, mais voici mes propres idées intuitives:

Approche à base de rectangles:
- Déterminez un "ient approximativement optimal " taille du rectangle basée sur a .
- Placez ces rectangles (peut-être de manière aléatoire) sur vos points requis, jusqu'à ce que tous les points soient couverts.
- Maintenant, prenez chaque rectangle et réduisez-le autant que possible sans & "perdre &"; des points de données.
- Trouvez des rectangles proches les uns des autres et décidez si les combiner coûterait moins cher que de les séparer.
grandir
- Commencez avec chaque point dans son propre rectangle 1x1.
- Localisez tous les rectangles dans n lignes / colonnes (n pouvant être basé sur a ); voyez si vous pouvez les combiner en un seul rectangle gratuitement (ou négatif: D).
- Répéter.
Réduire
- Commencez avec un grand rectangle qui couvre TOUS les points.
- Recherchez un sous-rectangle qui partage une paire de côtés avec le grand, mais contient très peu de points.
- Découpez-le dans le grand pour obtenir deux rectangles plus petits.
- Répéter.
Quad
- Divisez le plan en 4 rectangles. Pour chacun d’eux, voyez si vous obtenez un meilleur coût en récursant davantage ou en incluant tout le rectangle.
- Maintenant, prenez vos rectangles et voyez si vous pouvez les fusionner avec un coût minime ou nul. \

Aussi: gardez à l'esprit qu'il sera parfois préférable d'avoir deux rectangles qui se chevauchent plutôt qu'un grand rectangle qui en est un sur-ensemble. Par exemple. le cas où deux rectangles se chevauchent juste dans un coin.

Ok, ma compréhension de la question a changé. Nouvelles idées:

Stocke chaque ligne en tant que chaîne de bits longue. ET paires de chaînes de bits ensemble, en essayant de trouver des paires qui maximisent le nombre de 1 bits. Développez ces paires en groupes plus importants (triez et essayez de faire correspondre les plus gros entre eux). Construisez ensuite une demande qui atteindra le groupe le plus important, puis oubliez tous ces bits. Répétez jusqu'à ce que tout soit terminé. Peut-être parfois passer de lignes en colonnes.
Recherchez toutes les lignes / colonnes contenant zéro ou peu de points. " Supprimer " les temporairement. Maintenant, vous regardez ce qui serait couvert par une demande qui les exclut. Maintenant, appliquez peut-être l'une des autres techniques et résolvez ensuite les lignes / colonnes ignorées. Une autre façon de penser est de traiter d'abord les points les plus denses, puis de passer aux points les plus clairsemés.

Étant donné que vos valeurs sont rares, se pourrait-il que de nombreux utilisateurs demandent des valeurs similaires? La mise en cache dans votre application est-elle une option? Les demandes peuvent être indexées par un hachage fonction de la position (x, y), de sorte que vous puissiez facilement identifier les ensembles mis en cache qui se trouvent dans la zone correcte de la grille. Stocker les ensembles mis en cache dans une arborescence, par exemple, vous permettrait de trouver très rapidement les sous-ensembles minimums en cache qui couvrent la plage de demandes. Vous pouvez ensuite effectuer une recherche linéaire sur le sous-ensemble, ce qui est petit.

Je considérerais les n enregistrements (lignes) et les champs p (cols) mentionnés dans le jeu de demandes utilisateur sous la forme de n points dans un espace à une dimension p ({0,1} ^ p), la coordonnée étant 1 si et seulement si a un X et identifie une hiérarchie de clusters , avec le cluster le plus grossier à la racine, incluant tous le X. Pour chaque noeud de la hiérarchie de clustering, considérons le produit qui couvre toutes les colonnes nécessaires (il s'agit des lignes (n'importe quel sous-noeud) x cols (n'importe quel sous-noeud)). Décidez ensuite, de bas en haut, de fusionner les couvertures enfants (en payant l’ensemble des couvertures) ou de les conserver en tant que demandes séparées. (les revêtements ne sont pas des colonnes contiguës, mais exactement celles qui sont nécessaires; je pense à un vecteur de bits)

Je conviens avec Artelius que le chevauchement des demandes de produits pourrait être moins coûteux; mon approche hiérarchique aurait besoin d’être améliorée pour l’intégrer.

J'y ai travaillé un peu, et voici un algorithme évident, O (n ^ 3) gourmand, qui rompt la symétrie (les enregistrements et les champs sont traités séparément) dans un pseudo-code de type python.

L’idée est triviale: nous commençons par essayer une requête par enregistrement et nous effectuons la fusion la plus utile jusqu’à ce qu’il ne reste plus rien à faire. Cet algo a l'inconvénient évident qu'il ne permet pas les requêtes qui se chevauchent, mais je m'attends à ce qu'il fonctionne assez bien dans les cas réels (avec la fonction de coût a + n * (p^b) + c * n * p * (1 - g)):

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

C’est O (n3 * p) car:

après l’initialisation, nous commençons par n requêtes
la boucle while supprime exactement une demande du pool à chaque itération.
la boucle interne for itère sur les (ni^2 - ni) / 2 paires de requêtes distinctes, ni allant de n à un dans le pire des cas (lorsque nous fusionnons le tout en une seule grande requête).
1. Quelqu'un peut-il m'aider à signaler les très mauvais cas de l'algorithme? Cela vous semble-t-il raisonnable d’utiliser celui-ci?
2. C’est O (n ^ 3), ce qui est beaucoup trop coûteux pour de gros intrants. Une idée pour l'optimiser?

Merci d'avance!

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow