Menghasilkan masalah optimisasi kombinasi yang menarik

9

Saya mengajar kursus tentang meta-heuristik dan perlu membuat contoh menarik dari masalah kombinatorial klasik untuk proyek jangka. Mari kita fokus pada TSP. Kami menangani grafik dimensi dan lebih besar. Saya mencoba tentu saja untuk menghasilkan grafik dengan matriks biaya dengan nilai yang diambil dari U acak ( 0 , 1 ) , dan menemukan bahwa (seperti yang diharapkan) histogram untuk biaya jalur (diambil dengan mengambil sampel banyak jalur acak) memiliki distribusi normal yang sangat sempit ( μ adalah 100 tetapi σ sekitar 4200U(0,1)μ 100σ4). Ini berarti, menurut saya, masalahnya sangat mudah, karena sebagian besar jalur acak akan berada di bawah rata-rata, dan jalur biaya minimum sangat dekat dengan jalur acak.

Jadi saya mencoba pendekatan berikut: Setelah menghasilkan -matrix, berjalan secara acak di sekitar grafik, dan secara acak (Bernoulli dengan p = 0,5 ) dua kali lipat atau membagi dua nilai tepi. Ini cenderung menurunkan semua nilai, akhirnya mencapai nol, tetapi jika saya mengambil jumlah langkah yang tepat, saya bisa mendapatkan distribusi dengan μ sekitar 2 dan σ sekitar 1 .U(0,1)p=0.5μ2σ1

Pertanyaan saya adalah, pertama, apakah ini bahkan definisi yang bagus untuk masalah yang menarik ? Idealnya saya ingin contoh yang sangat multi-modal (untuk fungsi lingkungan yang paling umum), dan yang memiliki sangat sedikit jalur di dekat nilai minimum, sehingga sebagian besar solusi acak akan sangat jauh dari optimal. Pertanyaan kedua adalah, mengingat uraian ini, bagaimana saya bisa menghasilkan instance dengan karakteristik seperti itu?

Alejandro Piad
sumber
3
Cari perpustakaan tolok ukur TSP, seperti yang dipelajari dalam OR (mis. Mencari karya di TSP oleh Applegate et al., Mis. Di sini )?
Neal Young
2
Ada TSPLIB dengan banyak contoh.
adrianN
Terima kasih, saya memeriksa tautannya, dan ini sangat membantu, tetapi pertanyaan saya adalah tentang membuat instance bukan karena saya ingin menyelesaikan contoh spesifik, tetapi karena saya mencari wawasan tentang apa yang membuat masalah kombinatorial yang baik, wawasan yang nantinya dapat diperluas ke masalah lain selain TSP.
Alejandro Piad
posting terkait: cstheory.stackexchange.com/questions/739/...
Neal Young
1
@ Alejandro, Masalah klik tersembunyi mungkin menjadi contoh dari apa yang Anda cari. Anda juga dapat mencari penelitian tentang contoh acak Kepuasan yang dianggap sulit.
Neal Young

Jawaban:

6

Salah satu pendekatan umum untuk menghasilkan instance yang lebih sulit adalah sebagai berikut:

  • Mulai dengan contoh masalah acak.
  • Sematkan "pintu belakang tersembunyi": pilih secara acak solusi yang baik (solusi yang kemungkinan jauh lebih baik daripada solusi apa pun yang sudah ada) dan modifikasi instance masalah untuk secara paksa menanamkan solusi ini ke instance instance.

U(0,1)U(0,c)c<1; mengurangi berat yang ada; atau memodifikasi edge yang ada dengan probabilitas tetap). Prosedur penyesuaian ini memastikan bahwa solusi optimal akan, dengan probabilitas tinggi, menjadi tur spesial yang Anda pilih. Jika Anda beruntung dan Anda memilih penyematan yang masuk akal, itu juga tidak akan mudah untuk mengenali di mana Anda menyembunyikan solusi khusus.

Pendekatan ini berasal dari ide-ide umum dalam kriptografi, di mana kami ingin membuat masalah pintu satu arah: di mana masalahnya sulit untuk dipecahkan tanpa pengetahuan tentang pintu jebakan rahasia, tetapi dengan pengetahuan tentang pintu jebakan rahasia, masalahnya menjadi sangat mudah. Ada banyak upaya untuk menanamkan pintu jebakan rahasia ke dalam berbagai masalah sulit (sambil tetap mempertahankan kekerasan masalah bahkan setelah pintu jebakan ditambahkan), dengan tingkat keberhasilan yang beragam. Tetapi pendekatan umum ini sepertinya bisa diterapkan, untuk tujuan Anda.

Contoh masalah yang dihasilkan mungkin sulit , tetapi apakah mereka menarik , dari sudut pandang praktis? Saya tidak tahu Mengalahkan saya. Mereka terlihat cukup buatan bagi saya, tetapi apa yang saya tahu?

