Przegroda $N$ elementy do $K$ partycje o jednakowych rozmiarach, zachowując grupy w oryginalnych elementach

Question

Przypuśćmy, że są $N$ elementy, które wchodzą $M$grupy. Pozwolić$c_i \in \{1, ..., M\}$ dla $i=1, ..., N$ reprezentują członkostwo w grupie dla elementu $i$. Chciałbym znaleźć bardziej zgrubny podział elementów na$K$ nowe grupy, gdzie $K < M$, z dwoma ograniczeniami:

1. elementy z tej samej grupy muszą być przypisane do tej samej partycji, a
2. nowe rozmiary grup powinny być jak najbardziej zbliżone do równych.

Moją początkową myślą jest sformułowanie tego jako nieliniowego programu liczb całkowitych, gdzie $y_{ij} = 1$ jeśli pozycja $i$ jest przypisany do partycji $j$aw innym przypadku wynosi zero. Wtedy miałbym zestaw ograniczeń:

1. $\sum_{j=1}^K y_{ij} = 1$ dla $i=1,..., N$ (każda pozycja powinna być przypisana dokładnie do jednej partycji)
2. $y_{ij} = y_{\ell j}$ dla wszystkich $j=1, ..., K$ Jeśli $c_i = c_\ell$ (elementy z tej samej grupy muszą być przypisane do tej samej partycji)

a potem mógłbym zdefiniować $N_j = \sum_{i=1}^N y_{ij}$ i zminimalizuj

$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$

Jednak konkretny cel nie ma tutaj znaczenia. Tak długo aż$N_j$ jest blisko $N/K$ dla wszystkich $j$, Nie obchodzi mnie, czy jest w $\ell_2$ lub $\ell_1$ sens lub coś innego niejasno w tym kierunku.

Moje pytania:

1. Czy istnieje lepsze sformułowanie tego problemu ze szczególnie łatwym rozwiązaniem?
2. Jakie algorytmy dokładnie rozwiążą ten problem? Czy są sposoby na szybkie, chciwe przybliżone rozwiązania?
3. Zakładam, że będę musiał wykorzystać istniejące oprogramowanie optymalizacyjne, aby uzyskać moje rozwiązanie. Czy są tutaj jakieś standardowe opcje dla użytkownika Python / Julia / R? (Bardzo cenne próbki kodu!)

Dodatkowe informacje: zasadniczo szukam bardziej wydajnego (obliczeniowo) podejścia do weryfikacji krzyżowej pomijania grupowania. Obecny standard to pomijanie pojedynczej grupy na raz, tak abyś pasował$M$ modele, gdzie $M$może być dość wysoki. W praktyce coś w stylu$K=5$ lub $K=10$jest wystarczająca do celów statystycznych, a walidacja krzyżowa będzie miała właściwości, których chcemy, o ile wszyscy w tej samej grupie wchodzą do tej samej fałdy, a fałdy są mniej więcej tej samej wielkości. Tak pasuje$M >> 10$ modele w przypadku wielu grup są często nieefektywne i niepotrzebne.

Answer 1

Jednym podejściem jest myślenie o grupach jako o zadaniach, przy czym czas trwania każdej pracy jest równy liczbie elementów w jej grupie. Teraz zaplanuj te zadania$K$ identyczne maszyny, minimalizując czas produkcji, czyli minimalizując $\max_j N_j$. Heurystyka LPT jest szybka i daje plik$(2-1/K)$-przybliżenie.

Answer 2

Pierwsze pytanie: w modelu IP nie potrzebujesz zmiennej binarnej dla każdej kombinacji elementu i partycji. Biorąc pod uwagę Twoje wymaganie, aby grupy były razem, potrzebujesz tylko pliku binarnego dla każdej kombinacji grupy i partycji. Twój$y_{ij}=y_{\ell j}$ograniczenia pozwolą funkcji presolve solwera na zmniejszenie modelu do tego rozmiaru, ale równie dobrze możesz zacząć od mniejszego wzoru. Ponadto, zamiast uczynić problem kwadratowym, prawdopodobnie zminimalizowałbym różnicę między najmniejszym a największym rozmiarem partycji, która jest liniowa. Niekoniecznie tworzy to „szczególnie łatwy” do rozwiązania model, ale w zależności od wymiarów problemu i twojego rozwiązania do rozwiązywania problemów IP (i twojej cierpliwości), może to być wystarczająco łatwe.

Drugie pytanie: możesz rozwiązać problem dokładnie za pomocą modelu IP i narzędzia do rozwiązywania problemów. Szybką heurystyką, która może zadziałać całkiem dobrze, jest na początek$K$ puste partycje, posortuj grupy w kolejności malejącej, a następnie przypisz każdą grupę do aktualnie najmniejszej partycji.

Trzecie pytanie: nie mogę mówić w imieniu Julii lub Pythona (chociaż znam kilka solwerów IP dla Pythona), ale z RI byłbym skłonny użyć pakietu OMPR (DSL dla LP / IP) do napisania modelu. OMPR będzie z kolei polegał na ROI przy rozwiązywaniu modelu, a zarówno OMPR, jak i ROI będą wymagały załadowania wtyczki specyficznej dla solwera (i oczywiście zainstalowania odpowiedniego solwera).

Włamałem się do notebooka R przy użyciu OMPR i ROI z ich odpowiednimi wtyczkami CPLEX. Na losowym problemie z$N=5700$, $M=130$ i $K=10$, heurystyka, którą opisałem, zazwyczaj miała rozkład rozmiaru partycji wynoszący 5 (rozmiary od 567 do 572), a model IP miał dziesięć partycji po 570 każda (rozpiętość = 0). Heurystyka zajęła (mały) ułamek sekundy. Zbudowanie modelu IP i rozwiązanie go za pomocą CPLEX zajęło około dziewięciu sekund.

Jak zawsze, Twój przebieg będzie się różnić.

DODATEK: Podejrzewałem (poprawnie), że użycie okrągłych liczb do wymiarów problemu może poprawiać sytuację, więc spróbowałem $N=5723$, $M=137$ i $K=10$(co zapewnia, że ​​żadne rozwiązanie nie ma identycznych rozmiarów wszystkich partycji). Rozwiązanie IP poradziło sobie z rozprzestrzenianiem się 1 (niektóre partycje miały 572 elementy, inne 573, co jest nadal lepsze niż myślę, że jest ogólnie osiągalne). Rozpiętość rozwiązania heurystycznego wynosiła 30 (rozmiary partycji od 552 do 582).

DODATEK 2: Dodałem heurystykę wymiany parami po tym, co Rob nazywa heurystyką LPT. W przykładzie z$N=5723$itd., heurystyka zamiany parami zmniejszyła spread z 30 do 2, nie całkiem optymalnie (optymalnie 1), ale znacznie bliżej. Podobnie jak w przypadku LPT, heurystyka zamiany zajęła w tym przykładzie mniej niż jedną sekundę.