- Mixed Integer Linear Programming (MILP) telah menjadi alat inti di berbagai sektor industri
- Berkat peningkatan efisiensi komputasi solver modern, masalah yang dulu sulit diselesaikan kini dapat menemukan solusi optimal dengan cepat
- Artikel ini berfokus pada perkembangan praktis terbaru dalam metode penyelesaian MILP serta peningkatan kinerja komputasi
- Metodologi utama yang diperkenalkan mencakup branch-and-cut, dekomposisi Dantzig-Wolfe, dekomposisi Benders
- Tantangan yang terus berlanjut di bidang MILP dan peluang riset masa depan juga dirangkum
Pendahuluan
- Mixed Integer Linear Programming (MILP) adalah alat penting dalam riset operasi dan telah berhasil digunakan di berbagai bidang industri
- Solver MILP modern kini mampu mencari solusi optimal untuk masalah berskala besar yang dulu tidak mungkin diselesaikan, hanya dalam hitungan detik
- Karena itu, penerapan MILP meluas ke berbagai bidang seperti transportasi, rantai pasok, manajemen pendapatan, keuangan, telekomunikasi, manufaktur
- Namun, masih ada masalah yang belum terselesaikan dan tantangan baru, sehingga riset MILP tetap terus berlangsung secara aktif
Gambaran Isi Utama
- Makalah ini berfokus pada perkembangan terbaru metode penyelesaian MILP dan peningkatan kinerja praktis, serta menganalisis bagaimana tiap teknik benar-benar berkontribusi pada peningkatan performa komputasi
- Di antara literatur yang sangat luas, pembahasan diprioritaskan pada penelitian yang didasarkan pada eksperimen komputasi nyata
- Pembahasan disusun dalam tiga bidang inti metode penyelesaian MILP
- Metode Branch-and-Cut: pendekatan penyelesaian MILP yang representatif dengan menggabungkan teknik pemecahan node dan cutting plane
- Dekomposisi Dantzig-Wolfe: pendekatan dekomposisi yang membagi masalah berskala besar menjadi submasalah yang lebih kecil agar dapat diproses secara efisien
- Dekomposisi Benders: metode yang menurunkan beban komputasi pada struktur kompleks dengan memisahkan variabel dan kendala lalu menyelesaikannya secara iteratif
Penutup: Tantangan dan Prospek Masa Depan
- Bagian akhir makalah meninjau tantangan MILP yang masih tersisa serta peluang riset di masa depan
- Masalah industri nyata yang semakin kompleks, skala data yang terus membesar, serta batas performa solver akan menjadi topik riset utama ke depan
- Ke depan, bidang MILP diperkirakan akan terus berkembang bersama kemajuan algoritme, perkembangan perangkat keras, dan meluasnya domain aplikasi baru
1 komentar
Opini Hacker News
Seseorang menyatakan rasa penasaran apakah ada yang bisa menjelaskan mengapa solver ILP komersial seperti Gurobi jauh lebih unggul daripada solver gratis/open source, apakah itu karena tingkat kesulitan ILP yang memang inheren, atau karena solver terbaik pada dasarnya adalah kumpulan heuristik besar untuk submasalah tertentu, sehingga strategi yang secara umum “bagus” belum tersedia di domain publik
Solver komersial umumnya bekerja sangat dekat dengan pelanggan untuk mengimplementasikan teknik percepatan yang spesifik pada masalah, dan memiliki pengetahuan yang terakumulasi selama 10–20 tahun; ditekankan bahwa di bidang MILP, heuristik yang baik (memilih titik awal branch-and-bound, memangkas cabang pohon secara efektif) serta custom cut (mengecualikan solusi parsial secara efisien) sangat penting; selain itu, peneliti OR yang memilih masalah sendiri lalu menulis cut dan heuristik khusus sering kali bisa memperoleh hasil yang lebih baik daripada solver komersial, tetapi perusahaan solver merekrut tim peneliti tingkat doktor untuk menerapkan hal-hal ini secara konsisten dan melacak perbaikan menggunakan banyak data masalah nyata dari pelanggan
Solver komersial bisa menginvestasikan waktu dan sumber daya dalam jumlah besar untuk menyetel performa pemecahan masalah karena pelanggan nyata peduli dan membantu; selain heuristik, ini juga mencakup proses mengenali submasalah sederhana atau masalah aproksimasi lalu mengumpankan hasilnya kembali ke masalah keseluruhan; solver open source memiliki keterbatasan karena (1) hambatan masuk untuk mengembangkan optimizer mutakhir sangat tinggi (sedikit orang yang mahir dalam matematika sekaligus coding), (2) jika seseorang punya kemampuan setingkat itu biasanya mereka beralih ke karier yang jauh lebih menghasilkan uang, dan (3) karena sifat open source, pelanggan hampir tidak pernah memberikan kasus untuk perbaikan, data performa, atau profiling, sehingga batasannya mudah terlihat Pengecualian ada pada kasus seperti SNOPT yang bersifat komersial tetapi pengembangannya tidak tradisional secara komersial, dan solver akademik biasanya fokus pada bidang aplikasi tertentu sehingga kurang umum; di bidang lain, perusahaan besar seperti Google kadang mengakuisisi atau mendukung proyek untuk membesarkan ekosistem, tetapi di dunia solver, investasi untuk membangun seluruh stack dari nol terlalu besar sejak awal
Solver komersial benar-benar dapat mengetahui trik mana yang efektif untuk suatu masalah melalui beragam trik dan mekanisme deteksi pola; jika struktur masalah dipahami dengan baik, orang bisa membuat sesuatu yang lebih cepat daripada solver komersial, tetapi untuk masalah acak peluangnya hampir tidak ada
Ada pendapat bahwa “solver = kumpulan berbagai heuristik untuk submasalah khusus”, lalu ditunjukkan bahwa hampir semua masalah NP-Hard memang seperti itu; ILP setara dengan SAT sehingga hal yang sama juga berlaku
Masalah skala komersial dan kecepatan juga disorot; kebanyakan perusahaan quantitative trading menjalankan masalah optimisasi yang sangat besar sesering mungkin, dan solver open source sering kali bahkan tidak mampu menyelesaikan masalahnya atau kehabisan memori, menunjukkan betapa besarnya kesenjangan tersebut
Seseorang mengenang pengalaman membuat alat alokasi sumber daya dengan pustaka IBM ILOG MILP; jika masalah serupa diselesaikan 20 tahun lalu, sesuatu yang sekarang selesai dalam 5 menit mungkin saat itu masih terus berjalan; performa komputer meningkat seribu kali dan algoritma juga meningkat seribu kali, jadi secara total ada peningkatan sejuta kali; dianggap sebagai hal yang layak direnungkan saat memprediksi masa depan; sebagai catatan, “sumber daya” yang dimaksud di sini adalah berlian
Ada pertanyaan tentang bagaimana ini benar-benar digunakan dalam praktik; apakah optimisasi numerik, karena keterbatasan umum yang berbasis data (keandalan, masalah data, dsb.), pada akhirnya sering kalah oleh pengambil keputusan penting yang memakai “feeling”
Di sebuah perusahaan, solver digunakan di seluruh stack: untuk optimisasi penjadwalan baterai rumah tangga dan EV, penjadwalan optimal portofolio ratusan ribu rumah, hingga perdagangan portofolio tersebut; harga spot listrik Uni Eropa juga ditentukan dengan menjalankan satu solver raksasa bernama Euphemia; disebutkan bahwa solver banyak dipakai di mana pun ada tujuan optimisasi yang jelas dan benar-benar terkait dengan uang
Contoh penggunaan nyata di perusahaan FMCG: (1) perencanaan tenaga penjualan dan rute pengiriman, (2) penjadwalan mesin, tenaga kerja, dan bahan untuk produksi, (3) penentuan tingkat stok yang tepat di gudang pusat distribusi, dll.; tidak sepenuhnya otomatis karena sulitnya peramalan permintaan
Dibagikan tautan studi kasus yang layak dirujuk: Studi kasus Gurobi, Studi kasus CPLEX, Studi kasus Hexaly (dulu LocalSolver)
Ada pertanyaan apakah seseorang bisa membagikan informasi harga aktual, karena pernah mendengar bahwa Gurobi cukup mahal
Harga spesifik tidak dipublikasikan, tetapi untuk tujuan belajar MIP disarankan tidak perlu membeli solver komersial seperti XPRESS/Gurobi/CPLEX dan cukup memakai lisensi gratis untuk mahasiswa atau solver MIP open source gratis untuk penggunaan nonkomersial, misalnya: HiGHS, SCIP
Katanya, penetapan harga berada di level “telepon lalu negosiasi”, dan jumlahnya disesuaikan berdasarkan seberapa banyak uang yang dihasilkan pelanggan
Ditekankan bahwa ini jauh lebih murah daripada pengambilan keputusan lambat yang suboptimal; untuk masalah kecil solver gratis seperti GLPK sudah cukup, tetapi untuk masalah besar di lapangan bisnis, mendapatkan jawaban tepat waktu hampir mustahil, sehingga solver premium dinilai sangat sepadan
Sekitar 10 tahun lalu, yang diingat adalah kira-kira 100 ribu dolar untuk lisensi beberapa server; jumlah pengguna atau batas jumlah server yang tepat sudah tidak diingat, tetapi disebutkan bahwa di industri nilai sebesar itu dianggap masuk akal
Gurobi juga menyediakan layanan cloud dengan penagihan per jam, dan lisensi nonakademik sangat mahal
Seseorang pernah mengimplementasikan sendiri hyperplane pemotong Gomory pada 1990-an, dan kagum melihat sejauh mana bidang ini berkembang; dulu butuh dua bulan untuk menyelesaikan masalah LP, sekarang 1 detik sudah cukup; laporan penelitian Bixby menyebut bahwa antara 1990 dan 2020, CPLEX dan Gurobi menjadi hampir 4 juta kali lebih cepat secara independen dari performa mesin
Antara 1988 dan 2004, hardware menjadi 1.600 kali lebih cepat dan solver LP 3.300 kali lebih cepat, sehingga peningkatan kumulatifnya saat itu sudah lebih dari 5 juta kali; solver MILP komersial juga menjadi lebih dari 1.000 kali lebih cepat dari 2001 hingga 2020 (50 dari algoritma, 20 dari komputer); ada rasa penasaran bagaimana jika data peningkatan kecepatan tiap bidang seperti ini dikumpulkan lalu dipecah menurut kontribusi algoritma dan komputer; di bidang compiler juga ada hasil seperti “Hukum Proebsting”, yaitu bahwa kemajuan compiler setiap 18 tahun memberi efek setara dengan penggandaan daya komputasi
Ada kesan bahwa pendekatan berbasis ML/AI ternyata tidak terlalu banyak dipakai untuk masalah seperti ini; memang ada makalah yang mencoba RL/GNN pada masalah skala kecil, tetapi pada akhirnya membeli lisensi Gurobi tampaknya tetap yang terbaik; saat mengerjakan optimisasi penjadwalan baru-baru ini, ada juga yang melihat contoh RL, tetapi performa nyatanya kurang memadai; untuk masalah besar, algoritma evolusioner dianggap optimal; pada akhirnya, jika formulasi masalah bisa disusun dengan baik, pendekatan berbasis OR tampaknya yang paling efisien
Tergantung jenis masalahnya; misalnya keputusan ON/OFF pembangkit listrik (unit commitment) sangat kompleks, tetapi solver MILP dapat dengan cepat mencari solusi optimum global; algoritma genetika tidak punya jaminan bisa keluar dari minimum lokal dan juga bisa lambat, sementara neural network selalu suboptimal
SAT adalah masalah GOFAI tradisional, dan solver SAT bisa ditulis dalam semua bahasa keluarga ML juga; jadi justru pendekatan “ML/AI” bisa saja sangat relevan
Ada komentar bahwa sebaiknya penanda pdf ditambahkan ke judul
Tautan tersebut ternyata mengarah ke abstrak, bukan pdf
Referensi pdf makalahnya bisa ditambahkan langsung: https://inria.hal.science/hal-04776866v1/document
Ada pendapat bahwa integer linear programming tampaknya tidak terlihat rumit
Pewarnaan 3-warna simpul graf (G3C) termasuk NP dan NP-Hard, jadi NPC; ada hasil bahwa jika ILP umum bisa diselesaikan maka G3C juga bisa diselesaikan; SAT juga NP-Complete, dan jika SAT bisa diselesaikan maka G3C bisa diselesaikan, sehingga jika G3C bisa diselesaikan maka faktorisasi bilangan bulat (FAC) juga mungkin; FAC bukan NPC, tetapi sangat penting dalam komputasi saat ini; jadi dapat disimpulkan bahwa jika ILP arbitrer bisa diselesaikan, algoritma kriptografi utama dapat dirusak, yang menunjukkan bahwa ILP adalah masalah yang sangat rumit; hal yang sering membingungkan banyak orang adalah bahwa instance acak dari masalah NPC biasanya relatif mudah diselesaikan, dan proporsi instance yang benar-benar sulit justru mengecil saat ukuran masalah membesar
Travelling Salesperson Problem (TSP) juga bisa dienkode sebagai ILP, yang menunjukkan tingkat kesulitannya
Kita harus mencari bilangan bulat yang paling memenuhi syarat, dan walaupun terlihat seperti bilangan riil, secara mendasar ini sama sekali berbeda; tidak ada solusi umum, yang ada hanya heuristik (sangat baik) untuk kasus-kasus khusus
Ini masalah yang lebih sulit daripada linear programming
Atau justru bisa dilihat sebagai masalah yang sangat realistis