Optimisation combinatoire, problème d'allocation

Question

J'essaie de résoudre un problème (dans pyspark / python) où je dois trouver deux valeurs distinctes à allouer, et comment les allouer dans un réseau de magasins.

Les deux valeurs distinctes ne peuvent être que des valeurs entières et contraintes entre une limite inférieure et supérieure. Pour chaque paire de valeurs distinctes, disons 4 et 8, chaque magasin peut obtenir 4 ou 8, ce qui donne un total de 2 ⁿ modes d'allocation différents s'il y a n magasins ( n est proche de 1000).

La fonction objectif est complexe et utilise des modèles prédictifs pour donner l'impact d'une paire de valeurs particulière correspondant à son allocation dans le réseau.

J'espérais pouvoir créer une fonction de coût du formulaire:

Cost  = f( variant1, variant2, store_1_variant, store_2_variant, ..., store_n_variant)

où

• variant1 = 4 (entier, contraint dans une valeur max)
• variant2 = 8 (entier, contraint dans une valeur max)
• store_1_variant, ..., store_n_variantsont binaires [0,1] pour suggérer s'ils reçoivent variant_1ou non (ne pas recevoir variant1signifierait recevoir variant2)

Je pourrais résoudre les paramètres n + 2 qui minimisent le coût (il y a une autre contrainte qui doit garder sous contrôle l'impact d'une certaine allocation)

J'ai examiné diverses techniques d'optimisation combinatoire, mais aucune ne semble me permettre une fonction définie par l'utilisateur comme fonction de coût.

Je n'ai aucune expérience préalable dans ce domaine donc toute direction / assistance est appréciée.

Éditer

Pour ajouter quelques informations sur la forme actuelle de la fonction de coût, continuer avec l'exemple de deux variantes étant 4 et 8 avec disons 5 magasins, f(4, 8, 0, 1, 1, 0, 0)aura un coût associé du formulaire

a * s ₁₁ * (s _12/8 ) ^b + a * s ₂₁ * (s _22/4 ) ^b + a * s ₃₁ * (s _32/4 ) ^b + a * s ₄₁ * (s _42/8 ) ^b + a * s ₅₁ * (s _52/8 ) ^b

où s ₁₁ et s ₁₂ sont des métriques au niveau du magasin pour le magasin 1 et ainsi de suite.

Les paramètres a et b sont des coefficients régressés à partir de données historiques, mais ce n'est qu'un bon point de départ et finira par évoluer vers une forme fonctionnelle plus complexe (peut-être des prédictions d'un algorithme ML)

Contraintes:

variant1 <= k ₁
variant2> = k ₁ et <= k ₂
(s _treize / 8) + (s _vingt-trois / 4) + (s ₃₃ /4) + (s ₄₃ /8) + (s ₅₃ /8) devrait se situent entre [(0,95 / k ₁ ) * (s ₁₃ + s ₂₃ + s ₃₃ + s ₄₃ + s ₅₃ ), (1,05 / k ₁ ) * (s ₁₃ + s ₂₃ + s ₃₃ + s ₄₃ + s ₅₃ ) ] (Écart de 5%)
où k ₁ , k ₂ , variant1 et variant2 sont des entiers

Answer 1

Étant donné ce qui semble être une contrainte non linéaire (la contrainte de déviation de 5%) et une fonction objective non linéaire (et apparemment arbitrairement complexe), je ne serais pas optimiste quant à la recherche d'une solution prouvée optimale. Si vous êtes prêt à vous contenter d'une «bonne» solution, il existe une variété de métaheuristiques qui pourraient être applicables. La recommandation d'un métaheuristique particulier dépendrait des spécificités des contraintes et des tendances religieuses de la personne faisant la recommandation.

Addendum: Sur la base des commentaires ci-dessous, j'ai essayé à la fois un algorithme génétique et une heuristique gourmande. L'heuristique gourmande a constamment surpassé l'AG (meilleure réponse en moins de temps). Codé en R et exécuter un PC avec des données constituées pour 1000 magasins (en utilisant$k_1=6$ et $k_2=12$), l'heuristique gourmande prenait généralement moins de 0,2 seconde. L'heuristique gloutonne parcourt toutes les valeurs possibles de variant1 et variant2. Pour chaque combinaison, il attribue initialement le moins cher des deux à tous les magasins, puis vérifie si la contrainte d'équilibre est respectée. Si ce n'est pas le cas, il parcourt les magasins dans une commande «plus rentable», faisant passer les magasins de la variante la moins chère à la plus chère, jusqu'à ce que l'équilibre soit (espérons-le) atteint. Bien sûr, des valeurs plus élevées de$k_1$ et $k_2$ entraînera plus de temps de traitement, mais je pense que c'est encore une voie très pratique à emprunter.