0-1 Rucksackproblem mit Artikelrabatten

Ich bin kürzlich auf diese Art von Problem in einer realen Umgebung gestoßen und konnte für mich keine Literatur finden, die sich auf die Problemstellung bezieht, die ich mir ausgedacht habe. Ein Beispiel wird unten aufgeführt.

Einfache Erklärung des Problems

Angenommen, Sie haben Werte und Gewichte für Elemente, z. B. Gruppen von $2$ und $3$Die Anzahl der Artikel in Ihrem Set kann zu Werten führen, die niedriger sind als bei einer individuellen Auswahl (denken Sie an 50% Rabatt auf Gutscheine oder ähnliches). In diesem Sinne möchten wir die beste Kombination von Gegenständen finden, die es uns ermöglicht, angesichts einer Wertbeschränkung das größte Gewicht in unserem Rucksack zu tragen. Wie können wir die dynamische Programmiermethode ändern, um eine neue Lösung zu finden? Ist ein metaheuristischer Ansatz der beste Weg? Ist dieses Problem bereits gut untersucht?

Nachstehend wird nach bestem Wissen und Gewissen eine mathematische Aussage getroffen.

Lassen $V_1 = \{v_1, v_2, ..., v_N\}$ seien die Werte der einzelnen Elemente, $V_2 = \{ r_{(1,2)}, v_{(1,3)}, ... \}$ als Satz von Größe $M$ der Werte der Gruppen von zwei Elementen und $V_3 = \{s_{(1,2,3)}, s_{(1,2,4)} ... \}$ als Satz von Größe sein $L$ der Werte der Gruppen von drei Elementen zusammen mit entsprechenden Gewichten (mit ähnlicher Notation für Elemente) $W_1, W_2, W_3$.

Wir suchen zu finden $\textbf{x} = (x_i, x_{i,j}, x_{i,j,k})$ wo $x_i, x_{i,j}, x_{i,j,k} = \{0,1\}$ das ist ein Vektor der Länge $N + M + L$ damit

$$max\left(\sum_{w \in W_1} wx_i + \sum_{w \in W_2} wx_{i,j} + \sum_{w \in W_3}wx_{i,j,k} \right)$$ vorbehaltlich $$\sum_{v \in V_1} vx_i + \sum_{v \in V_2} vx_{i,j} + \sum_{v \in V_3}vx_{i,j,k} \leq C$$

Wo $C$ist die Wertebeschränkung. Hier der Index$(i,j)$ und $(i,j,k)$entsprechen einfach den Indizes der entsprechenden Artikel. Dies bedeutet auch, dass ein Element in einer Gruppe von ausgewählt wurde$2$ oder $3$ kann nicht mehr an anderer Stelle gewählt werden, daher stellen wir die folgenden Bedingungen:

Wenn $x_{i,j,k} = 1$ dann $x_i = 0$, $x_j = 0$, $x_k = 0$, $x_{i,j} = 0$, $x_{i,k} = 0$, und $x_{j,k} = 0$.

Wenn $x_{i,j} = 1$ dann $x_i = 0$, $x_k = 0$und jedes Triplett, das einen Gegenstand mit Index enthält $i$ und $j$ ist Null.

Wenn $x_i = 1$, dann jede Gruppe, die ein Element mit Index enthält $i$ ist Null.

Einige Diskussionen

Ein Element in dem obigen Problem kann nur in einer Zweiergruppe abgezinst werden. Es kann jedoch auch Dreiergruppen geben, die eine Überlappung zwischen zwei Zweiergruppen erzeugen, weshalb diese eingeschlossen werden müssen. Dies bedeutet, dass ein offensichtlicher gieriger Algorithmus erscheint, indem die größten Gewichte pro Wert von Drillingen geordnet werden, dort die Form ausgewählt und zu Doppel und dann zu Einzel übergegangen wird, bis dies nicht möglich ist.

Ich möchte glauben, dass eine Änderung des dynamischen Programmieralgorithmus möglich ist, indem einfach weitere Zeilen hinzugefügt werden, die die Elementgruppen darstellen. Ich bin mir jedoch nicht sicher, wie wir mit der Option "Diese Gruppe wurde ausgewählt, daher müssen alle Teilmengen in der Gruppe umgehen" umgehen nicht gewählt werden. " Bedingung. In meinem realen Problem gab es 150 Elemente, was den Anschein erweckt, dass die dynamische Programmiermethode nicht möglich war (es gab viele mögliche Gruppen von 2 und 3, wenn man bedenkt, wie groß 150 sind, wählen Sie 3 ..). Tatsächlich wäre die Anzahl der Zeilen für meinen Fall auf den ersten Blick$150$ $+$ ${150}\choose{2} $ + ${150}\choose{3}$ $= 562,625$Reihen! Wenn Sie dies mit den Spalten kombinieren, die die Werte darstellen, die viele sein können, muss möglicherweise eine Option mit geringer Matrix verwendet werden, um die Suche nach einer Lösung zu optimieren.

Ein kurzes Beispiel

Lassen $4$ Elemente haben Werte $v_1 = 4$, $v_2 = 7$, $v_3 = 3$, und $v_4 = 9$ So dass die Werte der folgenden Gruppen Rabatte haben: $(v_1, v_2) = 8$, $(v_2, v_4) = 14$, und $(v_1, v_2, v_4) = 15$. Es ist erwähnenswert, dass Artikelkombinationen, die nicht mit einem Rabatt aufgeführt sind, einfach die Summe ihrer Werte sind und nicht ausgeschrieben werden müssen. Nehmen wir weiter an$C = 17$.

Ihre Gewichte sind $w_1 = 2$, $w_2 = 5$, $w_3 = 5$, und $w_4 = 3$. Dann wollen wir finden$\bf{x}$ damit

$$max(2x_1 + 5x_2 + 5x_3 + 3x_4 + 7x_{(1,2)} + 8x_{(2,4)} + 10x_{(1,2,4)})$$ vorbehaltlich $$4x_1 + 7x_2 + 3x_3 + 9x_4 + 8x_{(1,2)} + 14x_{(2,4)} + 15x_{(1,2,4)} \leq 17$$

Wenn ein ausgewähltes Element in der Gruppe eines anderen Elements enthalten ist, ist dies der Fall $x$Der Wert muss Null sein, um Überlappungen zu vermeiden. Es scheint mir, dass die Elemente mit Indizes$\{(1,2), 3 \}$ ist die Lösung mit Gewicht 12 mit Wert 11.