- Untuk masalah optimisasi yang memerlukan keputusan dalam satuan bilangan bulat, seperti perencanaan produksi, penjadwalan kru, dan rute kendaraan, Victor Reis dan Thomas Rothvoss memperkenalkan algoritma baru yang secara signifikan memangkas waktu eksekusi ILP
- ILP lebih rumit daripada pemrograman linear biasa, dan karena hampir tidak ada peningkatan rekor sejak 1980-an, hasil ini dipandang sebagai kemajuan besar setelah puluhan tahun
- Pendekatan baru ini menggabungkan alat geometris yang menangani irisan antara lattice dan convex body, sehingga mempersempit rentang solusi bilangan bulat yang mungkin dengan lebih kuat
- Intinya adalah memanfaatkan hasil tahun 2016 terkait titik lattice untuk menurunkan batas atas covering radius, sehingga waktu eksekusi berkurang hingga tingkat ((\log n)^{O(n)})
- Meski belum langsung diterapkan pada sistem logistik nyata, hasil ini hampir mendekati batas kecepatan teoretis ILP dan menunjukkan arah jangka panjang untuk peningkatan solver praktis
Mengapa kendala bilangan bulat membuat optimisasi menjadi sulit
- Traveling salesman problem adalah masalah komputasi lama untuk mencari rute terpendek yang melewati sejumlah kota, dan jika semua rute yang mungkin diperiksa, jumlah kota yang bertambah sedikit saja sudah membuatnya sulit ditangani
- Pemrograman linear adalah model matematis yang menangani kombinasi yang mungkin secara sistematis melalui persamaan dan pertidaksamaan
- Dalam masalah optimisasi di dunia nyata, jawaban desimal sering kali tidak berguna
- Dalam rencana optimisasi pabrik, jawaban untuk memproduksi 500,7 sofa sulit digunakan sebagai keputusan nyata
- Integer linear programming (ILP) adalah variasi pemrograman linear dengan kendala bilangan bulat seperti ini, dan banyak digunakan untuk masalah keputusan diskrit seperti perencanaan produksi, penjadwalan kru maskapai, dan penentuan rute kendaraan
- Santosh Vempala memandang ILP sebagai alat inti dalam riset operasi, baik secara teori maupun praktik
Batas kecepatan yang membaik lambat sejak 1980-an
- Setelah diformalkan lebih dari 60 tahun lalu, berbagai algoritma untuk ILP telah muncul, tetapi dari sisi jumlah langkah yang diperlukan, ILP masih tergolong lambat
- Titik acuan paling sederhana adalah kasus variabel biner, ketika variabel hanya dapat bernilai 0 atau 1
- 1 variabel memiliki 2 kombinasi yang mungkin
- 2 variabel memiliki 4 kombinasi
- 3 variabel memiliki 8 kombinasi
- Secara umum, waktu eksekusi meningkat secara eksponensial terhadap jumlah variabel, yaitu dimensinya
- Jika variabel dapat memiliki nilai bilangan bulat yang lebih luas, melampaui 0 dan 1, waktu eksekusinya menjadi jauh lebih lama
- Para peneliti telah lama menyelidiki apakah ILP umum bisa dibuat lebih mendekati kecepatan kasus biner sederhana ini
- Setelah rekor pada 1980-an, peningkatan yang terjadi hanya bertahap
Interpretasi geometris yang dibuka oleh Lenstra
- Pada 1983, Hendrik Lenstra membuktikan bahwa masalah ILP umum dapat diselesaikan dan memperkenalkan algoritma pertama untuk itu
- Lenstra menangani ILP dengan mengubahnya menjadi masalah geometris
- Pertidaksamaan dalam ILP direpresentasikan sebagai bangun cembung, yaitu convex body
- Bagian dalam bangun tersebut bersesuaian dengan semua nilai yang mungkin memenuhi pertidaksamaan
- Masalah dengan 2 variabel menjadi poligon pada bidang, sedangkan masalah dengan 3 variabel menjadi bentuk 3 dimensi; dimensinya bertambah seperti itu
- Semua bilangan bulat secara matematis dapat dipandang sebagai titik pada lattice
- Dalam 2 dimensi, ia terlihat seperti lautan titik
- Dalam 3 dimensi, ia menjadi struktur seperti titik pertemuan rangka baja bangunan
- Pada akhirnya, menyelesaikan ILP berarti mencari irisan antara convex body dan lattice, yakni lokasi tempat solusi yang mungkin bertemu dengan titik bilangan bulat
- Algoritma Lenstra dapat menelusuri ruang ini, tetapi demi efisiensi kadang masalah harus dipecah menjadi potongan berdimensi lebih rendah, dan proses ini menambah waktu eksekusi
Covering radius yang menjadi bottleneck selama 30 tahun
- Pada 1988, Ravi Kannan dan László Lovász mencoba menangani irisan convex body dan lattice dengan lebih efisien menggunakan konsep covering radius yang diambil dari riset kode koreksi galat
- Covering radius terkait dengan ukuran yang menjamin bahwa di mana pun convex body ditempatkan di atas lattice, ia akan memuat setidaknya satu titik bilangan bulat
- Besarnya nilai ini menentukan seberapa efisien masalah ILP dapat diselesaikan
- Menentukan ukuran covering radius yang ideal itu sendiri merupakan masalah yang sulit
- Kannan dan Lovász mempersempit nilai yang mungkin melalui batas atas dan batas bawah, serta menunjukkan bahwa batas atas tumbuh secara linear terhadap dimensi
- Hasil ini saja belum cukup untuk memangkas waktu eksekusi ILP secara besar-besaran, dan selama 30 tahun berikutnya ruang peningkatannya terbatas
Algoritma baru Reis dan Rothvoss
- Victor Reis dan Thomas Rothvoss menciptakan terobosan dengan memanfaatkan hasil matematika terpisah yang berfokus pada lattice
- Pada 2016, Oded Regev dan Noah Stephens-Davidowitz menunjukkan berapa banyak titik lattice yang dapat masuk ke dalam bangun tertentu
- Reis dan Rothvoss menerapkan hasil ini pada bangun lain untuk memperkirakan dengan lebih baik jumlah titik lattice yang termasuk dalam covering radius ILP
- Perkiraan ini membuat batas atas menurun, dan waktu eksekusi keseluruhan algoritma ILP berkurang secara signifikan
- Waktu eksekusi baru adalah ((\log n)^{O(n)}), dengan (n) sebagai jumlah variabel dan (O(n)) berbanding lurus secara linear dengan (n)
- Ekspresi ini dianggap “hampir” setara dengan waktu eksekusi masalah variabel biner
Jarak antara capaian teoretis dan penerapan nyata
- Noah Stephens-Davidowitz memandang algoritma baru ini sebagai peningkatan besar pertama pada solver ILP dalam hampir 40 tahun
- Daniel Dadush menilai hasil ini sebagai capaian yang lahir di persimpangan matematika, ilmu komputer, dan geometri
- Algoritma baru ini belum digunakan untuk menyelesaikan masalah logistik nyata
- Diperlukan banyak pekerjaan untuk memperbarui program saat ini agar sesuai dengan metode ini
- Rothvoss melihat fokus hasil ini pada pemahaman teoretis atas masalah yang memiliki penerapan mendasar
- Masih ada kemungkinan efisiensi komputasi ILP menjadi lebih baik, tetapi Vempala menilai bahwa untuk semakin mendekati waktu eksekusi ideal, diperlukan ide yang secara fundamental baru
1 komentar
Komentar Hacker News
Menurunkan batas atas algoritmik untuk masalah inti NP-complete selalu sangat menarik, tetapi itu belum tentu berarti masalah tersebut akan diselesaikan lebih cepat dalam implementasi nyata
Solver mixed integer programming (MIP) menggunakan banyak algoritma beserta sejumlah besar heuristik, dan akumulasi pustaka heuristik serta strategi adalah alasan utama peningkatan solver MIP telah melampaui Hukum Moore
Menurut https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., pada 1990–2014 peningkatan hardware mencapai 6500 kali, tetapi peningkatan software berkontribusi pada kenaikan performa 870000 kali
Makalah ini juga bisa menjadi satu keping puzzle yang melanjutkan peningkatan performa solver MIP, tetapi tidak ada jaminan demikian
Saya kurang paham penjelasan bahwa alasan algoritma baru ini belum dipakai untuk menyelesaikan masalah logistik adalah karena “memperbarui program saat ini membutuhkan terlalu banyak pekerjaan”
Sebagian besar model khusus domain memanggil solver Gurobi, CPLEX, FICO untuk masalah besar, dan memakai solver open source seperti SCIP untuk masalah kecil
Model dapat dipertukarkan di antara solver-solver ini dengan format MPS standar, formulasi masalahnya tidak berubah, dan bukankah yang perlu berubah hanya cara penyelesaian di dalam solver?
Jika maksudnya perlu implementasi baru, maka manfaat yang bisa diperoleh dunia ketika itu diimplementasikan tampaknya juga akan sangat besar
Alat-alat ini adalah hasil rekayasa yang sangat kompleks dari akumulasi perbaikan bertahap selama puluhan tahun, jadi sekadar mencari cara mengintegrasikan temuan baru ini ke dalam engine seperti itu saja tampaknya membutuhkan upaya riset yang cukup besar
Memang ada cara standar untuk bertukar formulasi masalah lewat format seperti MPS, dan sekarang tampaknya bahasa pemodelan aljabar seperti AMPL lebih banyak digunakan, tetapi yang diberikan format semacam itu hanyalah formulasi matematis standar
Penyelesaian aktual sangat spesifik untuk tiap solver, dengan struktur data, algoritma, dan teknik heuristik masing-masing
Semua itu tidak dapat saling dipertukarkan, tidak sengaja dibuka ke publik, dan kita tidak bisa sekadar menyisipkan beberapa angka eksternal di tengah proses tanpa pengetahuan tentang kode solver dan keseluruhan alurnya
Saya ingin meluruskan kesalahpahaman itu
Kalau bisa, saya akan menghindari mengimplementasikan sesuatu langsung dengan itu
Namun itu tidak mengubah fakta bahwa hasilnya sangat bagus
Dari sudut pandang kompleksitas komputasi teoretis, algoritma terbaik untuk “integer linear programming” [2] berbasis lattice dan memiliki kompleksitas big-O kasus terburuk yang paling baik
Namun implementasi saat ini umumnya (1) membutuhkan aritmetika bilangan rasional berpresisi arbitrer seperti gmplib [3], sehingga boros memori dan secara nyata lambat, serta (2) membutuhkan tahap reduksi lattice tipe LLL [4], tetapi tidak dapat memanfaatkan sparsity matriks
Akibatnya algoritma semacam ini biasanya tidak muat di memori, sehingga masalah matriks yang lebih besar dari 1000x1000 bahkan tidak bisa mulai dijalankan; sekalipun muat, prosesnya terlalu lambat
Solver integer programming di praktiknya justru berbasis branch and bound, algoritma backtracking yang mirip dengan yang digunakan untuk SAT solving, dan pada setiap iterasi menyelesaikan masalah “linear programming” yang diperoleh dari masalah asli dengan mengubah semua variabel menjadi variabel kontinu
Setiap masalah linear programming dapat diselesaikan dengan algoritma waktu polinomial seperti metode interior-point, tetapi dalam praktiknya digunakan simplex method, yang pada kasus terburuk memerlukan waktu eksponensial
Alasannya, masalah-masalah linear programming yang harus diselesaikan sangat mirip satu sama lain, dan simplex method dalam praktiknya mampu memanfaatkan hal itu dengan baik
Selain itu, algoritma terkait sangat memanfaatkan sparsity pada vektor dan matriks
Karena itu, sebagian orang bahkan dapat menyelesaikan masalah integer programming dengan jutaan variabel dalam hitungan hari, bahkan beberapa jam
Para implementor solver tidak mengejar kompleksitas teoretis terbaik secara absolut, dan bisa dibilang teori serta praktik optimisasi diskret sudah agak terpisah
Meski begitu, makalah Reis & Rothvoss [1] adalah karya matematika yang mendalam, dan bagi siapa pun yang tertarik pada matematika diskret, karya itu sendiri sangat mengesankan
Mereka memecahkan konjektur Dadush yang sudah berusia 10 tahun, dan makalahnya dipresentasikan pada November lalu di FOCS, salah satu dari dua konferensi papan atas dalam teori ilmu komputer
Kegunaan praktis langsung bukanlah poin utamanya, dan para penulis pun dalam forum informal kemungkinan akan mengakuinya
Tentu saja dalam proposal pendanaan riset mereka akan berkata lain, tetapi itu bagian dari permainannya
Ini bukan berarti tidak berguna; memajukan pengetahuan matematika saja sudah bernilai besar, dan beberapa generasi peneliti setelahnya mungkin membangun algoritma praktis di atas ide ini dan mendorong batas terdepan solver
Pada akhirnya semua algoritma ini dalam kasus terburuk tetap membutuhkan waktu eksponensial
Dalam teori, orang akan mencoba sedikit mengurangi polinomial yang ada pada eksponen kompleksitas kasus terburuk, tetapi praktisi biasanya ingin menyelesaikan satu masalah optimisasi besar, bukan keluarga masalah dengan ukuran n yang makin besar
Yang penting bukan laju kenaikan garis tren waktu penyelesaian, melainkan apakah satu instance besar di depan mereka bisa diselesaikan; dan instance itu biasanya memiliki struktur yang membuatnya tidak menjadi kasus terburuk untuk ukuran yang sama
Karena itu pilihan rekayasanya juga berbeda
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
Abstraknya lebih informatif: https://arxiv.org/abs/2303.14605
Isinya adalah bahwa mereka memperoleh algoritma acak waktu (log(2n))^O(n) untuk menyelesaikan integer programming dengan n variabel
Jadi pekerjaan ini merupakan hasil teoretis, yang berdasarkan analisis struktur benda konveks di R^n dan cara menutupinya dengan kisi bilangan bulat, menyajikan algoritma waktu eksponensial yang lebih baik daripada yang terbaik sebelumnya
Sebagian besar pekerjaan ILP praktis memakai heuristik dan branch-and-bound, serta memanfaatkan struktur khusus dari formulasi masalah tertentu
Belum jelas apakah riset ini akan membantu salah satu dari keduanya, dan rasanya sulit menilainya hanya dengan membaca makalah kecuali ada seseorang dari tempat seperti Gurobi yang menjelaskannya
Ini catatan kecil, tetapi judulnya harus secara eksplisit menyebut integer linear programming
Karena di sini bagian “integer” membuat perbedaan yang jauh lebih besar
Untuk linear programming, algoritma waktu polinomial sudah dikenal sejak puluhan tahun lalu, dan integer linear programming-lah yang NP-hard
Continuous linear programming juga sulit
Bukan dalam arti NP-hard, melainkan bahwa membuat LP solver modern yang efisien membutuhkan banyak aspek algoritma dan rekayasa
Komputasi numeriknya saja sudah cukup kompleks
Dan banyak solver integer linear programming berbasis pada solver continuous linear programming
Jika Anda software engineer yang tertarik pada machine learning atau algoritma, linear programming layak dipelajari
Sangat banyak masalah yang secara mengejutkan dapat diformulasikan sebagai optimisasi linear
Misalnya, saat kuliah saya pernah berbincang dengan teman jurusan teknik industri tentang rata-rata jumlah pertukaran minimum yang diperlukan untuk menempatkan bola biliar pada posisi awal yang valid di dalam segitiga rack
Kami berdua menulis program untuk menyelesaikannya dengan sampling Monte Carlo; solusi saya memakai BFS pada ruang status graf, sedangkan solusi teman saya memakai linear programming
Kemungkinan solusi teman saya lebih efisien
Contohnya minimum spanning tree, matching pada graf bipartit atau graf umum, network flow, matroid intersection, submodular flow, dan sebagainya
Solusi titik sudut dari suatu LP juga memiliki sifat menarik yang dapat dimanfaatkan saat merancang algoritma aproksimasi untuk masalah NP-complete
Misalnya, dapat dibuktikan bahwa pada solusi titik sudut untuk masalah Steiner forest selalu ada variabel bernilai minimal 1/2, sehingga dengan membulatkan variabel secara berulang dan menyelesaikan ulang LP, kita bisa mendapatkan algoritma 2-aproksimasi
Saat saya di pascasarjana, itu adalah satu-satunya algoritma 2-aproksimasi yang ada untuk masalah ini
Hal menarik lainnya adalah jika memiliki separation oracle waktu polinomial, kita bisa menyelesaikan LP meskipun jumlah kendalanya eksponensial
Benar-benar menyenangkan dan layak direkomendasikan
Saat ini pun di bidang operations research ada tumpang tindih yang mengejutkan besarnya, tetapi mengejutkan sekali betapa banyak lulusan teknik industri yang tidak benar-benar bisa memprogram dengan baik
Sungguh disayangkan
Biasanya kita hanya bisa berdagang dalam jumlah bilangan bulat pada satuan sen, jadi seingat saya bagian integer itu cukup penting
Tulisan yang singkat tetapi bagus
Saya belum melihat matematikanya secara mendalam, tetapi preprint-nya tampaknya ini: https://arxiv.org/pdf/2303.14605.pdf
Sepertinya mereka tidak melihat space group secara langsung sebagai cara menggeneralisasi dan menyederhanakan “ruang” masalah dengan mengurangi simetri atau repetisi, tetapi akan menarik untuk melihat apakah struktur seperti itu bisa diterapkan
Sebagai pengguna software yang menerapkan space group dan menjelaskan sel Voronoi di sekitar titik atau kumpulan titik yang tersebar di dalamnya, saya akrab dengan cara efeknya merambat secara “menyeramkan” [1]
Saya bukan matematikawan, hanya arsitek, jadi bidang ini di luar kemampuan saya, tetapi sebagai orang yang mengamati lintasan melintasi struktur honeycomb yang dihasilkan, hasil ini layak diselidiki lebih lanjut
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Jika Anda mengenal matematikawan yang mungkin mau berkolaborasi dalam pekerjaan seperti ini, saya akan senang jika dihubungi
Ini pekerjaan yang sedang berjalan, dan seperti saya katakan, secara matematis di luar kemampuan saya, tetapi saya menemukan sifat-sifat menarik yang layak ditelaah lebih dalam oleh pakar sungguhan
Terkait masalah traveling salesman, kutipan dari buku terbaru Sapolsky, Determined: A Science of Life without Free Will, menarik
Saya tidak tahu seberapa relevan ini bagi pengembang perangkat lunak, tetapi tetap memikat
Ketika semut mencari makanan dengan memeriksa delapan lokasi, idealnya ia hanya mengunjungi tiap lokasi sekali dan memilih rute terpendek dari 5.040 rute yang mungkin, yaitu 7!
Ini adalah salah satu bentuk masalah traveling salesman yang terkenal, yang sudah digeluti para matematikawan selama berabad-abad tanpa menemukan solusi umum
Salah satu strategi adalah brute force: menelusuri dan membandingkan semua rute yang mungkin, lalu memilih yang terbaik. Namun, dengan hanya 10 tempat yang harus dikunjungi saja, kemungkinan caranya sudah lebih dari 360 ribu, dan dengan 15 tempat lebih dari 80 miliar
Namun isinya mengatakan bahwa jika sekitar 10 ribu semut dalam koloni biasa dilepas pada persoalan delapan titik makanan, meskipun tidak ada semut yang tahu lebih dari rute yang ditempuhnya sendiri dan dua aturan, mereka menemukan solusi yang hampir optimal dari 5.040 kemungkinan dalam waktu jauh lebih singkat daripada brute force
Cara ini bekerja dengan baik sehingga ilmuwan komputer juga memecahkan masalah semacam ini dengan “semut virtual”, dan hal ini kini dikenal sebagai kecerdasan kawanan
Dan respons standarnya adalah “algoritma komputer yang sangat sederhana pun melakukan hal itu”
Untuk masalah traveling salesman dengan jarak Euclidean—yakni ketika tiap node memiliki koordinat tetap dan biaya rute adalah jarak Euclidean antara dua titik—kita bahkan bisa memberikan algoritma waktu polinomial yang menemukan rute dalam faktor ε dari solusi optimal
Namun terhadap ε, kompleksitasnya eksponensial
Pengantarnya juga punya penafian yang bagus
“Kami secara pribadi percaya bahwa literatur di bidang ini membutuhkan lebih sedikit marsupial dan lebih banyak matematika, dan bahwa sebagai komunitas kita perlu melewati masa yang kaya metafora ini, mirip seperti kimia yang meninggalkan alkimia. Namun daftar ini tidak membuat klaim apa pun tentang kualitas ilmiah makalah-makalah yang dicantumkan.”
[1]: https://fcampelo.github.io/EC-Bestiary/
Ini adalah algoritma yang memodelkan perilaku koloni semut seperti itu
Seperti yang dikatakan orang lain, ini bagus untuk menemukan optimum lokal, seperti tabu search, simulated annealing, dan genetic algorithm
Untuk kebanyakan tujuan bisnis seperti contoh “produksi sofa” dalam artikel, tingkat ini sudah cukup
Namun itu berbeda dari menemukan “solusi umum”
Perbandingan Sapolsky antara ketidakmampuan kita menemukan “solusi umum” dan kemampuan semut menemukan optimum lokal tampaknya agak menyesatkan
Artinya bukan bentuk umum masalahnya tidak NP-hard, melainkan bahwa dengan menambahkan lebih banyak informasi, kita bisa membuatnya memungkinkan untuk mengaproksimasi solusi yang cukup baik atau menangani pencarian optimal
Sudut pandang ini sangat menonjol pada “revolusi” AI pertama, ketika populer melihat AI sebagai masalah pencarian yang diperkuat oleh pengetahuan manusia
Apakah ini yang dimaksud buku itu dengan “kecerdasan kawanan”?
Banyak masalah optimasi diskret dapat diterjemahkan menjadi linear programming
Seperti SAT solver, ini alat yang sangat kuat kalau diketahui
Sebagai pengembang, itu salah satu momen “bagaimana bisa saya melewatkan ini selama ini?”
Hasil yang hebat, tetapi mungkin tidak praktis
Mirip seperti dalam linear programming, metode interior point memiliki kompleksitas teoretis yang lebih baik daripada metode simplex, tetapi di dunia nyata simplex yang dituning dengan baik hampir selalu menang
Apakah ada “alasan” yang diterima luas mengapa metode interior point biasanya lebih lambat dalam praktik?
Rasanya melewati bagian dalam seharusnya bisa mendekati solusi yang baik lebih cepat daripada terikat pada batas, tetapi mungkin di dimensi tinggi perbedaan itu kurang penting
Ungkapan yang dipakai di sini agak membingungkan
Ada kalimat, “Versi terbaik yang mereka pikirkan, semacam batas kecepatan, berasal dari kasus sepele ketika variabel masalah hanya dapat mengambil nilai biner, yaitu 0 atau 1, seperti apakah traveling salesman mengunjungi sebuah kota atau tidak.” Apakah mereka menyebut masalah NP-complete sebagai kasus sepele?
Setahu saya semua ILP dapat direduksi menjadi 01-ILP dan sebaliknya
Lalu dari bagian “Sayangnya, ketika variabel mengambil nilai di luar 0 dan 1, waktu jalan algoritma menjadi jauh lebih lama. Para peneliti sudah lama bertanya-tanya apakah mereka bisa lebih mendekati ideal sepele ini,” saya jadi bertanya-tanya apakah riset ini adalah solver yang memperbaiki batas bawah 01-ILP, atau algoritma yang membuat batas antara 01-ILP dan ILP umum menjadi lebih dekat