Partisi $N$ item ke $K$ partisi berukuran sama sambil mempertahankan grup dalam item asli
Misalkan ada $N$ barang yang masuk $M$kelompok. Membiarkan$c_i \in \{1, ..., M\}$ untuk $i=1, ..., N$ mewakili keanggotaan grup untuk item $i$. Saya ingin mencari partisi item yang lebih kasar$K$ kelompok baru, dimana $K < M$, dengan dua batasan:
- item dalam grup yang sama harus ditetapkan ke partisi yang sama, dan
- ukuran grup baru harus sedekat mungkin.
Pikiran awal saya adalah merumuskan ini sebagai program integer non-linier, di mana $y_{ij} = 1$ jika barang $i$ ditugaskan ke partisi $j$dan nol sebaliknya. Maka saya akan memiliki serangkaian kendala:
- $\sum_{j=1}^K y_{ij} = 1$ untuk $i=1,..., N$ (setiap item harus ditetapkan ke satu partisi)
- $y_{ij} = y_{\ell j}$ untuk semua $j=1, ..., K$ jika $c_i = c_\ell$ (item dalam grup yang sama harus ditetapkan ke partisi yang sama)
dan kemudian saya bisa mendefinisikan $N_j = \sum_{i=1}^N y_{ij}$ dan meminimalkan
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
Namun, tujuan tertentu sebenarnya tidak penting di sini. Sepanjang$N_j$ dekat dengan $N/K$ untuk semua $j$, Saya tidak peduli jika itu dalam $\ell_2$ atau $\ell_1$ rasa atau sesuatu yang samar-samar di sepanjang garis itu.
Pertanyaan saya:
- Apakah ada rumusan yang lebih baik untuk masalah ini dengan solusi yang sangat mudah?
- Algoritma apa yang akan menyelesaikan masalah ini dengan tepat? Apakah ada cara untuk mendapatkan solusi perkiraan serakah yang cepat?
- Saya kira saya perlu memanfaatkan beberapa perangkat lunak pengoptimalan yang ada untuk mendapatkan solusi saya. Apakah ada pilihan standar di sini untuk pengguna Python / Julia / R? (Contoh kode sangat dihargai!)
Beberapa latar belakang tambahan: Saya pada dasarnya mencari pendekatan yang lebih efisien (secara komputasi) untuk validasi silang tanpa grup. Standar saat ini adalah meninggalkan satu grup pada satu waktu, sehingga Anda cocok$M$ model, di mana $M$bisa sangat tinggi. Dalam praktiknya, seperti$K=5$ atau $K=10$cukup untuk tujuan statistik, dan validasi silang akan memiliki properti yang kita inginkan selama semua orang dalam grup yang sama masuk ke lipatan yang sama dan lipatan berukuran sama. Sangat pas$M >> 10$ model ketika ada banyak kelompok seringkali tidak efisien dan tidak perlu.
Jawaban
Salah satu pendekatannya adalah dengan menganggap kelompok sebagai pekerjaan, dengan durasi setiap pekerjaan sama dengan jumlah item dalam kelompoknya. Sekarang jadwalkan pekerjaan ini$K$ mesin identik, meminimalkan makespan, yaitu meminimalkan $\max_j N_j$. Heuristik LPT cepat dan menghasilkan a$(2-1/K)$-perkiraan.
Pertanyaan pertama: Dalam model IP, Anda tidak memerlukan variabel biner untuk setiap kombinasi item dan partisi. Mengingat persyaratan Anda bahwa grup harus disimpan bersama, Anda hanya memerlukan biner untuk setiap kombinasi grup dan partisi. Anda$y_{ij}=y_{\ell j}$batasan akan membiarkan fungsi presolve solver mengecilkan model ke ukuran ini, tetapi Anda sebaiknya mulai dengan formulasi yang lebih kecil. Selain itu, daripada membuat masalah menjadi kuadrat, saya mungkin akan meminimalkan perbedaan antara ukuran partisi terkecil dan terbesar, yang linear. Ini tidak selalu menghasilkan model yang "sangat mudah" untuk dipecahkan, tetapi tergantung pada dimensi masalah Anda dan pemecah IP Anda (dan kesabaran Anda), ini mungkin cukup mudah.
Pertanyaan kedua: Anda dapat menyelesaikan masalah dengan tepat menggunakan model IP dan pemecah IP. Heuristik cepat yang mungkin berhasil dengan baik adalah untuk memulai$K$ kosongkan partisi, urutkan grup ke dalam urutan ukuran menurun, lalu tetapkan setiap grup ke partisi terkecil saat ini.
Pertanyaan ketiga: Saya tidak dapat berbicara untuk Julia atau Python (walaupun saya tahu tentang beberapa pemecah IP untuk Python), tetapi dengan RI akan cenderung menggunakan paket OMPR (DSL untuk LP / IP) untuk menulis model. OMPR pada gilirannya akan mengandalkan ROI untuk menyelesaikan model, dan baik OMPR maupun ROI akan meminta Anda untuk memuat plug-in khusus solver (dan, tentu saja, menginstal solver yang sesuai).
Saya meretas notebook R menggunakan OMPR dan ROI dengan plug-in CPLEX masing-masing. Pada soal uji acak dengan$N=5700$, $M=130$ dan $K=10$, heuristik yang saya jelaskan biasanya mendapat penyebaran ukuran partisi 5 (ukuran mulai dari 567 hingga 572), dan model IP mendapat sepuluh partisi masing-masing 570 (spread = 0). Heuristik membutuhkan waktu (kecil) sepersekian detik. Membangun model IP dan menyelesaikannya dengan CPLEX membutuhkan waktu sekitar sembilan detik.
Seperti biasa, jarak tempuh Anda akan bervariasi.
TAMBAHAN: Saya menduga (dengan benar) bahwa menggunakan angka bulat untuk dimensi masalah mungkin membuat segalanya lebih baik, jadi saya mencoba $N=5723$, $M=137$ dan $K=10$(yang memastikan bahwa tidak ada solusi yang semua ukuran partisi sama). Solusi IP mengelola penyebaran 1 (beberapa partisi memiliki 572 item, beberapa memiliki 573, yang masih lebih baik daripada yang saya kira secara umum dapat dicapai). Solusi heuristik memiliki penyebaran 30 (ukuran partisi mulai dari 552 hingga 582).
TAMBAHAN 2: Saya menambahkan heuristik pertukaran berpasangan setelah apa yang disebut Rob sebagai heuristik LPT. Dalam contoh dengan$N=5723$dll., heuristik swap berpasangan mengurangi penyebaran dari 30 menjadi 2, tidak cukup optimal (optimal menjadi 1) tetapi lebih dekat. Seperti LPT, heuristik swapping memakan waktu kurang dari satu detik pada contoh ini.