Jika tujuan utama Anda adalah untuk memilih contoh masalah yang praktis relevan dan mewakili aplikasi TSP dunia nyata, saran saya akan mengambil pendekatan yang sama sekali berbeda. Alih-alih, mulailah dengan mensurvei aplikasi TSP dunia nyata, kemudian mencari contoh representatif dari masalah tersebut, dan mengonversinya menjadi instance masalah TSP yang sesuai - jadi Anda bekerja dengan instance masalah yang berasal dari masalah dunia nyata.

DW
sumber
Saya sangat menyukai pendekatan ini, memang sangat dekat dengan apa yang saya coba buat, dan sepertinya cukup mudah beradaptasi dengan masalah yang berbeda. Motivasi awal saya adalah membuat masalah tes untuk siswa, jadi meskipun saya mendapatkan masalah kata-sebenarnya, tetapi server saya baik untuk situasi yang agak artifisial (mencoba untuk menilai algoritma siswa). Bagaimanapun, saya akan mencari untuk mengadaptasinya juga untuk kebutuhan penelitian saya, tetapi itu akan membutuhkan pengamatan lebih dekat, seperti yang Anda katakan, untuk menentukan apakah instance yang dibuat cukup representatif. Terima kasih banyak, Anda mendapat +1 dan penerimaan saya.
Alejandro Piad
3

pendekatan yang sering memberi Anda kontrol tinggi atas sifat solusi adalah konversi dari satu masalah lengkap NP ke yang lain. sekarang Anda mendefinisikan "menarik" dalam pertanyaan Anda secara statistik, tetapi pendekatan lain yang rapi adalah menggunakan masalah klasik dari lapangan. favorit saya adalah anjak / SAT. itu sepele untuk menemukan nomor "halus" dengan banyak faktor, atau bilangan prima dengan hanya dua "faktor" (satu dan prima). buat instance SAT untuk menyelesaikan anjak piutang, dan solusinya adalah faktor (sebenarnya permutasi faktor, tetapi juga yang tidak sulit untuk dihitung sebelumnya).

di bawah pendekatan ini, ada definisi alami tentang "menarik" - contoh kasar yang tidak dapat diselesaikan pada waktu P. dan pendekatan ini dijamin untuk menghasilkan contoh-contoh sulit untuk anjak angka-angka tidak mulus kalau tidak akan menyelesaikan pertanyaan terbuka utama dalam teori kompleksitas yaitu kekerasan anjak piutang .

kemudian, mungkin dikonversi ke masalah Anda, dalam hal ini TSP. untuk mengisi jawaban ini akan menyenangkan untuk memiliki SAT langsung ke konversi TSP, berpikir mereka di luar sana, tetapi saya tidak terbiasa dengan mereka. Namun, berikut adalah beberapa rujukan pada factoring-to-SAT dalam pertanyaan ini: mengurangi masalah faktorisasi bilangan bulat menjadi masalah lengkap NP

jika Anda tidak suka anjak piutang, mungkin masih lebih disukai untuk membuat instance di SAT terlebih dahulu karena berbagai alasan. Anda bisa mulai dengan instance SAT acak yang disetel ke pusat di titik transisi mudah-sulit-mudah, dan sebagainya. atau Anda dapat bekerja dari instance keras DIMACS , yang dihasilkan oleh komunitas. atau buat "program" logis lainnya di SAT.

vzn
sumber
1
Saya suka pendekatan konversi, meskipun Anda tidak memberikan tautan lebih lanjut yang secara khusus terkait dengan TSP, tetapi tetap terima kasih atas idenya, saya akan menjelajahinya lebih dalam. Anda mendapat +1 saya.
Alejandro Piad
1
@alejandro thx ok inilah link tentang itu. lihat misalnya mulai pada slide 28 di sini [kelas sarjana!], CMSC 451: SAT, Pewarnaan, Siklus Hamiltonian, TSP Slides Oleh: Carl Kingsford . mengkonversi SAT → Hamiltonian cycle (TSP). mungkin ada pendekatan konversi yang lebih efisien (kurang overhead) atau dengan aspek-aspek khusus lainnya dalam literatur jika itu yang diinginkan. berharap untuk mendengar lebih lanjut dari pekerjaan Anda, mungkin membalas di sini atau di blog saya jika Anda suka
vzn
1
Saya memeriksa pdf, level yang sangat tinggi tetapi cukup dimengerti. Meskipun untuk saat ini saya mendapatkan apa yang saya butuhkan dengan jawaban @DW, pendekatan Anda tampaknya sangat menarik bagi saya. Saya harus mencobanya sendiri. Saya telah melihat pengurangan sebelumnya (pada program sarjana kompleksitas) tetapi belum memikirkan implementasi aktual khusus untuk membuat contoh-contoh sulit. Saya memiliki minat jangka panjang dalam optimasi, dan metaheuristik, dan salah satu bidang minat saya adalah tentang menciptakan masalah tolok ukur yang menarik. BTW, baru saja memeriksa blog Anda, pasti akan kembali !!!
Alejandro Piad