Peneliti Mendekati Batas Kecepatan Baru untuk Masalah Penting | Majalah Kuanta

Masalah tenaga penjual keliling adalah salah satu pertanyaan komputasi tertua yang diketahui. Ia menanyakan rute ideal melalui daftar kota tertentu, meminimalkan jarak tempuh. Meski tampak sederhana, permasalahannya terkenal sulit. Meskipun Anda dapat menggunakan kekerasan untuk memeriksa semua kemungkinan rute hingga Anda menemukan jalur terpendek, strategi seperti itu menjadi tidak dapat dipertahankan hanya setelah beberapa kota. Sebagai gantinya, Anda dapat menerapkan model matematika ketat yang disebut pemrograman linier, yang secara kasar memperkirakan masalah sebagai sekumpulan persamaan dan secara metodis memeriksa kemungkinan kombinasi untuk menemukan solusi terbaik.

Namun terkadang, Anda perlu mengoptimalkan masalah yang melibatkan jumlah bilangan bulat. Apa gunanya rencana pengoptimalan pabrik yang memproduksi 500.7 sofa? Untuk ini, peneliti sering beralih ke varian pemrograman linier yang disebut pemrograman linier bilangan bulat (ILP). Ini populer dalam aplikasi yang melibatkan keputusan terpisah, termasuk perencanaan produksi, penjadwalan awak maskapai penerbangan, dan perutean kendaraan. “Pada dasarnya ILP adalah inti dari riset operasi baik secara teori maupun praktik,” ujarnya Santosh Vempala, seorang ilmuwan komputer di Institut Teknologi Georgia.

Sejak pertama kali mereka merumuskan ILP lebih dari 60 tahun yang lalu, para peneliti telah menemukan berbagai algoritma yang memecahkan masalah ILP, namun semuanya relatif lambat dalam hal jumlah langkah yang diperlukan. Versi terbaik yang bisa mereka dapatkan - semacam batas kecepatan - berasal dari kasus sepele di mana variabel masalah (seperti apakah seorang salesman mengunjungi suatu kota atau tidak) hanya dapat mengasumsikan nilai biner (nol atau 1). Dalam hal ini, ILP memiliki runtime yang berskala secara eksponensial dengan jumlah variabel, disebut juga dimensi. (Jika hanya ada satu variabel, hanya diperlukan dua langkah untuk menguji setiap kemungkinan kombinasi dan memecahkan masalah; dua variabel berarti empat langkah, tiga berarti delapan langkah, dan seterusnya.)

Sayangnya, ketika variabel mengambil nilai lebih dari nol dan 1, waktu proses algoritma menjadi jauh lebih lama. Para peneliti telah lama bertanya-tanya apakah mereka bisa mendekati kondisi ideal yang sepele ini. Kemajuan berjalan lambat, dengan catatan ditetapkan pada tahun 1980an dan hanya bertahap perbaikan dibuat sejak itu.

Tetapi baru-baru ini kerja by Victor Reis, saat ini di Institute for Advanced Study, dan Thomas Rothvoss, di Universitas Washington, telah mencapai lompatan runtime terbesar dalam beberapa dekade. Dengan menggabungkan alat geometris untuk membatasi solusi yang mungkin, mereka menciptakan algoritma baru yang lebih cepat untuk menyelesaikan ILP dalam waktu yang hampir bersamaan dengan kasus biner sepele. Hasilnya mendapat penghargaan makalah terbaik pada tahun 2023 Dasar-dasar Ilmu Komputer konferensi.

“Algoritma baru ini sangat menarik,” katanya Noah Stephens-Davidowitz, seorang ahli matematika dan ilmuwan komputer di Cornell University. “Ini merupakan peningkatan [besar] pertama pada pemecah masalah ILP dalam hampir 40 tahun.”

ILP bekerja dengan mengubah permasalahan tertentu menjadi sekumpulan persamaan linier yang harus memenuhi beberapa ketidaksetaraan. Persamaan spesifik didasarkan pada rincian permasalahan awal. Meskipun detailnya mungkin berbeda, susunan dasar masalah ILP tetap sama, sehingga memberikan peneliti satu cara untuk mengatasi banyak masalah.

Bukan berarti ini pekerjaan mudah. Baru pada tahun 1983 ahli matematika itu Hendrik Lenstra terbukti bahwa masalah umum bahkan dapat dipecahkan, dengan menyediakan algoritma pertama yang dapat menyelesaikannya. Lenstra memikirkan ILP secara geometris. Pertama, ia mengubah pertidaksamaan di jantung ILP menjadi bentuk cembung, seperti poligon beraturan. Bentuk ini mewakili kendala dari masing-masing masalah yang Anda selesaikan, baik itu produksi sofa atau penjadwalan penerbangan, sehingga interior bentuk tersebut sesuai dengan semua nilai yang mungkin dapat menyelesaikan ketidaksetaraan, dan juga masalahnya. Lenstra menyebut bentuk ini sebagai badan cembung. Dimensi soal mempengaruhi dimensi bentuk ini: Dengan dua variabel maka berbentuk poligon datar; dalam tiga dimensi itu adalah a Padat platonis, Dan sebagainya.

