Apakah masalah optimasi kombinatorial ini mirip dengan masalah yang diketahui?

Masalahnya adalah sebagai berikut:

Kami memiliki array dua dimensi / kisi angka, masing-masing mewakili beberapa "manfaat" atau "keuntungan." Kami juga memiliki dua bilangan bulat tetap dan (untuk "lebar" dan "tinggi".) Dan bilangan bulat tetap .h $w$$h$$n$

Kami sekarang ingin melampui segi empat dimensi pada kisi sedemikian sehingga jumlah total nilai sel dalam segi empat ini dimaksimalkan.w × $n$$w \times h$

Gambar berikut adalah contoh dari grid dua dimensi dengan dua persegi panjang seperti itu overlay di atasnya (gambar tidak menunjukkan solusi optimal, hanya satu kemungkinan overlay di mana dan )n = $w = h = 2$$n = 2$

Persegi panjang tidak dapat berpotongan (jika tidak kita hanya perlu menemukan posisi optimal untuk satu persegi panjang dan kemudian meletakkan semua persegi panjang di posisi itu.)

Dalam contoh di atas, jumlah total nilai dalam sel adalah$-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Apakah ini mirip dengan masalah yang diketahui dalam optimasi kombinatorial? sehingga saya dapat mulai membaca dan mencoba menemukan cara untuk menyelesaikannya.

Beberapa latar belakang untuk mereka yang tertarik:

Sejauh ini satu-satunya ide yang saya miliki adalah algoritma serakah (yang akan menemukan lokasi terbaik untuk persegi panjang pertama, kemudian menemukan lokasi non-tumpang tindih untuk persegi panjang kedua dll) atau beberapa metaheuristik seperti algoritma genetika.

Pada kenyataannya saya ingin menyelesaikan masalah ini dengan grid yang memiliki sekitar satu juta sel dan puluhan ribu (atau bahkan ratusan ribu) persegi panjang, meskipun tidak perlu untuk menyelesaikannya dalam waktu singkat (yaitu akan diterima untuk algoritma untuk mengambil jam atau bahkan berhari-hari.) Saya tidak mengharapkan solusi yang tepat tetapi saya ingin mendapatkan yang sebaik mungkin mengingat kendala-kendala ini.

Bersulang!

Formulasi terakhir saya memiliki kesalahan fatal yang membutuhkan jumlah eksponensial dari "kendala" node.

Formulasi grafis alami lain dari masalah adalah membuat grafik di mana setiap simpul mewakili persegi panjang dengan . Setiap pasangan persegi panjang yang tumpang tindih memiliki keunggulan dalam grafik ini. Dengan memecahkan untuk set independen ukuran maksimum tertimbang kami memiliki solusi untuk masalah awal Anda. Ada banyak heuristik dan algoritma aproksimasi yang baik untuk ini.w r r , r ' k = $r$$w_r$$r, r'$$k=n$

Anda dapat memformulasikan ini sebagai instance pemrograman linier raksasa (ILP), dan kemudian menerapkan solver ILP yang tidak tersedia (lp_solve, CPLEX, dll.). Mereka akan memberi Anda solusi terbaik yang bisa mereka temukan. Mengingat ukuran contoh masalah Anda, saya tidak tahu apakah ini akan cukup efisien, tetapi akan mudah untuk mencoba.

Inilah formulasi ILP. Kami memiliki variabel nol-atau-satu untuk setiap persegi yang mungkin , dengan interpretasi yang dimaksudkan bahwa berarti Anda memasukkan persegi panjang di set Anda dan berarti Anda tidak memasukkannya. Anda ingin memaksimalkan fungsi objektif (di mana adalah keuntungan dari persegi panjang ), tunduk pada batasan yang dan bahwa tidak ada dua persegi panjang yang tumpang tindih. Pembatasan yang terakhir dapat dinyatakan sebagai ketidaksamaan linear dengan mensyaratkan untuk semua pasangan persegi panjang r x r = 1 r x r = 0 ∑ r c r x r c r r ∑ r x r = n x r + x s ≤ 1 r , $x_r$$r$$x_r=1$$r$$x_r=0$$\sum_r c_r x_r$$c_r$$r$$\sum_r x_r = n$$x_r + x_s \le 1$$r,s$tumpang tindih itu. Jadi, dengan cara ini Anda mendapatkan ILP.