NP menyelesaikan atau masalah sulit NP dalam kehidupan nyata

Apakah ada yang punya contoh kehidupan nyata di mana mereka secara teratur menyelesaikan masalah NP lengkap atau NP keras (oleh heuristik, atau mengejar solusi suboptimal atau apa pun) dalam pekerjaan mereka? Saya tahu mereka terjadi dalam penjadwalan, perencanaan, desain VLSI, dll, tetapi saya mencoba untuk mendapatkan gambaran tentang industri besar yang mempekerjakan programmer atau insinyur hari ini yang secara teratur melakukan ini. Jika seseorang ingin mengembangkan keahlian atau pustaka, katakanlah, optimasi kombinatorial di mana orang dapat menggunakannya sebagai bagian dari pekerjaan pemrograman?

Adakah akun pribadi?

Beberapa hal yang dapat saya pikirkan (sebagian besar dari ini saya terlibat dalam kurang lebih):

• Lingkungan pengembangan untuk bahasa dan kompiler. Pertanyaan seperti: apakah tata bahasa ini menghasilkan bahasa yang ambigu? (Masalah ini sebenarnya tidak dapat dipastikan!)
• Pemulihan data. Merakit kembali paket data yang sebagian hilang atau memulihkan file yang terfragmentasi. (Kompleksitas faktorial)
• Keamanan perangkat lunak. Penilaian semua jalur eksekusi yang mungkin melalui perangkat lunak untuk menentukan apakah beberapa perilaku yang diamati dapat dikaitkan dengannya. (Menghentikan masalah?)
• Logistik. Mengoptimalkan penggunaan transportasi berdasarkan paket untuk transportasi, ukurannya dan ke mana mereka harus pergi. (Setidaknya eksponensial)

Ada banyak contoh standar seperti menemukan rute terpendek, penjadwalan perawat, dll. Tetapi jika Anda ke optimasi kombinatorial, Anda tahu semua tentang itu :)

Saya telah menggunakan annealing simulasi waktu terbatas untuk menyelesaikan masalah perjalanan saleman dalam pembuatan panel sentuh. Setiap milidetik yang kami dapat mencukur dari siklus waktu laser etsa dari setiap panel akan meningkatkan throughput, pemanfaatan dan dengan demikian keuntungan dari mesin, jadi saya berusaha keras untuk meminimalkan waktu mati (jalur non scribing) di antara jalur penulisan (yang jelas tidak bisa dioptimalkan jauh).

Saya menggunakan algoritma terikat waktu untuk mengatasi kekerasan NP masalah, karena kami tidak mampu menanggung risiko bahwa perhitungan optimasi mungkin lebih lama dari waktu yang dihemat oleh jalur yang lebih optimal. Ketika mesin memindahkan panel dari posisi pemuatan ke posisi di mana kepala laser berada di sudut terdekat, saya punya waktu untuk menjalankan beberapa simulasi. Algoritma hampir tidak pernah berjalan sampai selesai dalam beberapa ratus milidetik dari langkah tersebut, tetapi hampir selalu mengembalikan jalur juru tulis yang lebih baik daripada model sederhana dan non-adaptif yang selalu kami gunakan sebelumnya (seperti jalur spiral atau ular).

Saya sedang bekerja (sekarang, sebenarnya) pada masalah bioinformatika dari penyelarasan urutan DNA lokal ganda. Intinya adalah bahwa jika banyak sekuens dari gen dengan beberapa sifat yang sama (profil ekspresi yang sama atau faktor transkripsi yang sama yang mengikat dalam percobaan chip-CHIP) menyelaraskan dengan kuat pada beberapa titik, maka Anda mungkin telah menemukan alasan kesamaannya. Properti. Kemudian lagi, saya lebih tertarik pada aspek statistik masalah. Meskipun ini NP-hard, Anda tidak kehilangan banyak dengan menggunakan heuristik dalam praktek. Bagian yang menarik dari masalah ini, IMHO, adalah masalah rasio sinyal terhadap noise.

Saya tidak benar-benar tahu, apa artinya NP lengkap / sulit, tapi saya pikir, supply autoplanning adalah sejenis itu.

Anda memiliki paket permintaan 90 hari ke depan untuk 100 produk SKU: bir! 100 produk SKU berasal dari:

• sudah ada 10-15 jenis bahan dasar diseduh level 1, mereka diseduh dalam kaleng besar liter liter, dan itu membutuhkan waktu sehari;
• setelah pembuatan bir, beberapa bahan harus ditambahkan (ragi?), dan harus istirahat selama 10-15 hari, maka Anda mendapat 15-20 jenis barang level-2;
• akhirnya, ketika sudah siap, beberapa bahan harus ditambahkan, itu barang level-3, yang disebut bir minum, ada cc. 30 jenis bir;
• bir dapat dibotolkan sebagai 3 dl, 5 dl, kadang-kadang mendapat necklacigng khusus (level 4), maka dapat dikemas sebagai kotak 5x4, 6-pack (level 5).

Ada "jalur" mesin untuk setiap operasi: dari pembuatan bir hingga pengemasan. Mesin-mesin dapat melakukan lebih banyak operasi, katakanlah, beberapa mesin pengepakan dapat membuat 6-pack dan 3-pack, tetapi yang lain hanya dapat melakukan 6-pack. Ada kendala, misalnya kecepatan, atau teko pembuatan bir besar adalah untuk menyeduh min. 6000, maks, 8000 l bir, (tetapi jika jenis bir ringan, min. Adalah 5000 l dan maks. 7000 l). Dan seterusnya, di setiap level.

Tugasnya: seperti yang saya sebutkan, ada rencana permintaan, untuk 100 jenis level-5 (botolan, barang yang dikemas). Buat rencana pembuatan yang optimal untuk semua 5 level, semua mesin. Minimalkan sakelar mesin (mis. Pembotolan .5, .5, .5, .3, .3, .3 lebih baik daripada .3, .5, .3, .5, .3, .5, ada lebih sedikit swithc, lebih sedikit waktu mati untuk mesin pembotolan). Diprioritaskan oleh pelanggan: beberapa pelanggan hanya perlu mengirimkan bir dengan sisa waktu kedaluwarsa lebih dari 50%. Dll.

Temukan kemacetan (eh), buat rencana alternatif dengan menambahkan mesin yang tidak ada ke titik-titik ini, maka skenario virtual terbaik dapat digunakan untuk menyarankan membeli mesin baru.

Apakah ini cukup sulit, atau haruskah saya beri tahu Anda cara kerja pabrik tekstil ?

(Pernyataan pribadi: web, bank, dan logistik adalah bidang yang menantang, tetapi itu mainan bayi dibandingkan dengan masalah manufaktur.)

Penafian: nomor terdistorsi karena alasan keamanan, urutan besarnya nyata.