Teilung$N$Artikel hinein$K$gleichgroße Partitionen, während Gruppen in Originalelementen beibehalten werden
Angenommen, es gibt sie$N$Artikel die reinkommen$M$Gruppen. Lassen$c_i \in \{1, ..., M\}$zum$i=1, ..., N$repräsentieren die Gruppenmitgliedschaft für Artikel$i$. Ich würde gerne eine gröbere Aufteilung der Artikel finden$K$neue Gruppen, wo$K < M$, mit zwei Einschränkungen:
- Elemente in derselben Gruppe müssen derselben Partition zugewiesen werden, und
- Die neuen Gruppengrößen sollten möglichst gleich sein.
Mein erster Gedanke ist, dies als nichtlineares ganzzahliges Programm zu formulieren, wobei$y_{ij} = 1$wenn Artikel$i$ist der Partition zugeordnet$j$und ist ansonsten null. Dann hätte ich eine Reihe von Einschränkungen:
- $\sum_{j=1}^K y_{ij} = 1$zum$i=1,..., N$(jedes Item sollte genau einer Partition zugeordnet werden)
- $y_{ij} = y_{\ell j}$für alle$j=1, ..., K$wenn$c_i = c_\ell$(Elemente in derselben Gruppe müssen derselben Partition zugewiesen werden)
und dann konnte ich definieren$N_j = \sum_{i=1}^N y_{ij}$und minimieren
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
Dabei spielt das jeweilige Ziel aber eigentlich keine Rolle. So lange wie$N_j$ist nah dran$N/K$für alle$j$, Es ist mir egal, ob es in einem ist$\ell_2$oder$\ell_1$Sinn oder etwas anderes vage in diese Richtung.
Meine Fragen:
- Gibt es eine bessere Formulierung dieses Problems mit einer besonders einfachen Lösung?
- Welche Algorithmen lösen dieses Problem genau? Gibt es Möglichkeiten, schnell gierige Näherungslösungen zu erhalten?
- Ich nehme an, ich muss eine vorhandene Optimierungssoftware nutzen, um meine Lösung zu erhalten. Gibt es hier Standardoptionen für einen Python/Julia/R-Benutzer? (Codebeispiele sind sehr willkommen!)
Einige zusätzliche Hintergrundinformationen: Ich suche im Wesentlichen nach einem (rechentechnisch) effizienteren Ansatz für die Kreuzvalidierung von Auslassungsgruppen. Der aktuelle Standard besteht darin, jeweils eine einzelne Gruppe auszulassen, damit Sie passen$M$Modelle, wo$M$kann ziemlich hoch sein. In der Praxis so etwas wie$K=5$oder$K=10$ist für statistische Zwecke ausreichend, und die Kreuzvalidierung wird die Eigenschaften haben, die wir wollen, solange alle in derselben Gruppe in dieselbe Falte gehen und die Faltungen ungefähr gleich groß sind. Also passend$M >> 10$Modelle, wenn es viele Gruppen gibt, ist oft ineffizient und unnötig.
Antworten
Ein Ansatz besteht darin, sich die Gruppen als Jobs vorzustellen, wobei die Dauer jedes Jobs gleich der Anzahl der Elemente in seiner Gruppe ist. Planen Sie diese Jobs jetzt ein$K$identische Maschinen, wodurch die Fertigungsspanne minimiert, dh minimiert wird$\max_j N_j$. Die LPT-Heuristik ist schnell und liefert a$(2-1/K)$-Annäherung.
Erste Frage: Im IP-Modell braucht man nicht für jede Kombination aus Item und Partition eine binäre Variable. Angesichts Ihrer Anforderung, dass Gruppen zusammengehalten werden müssen, benötigen Sie nur eine Binärdatei für jede Kombination aus Gruppe und Partition. Dein$y_{ij}=y_{\ell j}$Constraints lassen die Presolve-Funktion des Solvers das Modell auf diese Größe schrumpfen, aber Sie können auch einfach mit der kleineren Formulierung beginnen. Anstatt das Problem quadratisch zu machen, würde ich wahrscheinlich den linearen Unterschied zwischen der kleinsten und größten Partitionsgröße minimieren. Dies führt nicht unbedingt zu einem „besonders einfach“ zu lösenden Modell, aber abhängig von Ihren Problemdimensionen und Ihrem IP-Löser (und Ihrer Geduld) kann es einfach genug sein.
Zweite Frage: Mit dem IP-Modell und einem IP-Solver können Sie das Problem exakt lösen. Eine schnelle Heuristik, die einigermaßen gut abschneiden könnte, ist für den Anfang$K$leere Partitionen, sortieren Sie die Gruppen nach absteigender Größe und weisen Sie dann jede Gruppe der aktuell kleinsten Partition zu.
Dritte Frage: Ich kann nicht für Julia oder Python sprechen (obwohl ich einige IP-Löser für Python kenne), aber mit RI würde ich dazu neigen, das OMPR-Paket (eine DSL für LP/IP) zum Schreiben des Modells zu verwenden. OMPR stützt sich wiederum auf ROI, um das Modell zu lösen, und sowohl OMPR als auch ROI erfordern, dass Sie ein Solver-spezifisches Plug-In laden (und natürlich den entsprechenden Solver installiert haben).
Ich habe ein R-Notebook mit OMPR und ROI mit ihren jeweiligen CPLEX-Plug-ins gehackt. Auf einem zufälligen Testproblem mit$N=5700$,$M=130$und$K=10$, die von mir beschriebene Heuristik hat typischerweise eine Verteilung der Partitionsgröße von 5 (Größen reichen von 567 bis 572), und das IP-Modell hat zehn Partitionen mit jeweils 570 (Spreizung = 0). Die Heuristik dauerte einen (kleinen) Bruchteil einer Sekunde. Das Erstellen des IP-Modells und das Lösen mit CPLEX dauerte etwa neun Sekunden.
Wie immer wird Ihre Laufleistung variieren.
NACHTRAG: Ich habe (zu Recht) vermutet, dass die Verwendung runder Zahlen für die Problemdimensionen die Dinge schöner machen könnte, also habe ich es versucht$N=5723$,$M=137$und$K=10$(was sicherstellt, dass keine Lösung alle Partitionsgrößen identisch hat). Die IP-Lösung verwaltete einen Spread von 1 (einige Partitionen hatten 572 Elemente, andere 573, was immer noch besser ist, als ich für allgemein erreichbar halte). Die heuristische Lösung hatte eine Streuung von 30 (Partitionsgrößen von 552 bis 582).
NACHTRAG 2: Ich habe eine paarweise Austauschheuristik nach dem hinzugefügt, was Rob die LPT-Heuristik nennt. Im Beispiel mit$N=5723$usw. reduzierte die Pairwise-Swap-Heuristik den Spread von 30 auf 2, nicht ganz optimal (optimal ist 1), aber viel näher. Wie bei LPT dauerte die Swapping-Heuristik bei diesem Beispiel weit unter einer Sekunde.