Was ist die richtige Formulierung für dieses Optimierungsproblem „Einkaufstasche“ und wie kann ich es effizient lösen?

8

Ich suche nach einer Lösung für das folgende Problem, habe aber Probleme, es sinnvoll zu formulieren und dann einen geeigneten Algorithmus zu finden, um es zu lösen.

Betrachten Sie eine Liste der Artikel in einer Einkaufstasche: 1, 2, 3, 4 ...

Jeder Artikel kann Teil einer oder mehrerer Werbeaktionen sein: A, B, C, D.

Wir möchten die Werbeaktionen so anwenden, dass wir den Wert des Rabatts maximieren, dass kein Artikel an mehr als einer Aktion teilnehmen darf, aber jede Aktion mehr als einmal angewendet werden kann.

Werbeaktionen können auf verschiedene Arten definiert werden, aber im Moment denke ich nur über eine Art von "2 qualifizierende Gegenstände kaufen, X speichern" nach. Ich hoffe, dass ich von hier aus verallgemeinern kann.

Mein Beispiel wäre:

  • Aktion A - Kaufen Sie 2 Sparen Sie 8
  • Promotion B - Kaufen Sie 2 Sparen Sie 10

  • Promotion C - Kaufen Sie 2 Sparen Sie 6

  • Punkt 1 - Berechtigt für A, B.

  • Punkt 2 - Berechtigt für B.
  • Punkt 3 - Berechtigt für A, C.
  • Punkt 4 - Berechtigt für B, C.

Hier ist leicht zu erkennen, dass die korrekte Anwendung von Werbeaktionen A bis Punkt 1, 3 und B bis 2, 4 ist. Dies ergibt einen Gesamtrabatt von 18.

In einem größeren Fall wird es schwierig, daher muss es algorithmisch gelöst werden.

Ich habe folgendes versucht:

  1. Listen Sie alle möglichen Kombinationen von Werbeaktionen auf, die wir anwenden könnten.
  2. Verwerfen Sie alle offensichtlich schlechten (z. B. eine direkte Kopie einer Aktion mit einem höheren Wert).
  3. Wenden Sie alle Aktionen an, die sich nicht mit anderen Werbeaktionen überschneiden (z. B. wenn Artikel 1 und 2 nur für Aktion A gültig sind, wenden Sie diese Aktion an).
  4. Nehmen Sie den verbleibenden Satz und versuchen Sie eine Suche nach verzweigten und gebundenen Typen für die Ergebnisse.

Dies kann jedoch lange dauern (bei großen Sets mit ähnlichen Rabatten).

Ich denke, dies ist eine Art Rucksack- oder Zuweisungsproblem, aber ich kann es nicht vernünftig schreiben. Ohne es vernünftig schreiben zu können, kann ich es nicht lösen.

Ist dies eine anerkannte Variante eines Problems? Jede Hilfe, die es angreift, wäre sehr dankbar, insbesondere mit Pseudo-Code, um es zu lösen

optimization algorithms James Osborn
quelle
2
Die Daten können als zweigeteilter Graph ausgedrückt werden. Wenn jede Aktion höchstens einmal angewendet werden könnte, wäre dies ein zweigliedriges Diagrammanpassungsproblem mit maximalem Gewicht, das sehr gut verstanden wird. Was Sie also wollen, denke ich, ist eine entspannte Form dieses Problems. Dies könnte Ihnen helfen, etwas in der Literatur zu finden.
Pseudonym
Wenn wir also vorerst davon ausgehen, dass jede Aktion nur einmal angewendet werden kann, wie würden Sie das Diagramm erstellen? Ich habe verschiedene Möglichkeiten ausprobiert, kann aber nicht sehen, wie Sie die Einschränkung beibehalten, dass eine Aktion nur angewendet werden kann, wenn sie als gültig angesehen wird.
James Osborn
Sie können dieses Problem als 0-1 Integer-Programm erstellen und dann entweder einen Open Source- oder einen kommerziellen Solver verwenden, um die größeren Versionen davon zu lösen.
Aron Ahmadia
1
@ James Osborn: Betrachten Sie ein zweiteiliges Diagramm, in dem zwischen jeder Aktion und jedem Artikel ein Vorteil besteht. Wenn es gültig ist, diese Aktion auf diesen Gegenstand anzuwenden, ist das Gewicht am Rand der "Gewinn". Andernfalls ist das Gewicht an der Kante Null. Dann finden Sie eine maximale Gewichtsübereinstimmung und verwerfen alle Kanten mit dem Gewicht Null. Grundsätzlich lassen Sie die Übereinstimmung geschehen, machen dem Optimierungsalgorithmus jedoch klar, dass Sie dadurch nichts gewinnen.
Pseudonym
Nur ein kurzes Update, danke für die bisherige Hilfe. Ich hatte noch keine große Chance, mir die Lösungen anzuschauen, aber es hat mir einige gute Orte gegeben, an denen ich nachsehen kann.
James Osborn

Antworten:

1

Es scheint, als würden Sie die Struktur des Problems nutzen wollen, dass Gegenstände nur für eine Aktion verwendet werden können. Das heißt, wenn Sie eine Lösung gefunden haben, die so viele Werbeaktionen wie möglich verwendet, besteht die einzige Möglichkeit, dies zu verbessern, darin, eine andere Lösung zu finden, die eine oder mehrere Werbeaktionen sowie die nicht zugewiesenen Artikel verwendet und diese gegen einen anderen Satz von Werbeaktionen und nicht verwendeten Artikeln austauscht von höherem Wert.

Zum Beispiel könnten Sie das vorherige Beispiel mit (1,2) und (3,4) für 16 beginnen. Sie könnten dann überprüfen, ob (1,3) und (2,4) zu 18 führen, und der Swap sollte sein gemacht.

aeismail
quelle