Kombinatorische Optimierung, Zuordnungsproblem

Question

Ich versuche, ein Problem (in pyspark / python) zu lösen, bei dem ich zwei unterschiedliche Werte zum Zuweisen finden muss und wie ich sie in einem Netzwerk von Geschäften zuweisen kann.

Die zwei unterschiedlichen Werte können nur ganzzahlige Werte sein und innerhalb einer Unter- und Obergrenze eingeschränkt sein. Für jedes dieser unterschiedlichen Wertepaare, beispielsweise 4 und 8, kann jedes Geschäft entweder 4 oder 8 erhalten, was insgesamt 2 ⁿ verschiedene Zuordnungsarten ergibt, wenn es n Geschäfte gibt ( n liegt nahe bei 1000).

Die Zielfunktion ist komplex und verwendet Vorhersagemodelle, um die Auswirkung eines bestimmten Wertepaars entsprechend seiner Zuordnung im Netzwerk zu ermitteln.

Ich hatte gehofft, eine Kostenfunktion des Formulars erstellen zu können:

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

wo

• variant1 = 4 (Ganzzahl, beschränkt auf einen Maximalwert)
• variant2 = 8 (Ganzzahl, beschränkt auf einen Maximalwert)
• store_1_variant, ..., store_n_variantsind binär [0,1], um anzugeben, ob sie empfangen variant_1oder nicht (nicht empfangen variant1würde empfangen variant2)

Ich könnte nach den n + 2 Parametern suchen, die die Kosten minimieren (es gibt eine weitere Einschränkung, die die Auswirkungen einer bestimmten Zuordnung kontrollieren muss).

Ich habe mir verschiedene kombinatorische Optimierungstechniken angesehen, aber keine, die mir eine benutzerdefinierte Funktion als Kostenfunktion zu ermöglichen scheinen.

Ich habe keine Vorkenntnisse in diesem Bereich, daher wird jede Anleitung / Unterstützung geschätzt.

Bearbeiten

Um einige Informationen über die aktuelle Form der Kostenfunktion hinzuzufügen, werden mit dem Beispiel von zwei Varianten, 4 und 8 mit beispielsweise 5 Filialen, f(4, 8, 0, 1, 1, 0, 0)Kosten des Formulars verbunden

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

Dabei sind s ₁₁ und s ₁₂ Metriken auf Speicherebene für Speicher 1 und so weiter.

Die Parameter a und b sind regressive Koeffizienten aus historischen Daten, aber dies ist nur ein guter Ausgangspunkt und wird sich schließlich zu einer komplexeren funktionalen Form entwickeln (möglicherweise Vorhersagen eines ML-Algorithmus).

Einschränkungen:

Variante1 <= k ₁
Variante 2 > = k ₁ und <= k ₂
(s ₁₃ /8) + (S ₂₃ /4) + (n ₃₃ /4) + (n ₄₃ /8) + (S ₅₃ /8) sollen liegen zwischen [(0,95 / k ₁ ) * (s ₁₃ + s ₂₃ + s ₃₃ + s ₄₃ + s ₅₃ ), (1,05 / k ₁ ) * (s ₁₃ + s ₂₃ + s ₃₃ + s ₄₃ + s ₅₃ ) ] (5% Abweichung)
wobei k ₁ , k ₂ , Variante 1 und Variante ₂ ganze Zahlen sind

Answer 1

Angesichts einer scheinbar nichtlinearen Einschränkung (5% Abweichungsbedingung) und einer nichtlinearen (und scheinbar willkürlich komplexen) Zielfunktion wäre ich nicht optimistisch, eine nachweislich optimale Lösung zu finden. Wenn Sie bereit sind, sich mit einer "guten" Lösung zufrieden zu geben, gibt es eine Vielzahl von Metaheuristiken, die möglicherweise anwendbar sind. Die Empfehlung einer bestimmten Metaheuristik würde von den Besonderheiten der Einschränkungen und den religiösen Tendenzen der Person abhängen, die die Empfehlung abgibt.

Nachtrag: Basierend auf den Kommentaren unten habe ich sowohl einen genetischen Algorithmus als auch eine gierige Heuristik ausprobiert. Die gierige Heuristik übertraf die GA durchweg (bessere Antwort in weniger Zeit). In R codiert und einen PC mit zusammengestellten Daten für 1.000 Geschäfte ausführen (mit$k_1=6$ und $k_2=12$) dauerte die gierige Heuristik typischerweise weniger als 0,2 Sekunden. Die gierige Heuristik durchläuft alle möglichen Werte von Variante1 und Variante2. Für jede Kombination wird zunächst allen Filialen die billigere der beiden zugeordnet, und dann wird geprüft, ob die Kontostandbeschränkung erfüllt ist. Wenn nicht, durchläuft es die Geschäfte in einer "größten Knall-für-das-Geld" -Bestellung und wechselt die Geschäfte von der billigeren Variante zur teureren, bis das Gleichgewicht (hoffentlich) erreicht ist. Natürlich größere Werte von$k_1$ und $k_2$ wird zu mehr Bearbeitungszeit führen, aber ich denke, dies ist immer noch ein sehr praktischer Weg.