Versi aslinya dari cerita ini muncul di Majalah Kuanta.
Pada tahun 1939, setelah datang terlambat ke mata kuliah statistika di UC Berkeley, George Dantzig—seorang mahasiswa pascasarjana tahun pertama—menyalin dua soal dari papan tulis, mengira itu adalah pekerjaan rumah. Dia mendapati pekerjaan rumahnya “lebih sulit untuk dikerjakan daripada biasanya,” dia kemudian menceritakannya, dan meminta maaf kepada profesor karena mengambil beberapa hari ekstra untuk menyelesaikannya. Beberapa minggu kemudian, profesornya memberi tahu dia bahwa dia telah memecahkan dua permasalahan terbuka yang terkenal dalam statistik. Karya Dantzig menjadi dasar disertasi doktoralnya dan, beberapa dekade kemudian, menjadi inspirasi untuk film tersebut Perburuan Niat Baik.
Dantzig menerima gelar doktornya pada tahun 1946, tepat setelah Perang Dunia II, dan ia segera menjadi penasihat matematika di Angkatan Udara AS yang baru dibentuk. Seperti semua perang modern, hasil Perang Dunia II bergantung pada alokasi sumber daya yang terbatas secara bijaksana. Namun tidak seperti perang-perang sebelumnya, konflik ini benar-benar berskala global, dan sebagian besar dimenangkan melalui kekuatan industri. AS bisa saja memproduksi lebih banyak tank, kapal induk, dan pembom dibandingkan musuh-musuhnya. Mengetahui hal ini, pihak militer sangat tertarik pada masalah optimalisasi—yaitu, bagaimana mengalokasikan sumber daya yang terbatas secara strategis dalam situasi yang dapat melibatkan ratusan atau ribuan variabel.
Angkatan Udara menugaskan Dantzig untuk mencari cara baru untuk memecahkan masalah optimasi seperti ini. Sebagai tanggapan, ia menemukan metode simpleks, sebuah algoritma yang memanfaatkan beberapa teknik matematika yang ia kembangkan saat memecahkan masalah papan tulisnya hampir satu dekade sebelumnya.
Hampir 80 tahun kemudian, metode simpleks masih menjadi salah satu alat yang paling banyak digunakan ketika keputusan logistik atau rantai pasokan perlu diambil dalam kondisi yang kompleks. Ini efisien dan berhasil. “Ia selalu berjalan cepat, dan tak seorang pun pernah melihatnya tidak cepat,” katanya Sophie Huiberts dari Pusat Penelitian Ilmiah Nasional Perancis (CNRS).
Pada saat yang sama, ada sifat aneh yang telah lama membayangi metode Dantzig. Pada tahun 1972, ahli matematika membuktikan bahwa waktu yang dibutuhkan untuk menyelesaikan suatu tugas dapat meningkat secara eksponensial seiring dengan banyaknya kendala. Jadi, tidak peduli seberapa cepat metode ini dipraktikkan, analisis teoritis secara konsisten menawarkan skenario terburuk yang menyiratkan bahwa hal ini bisa memakan waktu lebih lama secara eksponensial. Untuk metode simpleks, “alat tradisional kami untuk mempelajari algoritma tidak berfungsi,” kata Huiberts.
Eleon Bach adalah salah satu penulis hasil baru ini.
Namun dalam cara yang baru kertas yang akan dipresentasikan pada bulan Desember di konferensi Foundations of Computer Science, Huiberts dan Eleon Bachseorang mahasiswa doktoral di Technical University of Munich, tampaknya telah mengatasi masalah ini. Mereka telah membuat algoritme menjadi lebih cepat, dan juga memberikan alasan teoretis mengapa runtime eksponensial yang telah lama dikhawatirkan tidak terwujud dalam praktik. Pekerjaan yang dibangun di atas a hasil penting dari tahun 2001 oleh Daniel Spielman Dan Shang-Hua Tengadalah “brilian [and] cantik,” menurut Teng.
“Ini adalah karya teknis yang sangat mengesankan, yang secara ahli menggabungkan banyak ide yang dikembangkan dalam penelitian sebelumnya, [while adding] beberapa ide teknis baru yang benar-benar bagus,” katanya Laszló Véghseorang ahli matematika di Universitas Bonn yang tidak terlibat dalam upaya ini.
Geometri Optimal
Metode simpleks dirancang untuk mengatasi sekelompok masalah seperti ini: Misalkan sebuah perusahaan furnitur membuat lemari, tempat tidur, dan kursi. Secara kebetulan, setiap lemari tiga kali lebih menguntungkan dibandingkan setiap kursi, sementara setiap tempat tidur dua kali lebih menguntungkan. Jika kita ingin menulis ini sebagai ekspresi, gunakan A, BDan C untuk mewakili jumlah furnitur yang diproduksi, kita katakan bahwa total keuntungan sebanding dengan 3A + 2B + C.
Untuk memaksimalkan keuntungan, berapa banyak setiap barang yang harus diproduksi perusahaan? Jawabannya tergantung pada kendala yang dihadapi. Katakanlah sebuah perusahaan dapat memproduksi paling banyak 50 item per bulan, jadi A + B + C kurang dari atau sama dengan 50. Lemari lebih sulit dibuat—tidak lebih dari 20 yang bisa diproduksi—jadi A kurang dari atau sama dengan 20. Kursi membutuhkan kayu khusus, dan persediaannya terbatas C harus kurang dari 24.
Metode simpleks mengubah situasi seperti ini—walaupun seringkali melibatkan lebih banyak variabel—menjadi masalah geometri. Bayangkan membuat grafik batasan kita A, B Dan C dalam tiga dimensi. Jika A kurang dari atau sama dengan 20, kita dapat membayangkan sebuah bidang pada grafik tiga dimensi yang tegak lurus terhadap A sumbu, memotongnya di A = 20. Kita akan menetapkan bahwa solusi kita harus terletak pada atau di bawah bidang tersebut. Demikian pula, kita dapat membuat batasan yang terkait dengan batasan lainnya. Jika digabungkan, batas-batas ini dapat membagi ruang menjadi bentuk tiga dimensi kompleks yang disebut polihedron.
Sophie Huiberts memegang model geometris dari masalah optimasi.
Eksekusi algoritma simpleks dari awal sampai akhir, direpresentasikan secara geometris, melibatkan pencarian jalur—dari, katakanlah, titik terbawah ke titik paling atas—yang melibatkan langkah paling sedikit atau, setara, menelusuri sisi paling sedikit. Jumlah langkah, pada gilirannya, berkaitan dengan waktu proses (atau “kompleksitas”) algoritma, dengan tujuan untuk menyelesaikan masalah dalam jumlah langkah minimum. Mengidentifikasi rute terpendek dari bawah ke atas dalam gambar ini sama dengan mencari tahu bentuk paling efisien yang dapat diambil oleh algoritma tersebut.
Menemukan jalur yang cepat dan langsung mungkin mudah, jika bukan karena dua hal: Pertama, bentuk aslinya mungkin jauh lebih rumit daripada contoh kita, dengan lebih banyak sisi, simpul, dan tepi. Dan kedua, tidak ada peta yang bisa memandu Anda. Anda tidak dapat melihat seluruh objek yang Anda coba navigasikan. Sebaliknya, Anda memulai dari satu titik dan menentukan pilihan sisi mana yang harus diikuti terlebih dahulu. Anda melakukan hal yang sama pada titik berikutnya, dan seterusnya, tanpa mengetahui secara pasti ke mana sisi yang Anda pilih akan membawa Anda.
Jika Anda sangat kurang beruntung, Anda bisa salah belok di setiap titik dan terjebak di labirin. “Anda bisa berjalan sejauh mungkin dari A ke B,” kata Bach, “karena di setiap sudut ada seseorang yang memberitahu Anda bahwa Anda harus pergi ke arah yang salah.” Situasi seperti itulah yang dapat mengarah pada skenario terburuk yang memerlukan waktu penyelesaian yang sangat lama.
Pada tahun 2001, Spielman dan Teng membuktikan bahwa keacakan sekecil apa pun dapat membantu mencegah hal tersebut. Kembali ke contoh sebelumnya—dengan risiko menyederhanakan argumen Spielman dan Teng secara berlebihan—misalkan ada enam pilihan di setiap sudut yang Anda temui. Jika Anda selalu diberitahu arah terburuk yang harus Anda tempuh, Anda akan mendapat masalah. Namun, jika Anda mengandalkan lemparan dadu, Anda akan memiliki peluang lima dari enam untuk menghindari pilihan terburuk, dan bencana dapat dihindari. Memasukkan unsur keacakan dan ketidakpastian ke dalam proses adalah hal yang beralasan, mengingat bahwa di dunia nyata, pengukuran tidak pernah tepat. Spielman dan Teng memperkenalkan keacakan dengan cara yang sama sekali berbeda, namun mereka menunjukkan bahwa waktu berjalan tidak akan pernah lebih buruk daripada jumlah kendala yang dipangkatkan—misalnya, N2—yang merupakan contoh dari apa yang disebut waktu polinomial. Itu jauh lebih baik daripada waktu eksponensial, yang berbentuk, katakanlah, 2*N*.
Shang-Hua Teng.
Daniel Spielman.
Meski begitu, hal ini tidak sepenuhnya menyelesaikan masalah. Nilai waktu polinomialnya masih cukup tinggi, kata Huiberts—nilai tersebut menyertakan suku yang dipangkatkan 30, yang merupakan angka yang cukup besar untuk sebuah eksponen. Jadi, selama dua dekade terakhir, para peneliti telah membuat kemajuan bertahap dalam menurunkan nilai ini.
Dalam makalah baru mereka, Bach dan Huiberts mengandalkan lebih banyak keacakan dalam algoritma mereka untuk menunjukkan bahwa runtime dijamin jauh lebih rendah daripada yang telah ditetapkan sebelumnya. Mereka juga menunjukkan bahwa algoritma berdasarkan pendekatan yang dibuat oleh Spielman dan Teng tidak bisa berjalan lebih cepat dari nilai yang mereka peroleh. Hal ini memberi tahu kita, kata Huiberts, “bahwa kami sepenuhnya memahami [this] model metode simpleks.”
“Ini menandai kemajuan besar dalam pemahaman kita tentang [simplex] algoritma,” kata Heiko Röglinseorang ilmuwan komputer di Universitas Bonn, “menawarkan penjelasan pertama yang benar-benar meyakinkan mengenai efisiensi praktis metode ini.”
Meski begitu, Huiberts tidak melihat ini sebagai akhir dari segalanya. Pendekatan yang dimulai pada tahun 2001 oleh Spielman dan Teng menunjukkan bagaimana waktu proses dapat dikurangi dari waktu eksponensial menjadi waktu polinomial. Langkah logis berikutnya adalah menemukan cara untuk menskalakan secara linear dengan jumlah batasan. “Itu adalah Bintang Utara untuk semua penelitian ini,” katanya. Namun hal ini memerlukan strategi yang benar-benar baru. “Kami tidak mengambil risiko untuk mencapai hal ini dalam waktu dekat.”
Meskipun upaya Bach dan Huiberts secara teoritis menarik bagi rekan-rekan di bidangnya, karya tersebut belum menghasilkan penerapan praktis apa pun. Namun demikian, hal ini mungkin dapat meredakan beberapa kekhawatiran yang mungkin dimiliki orang-orang mengenai ketergantungan pada perangkat lunak yang tersedia saat ini yang didasarkan pada metode simpleks. “Sedangkan eksperimen praktis menunjukkan bahwa permasalahan tersebut selalu diselesaikan dalam waktu polinomial,” ujarnya Aula Julianseorang dosen matematika di Universitas Edinburgh yang merancang perangkat lunak pemrograman linier, Bach dan Huiberts telah memberikan dukungan matematis yang lebih kuat untuk intuisi tersebut. “Oleh karena itu, sekarang lebih mudah untuk meyakinkan mereka yang takut akan kompleksitas eksponensial.”
Cerita asli dicetak ulang dengan izin dari Majalah Kuantasebuah publikasi independen secara editorial dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman masyarakat terhadap sains dengan meliput perkembangan dan tren penelitian di bidang matematika serta ilmu fisika dan kehidupan.