Lenstra selanjutnya membayangkan semua bilangan bulat sebagai himpunan titik-titik grid tak terhingga, yang dalam matematika dikenal sebagai kisi. Versi dua dimensi terlihat seperti lautan titik, dan dalam versi tiga dimensi terlihat seperti titik sambungan balok baja pada sebuah bangunan. Dimensi kisi juga bergantung pada dimensi permasalahan yang diberikan.

Untuk menyelesaikan masalah ILP tertentu, Lenstra menunjukkan bahwa Anda cukup mencari di mana solusi yang mungkin memenuhi himpunan bilangan bulat: di perpotongan benda cembung dan kisi. Dan dia menemukan sebuah algoritme yang dapat menelusuri ruang ini secara mendalam — namun agar efektif, terkadang algoritme tersebut harus memecah masalah menjadi beberapa bagian dengan dimensi yang lebih kecil, sehingga menambahkan banyak langkah pada waktu proses.

Pada tahun-tahun berikutnya, beberapa peneliti mengeksplorasi bagaimana membuat algoritma ini berjalan lebih cepat. Pada tahun 1988, Ravi Kannan dan László Lovász memperkenalkan konsep yang disebut radius cakupan, dipinjam dari studi tentang kode koreksi kesalahan, untuk membantu badan cembung dan kisi berpotongan dengan lebih efisien. Secara kasar, radius penutup memastikan bahwa benda cembung selalu berisi setidaknya satu titik bilangan bulat, di mana pun Anda meletakkannya pada kisi. Akibatnya, ukuran radius cakupan juga menentukan seberapa efisien Anda dapat menyelesaikan masalah ILP.

Jadi semuanya bermuara pada menentukan ukuran radius cakupan yang ideal. Sayangnya, hal ini terbukti menjadi masalah yang sulit, dan hal terbaik yang dapat dilakukan Kannan dan Lovász adalah mempersempit kemungkinan nilai dengan mencari batas atas dan bawah. Mereka menunjukkan bahwa batas atas – ukuran maksimum radius cakupan – ditingkatkan secara linier dengan dimensi. Ini cukup cepat, namun tidak cukup untuk mempercepat waktu proses ILP secara signifikan. Selama 30 tahun berikutnya, peneliti lain hanya bisa melakukan sedikit lebih baik.

Apa yang pada akhirnya membantu Reis dan Rothvoss menerobos adalah hasil matematika yang tidak terkait yang hanya berfokus pada kisi. Pada tahun 2016, Oded Regev dan Stephens-Davidowitz menunjukkan, sebenarnya, berapa banyak titik kisi yang dapat ditampung dalam bentuk tertentu. Reis dan Rothvoss menerapkan ini pada bentuk lain, yang memungkinkan mereka memperkirakan dengan lebih baik jumlah titik kisi yang terdapat dalam radius cakupan ILP, sehingga menurunkan batas atas. “Terobosan terbaru datang dengan kesadaran bahwa Anda sebenarnya bisa membuat bentuk lain,” kata Regev.

Batas atas baru yang diperketat ini merupakan kemajuan besar, memungkinkan Reis dan Rothvoss mencapai percepatan dramatis dari keseluruhan algoritma ILP. Pekerjaan mereka membawa runtime ke (log n)^O(n), Di mana n adalah jumlah variabel dan O (n)berarti skalanya linear dengan n. (Ekspresi ini dianggap “hampir” sama dengan waktu proses permasalahan biner.)

“Ini adalah kemenangan di persimpangan antara matematika, ilmu komputer, dan geometri,” katanya Daniel Dadush dari lembaga penelitian nasional CWI di Belanda, yang membantu merintis algoritma yang digunakan Reis dan Rothvoss untuk mengukur runtime ILP.

Untuk saat ini, algoritma baru tersebut belum benar-benar digunakan untuk menyelesaikan masalah logistik apa pun, karena akan memerlukan terlalu banyak upaya untuk memperbarui program saat ini agar dapat memanfaatkannya. Namun bagi Rothvoss, hal itu tidak penting. “Ini tentang pemahaman teoretis terhadap suatu masalah yang memiliki penerapan mendasar,” ujarnya.

Mengenai apakah efisiensi komputasi ILP dapat ditingkatkan lebih lanjut, para peneliti masih berharap bahwa mereka akan terus mendekati waktu proses yang ideal – namun tidak dalam waktu dekat. “Hal ini memerlukan ide baru yang fundamental,” kata Vempala.