Teknik baru yang menggabungkan pembelajaran mesin dengan pengoptimalan tradisional telah terbukti mempercepat proses pencarian solusi pemecah pemrograman linier bilangan bulat campuran hingga 70%, sehingga meningkatkan efisiensi di bidang logistik dan sektor lainnya. Kredit: SciTechDaily.com
Pendekatan baru berbasis data dapat menghasilkan solusi yang lebih baik untuk masalah pengoptimalan yang rumit seperti perutean paket global atau pengoperasian jaringan listrik.
Meskipun Sinterklas mungkin memiliki kereta luncur ajaib dan sembilan rusa kutub yang gagah berani untuk membantunya mengantarkan hadiah, bagi perusahaan seperti FedEx, masalah pengoptimalan dalam mengarahkan paket liburan secara efisien sangatlah rumit sehingga mereka sering kali menggunakan perangkat lunak khusus untuk menemukan solusinya.
Perangkat lunak ini, yang disebut pemecah pemrograman linier bilangan bulat campuran (MILP), membagi masalah optimasi besar-besaran menjadi bagian-bagian yang lebih kecil dan menggunakan algoritma umum untuk mencoba dan menemukan solusi terbaik. Namun, pemecah masalah bisa memakan waktu berjam-jam – atau bahkan berhari-hari – untuk sampai pada solusi.
Prosesnya sangat berat sehingga perusahaan sering kali harus menghentikan pembuatan perangkat lunaknya di tengah jalan, menerima solusi yang tidak ideal namun merupakan solusi terbaik yang dapat dihasilkan dalam jangka waktu tertentu.
Mempercepat Solusi Dengan Pembelajaran Mesin
Para peneliti dari MIT dan ETH Zurich menggunakan pembelajaran mesin untuk mempercepat pekerjaan.
Mereka mengidentifikasi langkah perantara utama dalam pemecah MILP yang memiliki begitu banyak solusi potensial sehingga memerlukan banyak waktu untuk mengungkapnya, sehingga memperlambat keseluruhan proses. Para peneliti menggunakan teknik penyaringan untuk menyederhanakan langkah ini, dan kemudian menggunakannya pembelajaran mesin untuk menemukan solusi optimal untuk jenis masalah tertentu.
Pendekatan berbasis data mereka memungkinkan perusahaan menggunakan datanya sendiri untuk menyesuaikan pemecah MILP tujuan umum dengan masalah yang dihadapi.
Teknik baru ini mempercepat pemecah MILP antara 30 dan 70 persen, tanpa penurunan apa pun ketepatan. Seseorang dapat menggunakan metode ini untuk mendapatkan solusi optimal dengan lebih cepat atau, untuk masalah yang sangat kompleks, solusi yang lebih baik dalam jangka waktu yang dapat diatur.
Pendekatan ini dapat digunakan di mana pun pemecah MILP digunakan, misalnya pada layanan transportasi online, operator jaringan listrik, distributor vaksinasi, atau entitas mana pun yang menghadapi masalah alokasi sumber daya yang pelik.
“Terkadang, dalam bidang seperti pengoptimalan, sangat umum bagi orang untuk menganggap solusi sebagai pembelajaran mesin murni atau klasik. Saya sangat yakin bahwa kita ingin mendapatkan yang terbaik dari kedua dunia, dan ini adalah contoh yang sangat kuat dari pendekatan hibrida tersebut,” kata penulis senior Cathy Wu, Asisten Profesor Pengembangan Karir Gilbert W. Winslow di bidang Teknik Sipil dan Lingkungan ( CEE), dan anggota dari Laboratorium Sistem Informasi dan Keputusan (LIDS) dan Institut Data, Sistem, dan Masyarakat (IDSS).
Wu menulis makalah ini bersama penulis utama Sirui Li, seorang mahasiswa pascasarjana IDSS, dan Wenbin Ouyang, seorang mahasiswa pascasarjana CEE; serta Max Paulus, seorang mahasiswa pascasarjana di ETH Zurich. Penelitian ini akan dipresentasikan pada Konferensi Sistem Pemrosesan Informasi Neural.
Sulit untuk Dipecahkan
Masalah MILP memiliki jumlah solusi potensial yang eksponensial. Misalnya, seorang penjual keliling ingin mencari jalur terpendek untuk mengunjungi beberapa kota dan kemudian kembali ke kota asalnya. Jika ada banyak kota yang dapat dikunjungi dalam urutan apa pun, maka jumlah solusi potensial mungkin lebih besar daripada jumlah atom di alam semesta.
“Masalah-masalah ini disebut NP-hard, yang berarti sangat kecil kemungkinannya ada algoritma yang efisien untuk menyelesaikannya. Ketika masalahnya cukup besar, kami hanya bisa berharap untuk mencapai kinerja yang kurang optimal,” jelas Wu.
Pemecah MILP menggunakan serangkaian teknik dan trik praktis yang dapat mencapai solusi yang masuk akal dalam waktu yang dapat ditentukan.
Solver pada umumnya menggunakan pendekatan membagi dan menaklukkan, pertama-tama membagi ruang solusi potensial menjadi bagian-bagian yang lebih kecil dengan teknik yang disebut percabangan. Kemudian, solver menggunakan teknik yang disebut pemotongan untuk mengencangkan bagian-bagian yang lebih kecil sehingga dapat dicari dengan lebih cepat.
Pemotongan menggunakan seperangkat aturan yang memperketat ruang pencarian tanpa menghilangkan solusi yang layak. Aturan-aturan ini dihasilkan oleh beberapa lusin algoritma, yang dikenal sebagai pemisah, yang telah dibuat untuk berbagai jenis permasalahan MILP.
Wu dan timnya menemukan bahwa proses mengidentifikasi kombinasi algoritma pemisah yang ideal untuk digunakan, dengan sendirinya, merupakan masalah dengan jumlah solusi yang eksponensial.
“Manajemen separator adalah bagian inti dari setiap pemecah masalah, namun ini adalah aspek yang kurang dihargai dalam ruang permasalahan. Salah satu kontribusi dari pekerjaan ini adalah mengidentifikasi masalah manajemen pemisah sebagai tugas pembelajaran mesin,” katanya.
Memperkecil Ruang Solusi
Dia dan kolaboratornya merancang mekanisme pemfilteran yang mengurangi ruang pencarian pemisah ini dari lebih dari 130.000 kombinasi potensial menjadi sekitar 20 opsi. Mekanisme pemfilteran ini mengacu pada prinsip keuntungan marjinal yang semakin berkurang, yang menyatakan bahwa manfaat terbesar akan diperoleh dari sejumlah kecil algoritma, dan menambahkan algoritma tambahan tidak akan membawa banyak perbaikan ekstra.
Kemudian mereka menggunakan model pembelajaran mesin untuk memilih kombinasi algoritma terbaik dari 20 opsi yang tersisa.
Model ini dilatih dengan kumpulan data khusus untuk masalah pengoptimalan pengguna, sehingga model ini belajar memilih algoritme yang paling sesuai dengan tugas khusus pengguna. Karena perusahaan seperti FedEx telah memecahkan masalah perutean berkali-kali sebelumnya, menggunakan data nyata yang diperoleh dari pengalaman masa lalu akan menghasilkan solusi yang lebih baik daripada memulai dari awal setiap saat.
Proses pembelajaran berulang dari model tersebut, yang dikenal sebagai bandit kontekstual, merupakan suatu bentuk pembelajaran penguatan, melibatkan pemilihan solusi potensial, mendapatkan umpan balik tentang seberapa bagus solusi tersebut, dan kemudian mencoba lagi untuk menemukan solusi yang lebih baik.
Pendekatan berbasis data ini mempercepat pemecah MILP antara 30 dan 70 persen tanpa penurunan akurasi. Selain itu, kecepatannya serupa ketika mereka menerapkannya pada pemecah sumber terbuka yang lebih sederhana dan pemecah komersial yang lebih kuat.
Di masa depan, Wu dan kolaboratornya ingin menerapkan pendekatan ini pada masalah MILP yang lebih kompleks, karena pengumpulan data berlabel untuk melatih model bisa menjadi tantangan tersendiri. Mungkin mereka dapat melatih model tersebut pada kumpulan data yang lebih kecil dan kemudian mengubahnya untuk mengatasi masalah pengoptimalan yang jauh lebih besar, katanya. Para peneliti juga tertarik untuk menafsirkan model yang dipelajari untuk lebih memahami efektivitas algoritma pemisah yang berbeda.
Referensi: “Belajar Mengkonfigurasi Pemisah pada Cabang-dan-Potong” oleh Sirui Li, Wenbin Ouyang, Max B. Paulus, Cathy Wu, 8 November 2023, Matematika > Optimasi dan Kontrol.
arXiv:2311.05650
Penelitian ini sebagian didukung oleh Mathworks, National Science Foundation (NSF), the DENGAN Amazon Science Hub, dan Komite Dukungan Penelitian MIT.
RisalahPos.com Network
Related posts
# PARTNERSHIP
