Bölüm $N$ içine öğeler $K$ orijinal öğelerdeki grupları korurken eşit boyutta bölümler
Varsayalım ki $N$ gelen öğeler $M$gruplar. İzin Vermek$c_i \in \{1, ..., M\}$ için $i=1, ..., N$ öğe için grup üyeliğini temsil eder $i$. Öğelerin daha kaba bir bölümünü bulmak istiyorum$K$ yeni gruplar, nerede $K < M$, iki kısıtlama ile:
- aynı gruptaki öğeler aynı bölüme atanmalıdır ve
- yeni grup boyutları olabildiğince yakın olmalıdır.
İlk düşüncem, bunu doğrusal olmayan bir tamsayı programı olarak formüle etmektir. $y_{ij} = 1$ eğer öğe $i$ bölüme atandı $j$ve aksi takdirde sıfırdır. O zaman bir dizi kısıtlamam olur:
- $\sum_{j=1}^K y_{ij} = 1$ için $i=1,..., N$ (her öğe tam olarak bir bölüme atanmalıdır)
- $y_{ij} = y_{\ell j}$ hepsi için $j=1, ..., K$ Eğer $c_i = c_\ell$ (aynı gruptaki öğeler aynı bölüme atanmalıdır)
ve sonra tanımlayabilirim $N_j = \sum_{i=1}^N y_{ij}$ ve küçült
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
Bununla birlikte, özel hedef aslında burada önemli değil. Olduğu sürece$N_j$ yakındır $N/K$ hepsi için $j$İçinde olması umrumda değil $\ell_2$ veya $\ell_1$ algı veya bu çizgiler boyunca belli belirsiz başka bir şey.
Sorularım:
- Bu problemin özellikle kolay bir çözüme sahip daha iyi bir formülasyonu var mı?
- Bu sorunu tam olarak hangi algoritmalar çözecek? Hızlı açgözlü yaklaşık çözümler elde etmenin yolları var mı?
- Çözümümü elde etmek için bazı mevcut optimizasyon yazılımlarından yararlanmam gerekeceğini varsayıyorum. Burada bir Python / Julia / R kullanıcısı için standart seçenekler var mı? (Kod örnekleri çok beğenildi!)
Bazı ek bilgiler: Esasen grup dışı çapraz doğrulamayı bırakmak için daha (hesaplama açısından) verimli bir yaklaşım arıyorum. Mevcut standart, uymanız için her seferinde tek bir grubu dışarıda bırakmaktır.$M$ modeller, nerede $M$oldukça yüksek olabilir. Pratikte şöyle bir şey$K=5$ veya $K=10$istatistiksel amaç için yeterlidir ve çapraz doğrulama, aynı gruptaki herkes aynı kıvrıma girdiği ve kıvrımlar yaklaşık aynı büyüklükte olduğu sürece istediğimiz özelliklere sahip olacaktır. Çok uygun$M >> 10$ çok sayıda grup olduğunda modeller genellikle verimsiz ve gereksizdir.
Yanıtlar
Bir yaklaşım, grupları her işin süresi grubundaki öğelerin sayısına eşit olacak şekilde işler olarak düşünmektir. Şimdi bu işleri planlayın$K$ aynı makineler, üretim süresini en aza indirir, yani en aza indirir $\max_j N_j$. LPT buluşsal yöntemi hızlıdır ve bir$(2-1/K)$-yaklaşıklık.
İlk soru: IP modelinde, her öğe ve bölüm kombinasyonu için bir ikili değişkene ihtiyacınız yoktur. Grupların bir arada tutulması gereksiniminiz göz önüne alındığında, her grup ve bölüm kombinasyonu için bir ikiliye ihtiyacınız vardır. Sizin$y_{ij}=y_{\ell j}$kısıtlamalar çözücünün önceden çözme işlevinin modeli bu boyuta küçültmesine izin verir, ancak daha küçük formülasyonla da başlayabilirsiniz. Ayrıca, sorunu ikinci dereceden yapmak yerine, muhtemelen en küçük ve en büyük bölüm boyutu arasındaki farkı en aza indiririm ki bu doğrusaldır. Bu, mutlaka çözülmesi "özellikle kolay" bir model üretmez, ancak sorun boyutlarınıza ve IP çözücünüze (ve sabrınıza) bağlı olarak yeterince kolay olabilir.
İkinci soru: Problemi tam olarak IP modeli ve bir IP çözücü kullanarak çözebilirsiniz. Makul derecede iyi sonuç verebilecek hızlı bir buluşsal yöntem,$K$ boş bölümler, grupları azalan boyut sırasına göre sıralayın, ardından her grubu şu anda en küçük bölüme atayın.
Üçüncü soru: Julia veya Python için konuşamıyorum (Python için bazı IP çözücüler bilmeme rağmen), ancak RI ile modeli yazmak için OMPR paketini (LP / IP için DSL) kullanmaya meyilliyim. OMPR, modeli çözmek için sırasıyla ROI'ye güvenecektir ve hem OMPR hem de ROI, çözücüye özgü bir eklenti yüklemenizi (ve tabii ki ilgili çözücünün kurulu olmasını) gerektirecektir.
OMPR ve ROI'yi kendi CPLEX eklentileriyle kullanarak bir R dizüstü bilgisayarını hackledim. Rastgele bir test probleminde$N=5700$, $M=130$ ve $K=10$, tarif ettiğim buluşsal yöntem tipik olarak 5'lik bir bölüm boyutu dağılımına (567 ile 572 arasında değişen boyutlar) ve IP modelinde her biri 570'lik on bölüme (yayılma = 0) sahipti. Buluşsal yöntem, saniyenin (küçük) bir kısmını aldı. IP modelini oluşturmak ve bunu CPLEX ile çözmek yaklaşık dokuz saniye sürdü.
Her zaman olduğu gibi, kilometreniz değişecektir.
EK: Problem boyutları için yuvarlak sayılar kullanmanın işleri daha iyi hale getirebileceğinden şüphelendim (doğru), bu yüzden denedim $N=5723$, $M=137$ ve $K=10$(bu, hiçbir çözümün tüm bölüm boyutlarının aynı olmamasını sağlar). IP çözümü 1'lik bir yayılmayı yönetti (bazı bölümlerde 572 öğe vardı, bazılarında 573 vardı, bu hala genel olarak ulaşılabilir olduğunu düşündüğümden daha iyi). Sezgisel çözümün yayılımı 30'du (bölüm boyutları 552 ile 582 arasında).
EK 2: Rob'un LPT buluşsal yöntemi olarak adlandırdığı şeyin arkasına bir ikili değişim buluşsal yöntemi ekledim. Örnekte$N=5723$vb., ikili takas sezgisel yöntemi, spread'i 30'dan 2'ye düşürdü, tam olarak optimal değil (optimal 1'dir) ama çok daha yakın. LPT gibi, takas sezgisel yöntemi de bu örnekte bir saniyenin çok altında kaldı.