Problem gila-gilaan itu terpecahkan

SUATU kali, Anda mendapat tugas mengunjungi empat kota dengan pesawat terbang carteran. Anda berangkat dari Jakarta. Kota-kota yang harus Anda kunjungi, katakanlah, Surabaya, Denpasar, Ujungpandang, serta Pontianak. Jika Anda mendapat instruksi untuk menempuh jalur terpendek, rute mana yang harus Anda lewati ? Kening Anda harus berkerut-kerut lebih dahulu, sebelum jawaban yang pasti bisa ketemu. Syukur, kalau Anda hafal di luar kepala jarak antara satu dan lain kota. Kalau tidak, Anda harus mencari jawaban di buku panduan wisata atau mengukur skala jarak di peta. Itu baru langkah pertama. Selanjutnya, Anda mesti menyusun beberapa alternatif lintasan dan memilih jalur yang paling hemat bahan bakar dan murah. Jika Anda berhasil menemukan jawaban yang tepat dalam waktu singkat, Anda termasuk kategori manusia cerdas. Betapa tidak, untuk mengunjungi 4 kota itu ada 12 alternatif lintasan. Dan semua alternatif itu tentu harus dijajaki satu per satu dengan menjumlahkan panjang lintasannya dan membandingkan satu dengan yang lain. Problem mencari lintasan semacam itu akan lebih memusingkan jika kota yang harus disinggahi makin banyak. Ambil contoh, umpamanya, trip itu ditambah dengan Medan. Alternatif lintasan pada enam kota itu, termasuk Jakarta, jumlahnya menjadi 60. Jika ditambah Padang, misalnya, alternatifnya mencapai 360 lintasan. Kalau 16 kota? Jalur yang tersedia mencapai lebih dari 653 milyar alternatif. Jangan tanya jumlah alternatif lintasan dari 50 kota, sampai ubanan pun jawabannya tak akan lengkap. Konon, problem matematis seperti itu telah ramai diperdebatkan sejak dua abad silam. Selama ini, "teka-teki" tersebut tak pernah memperoleh jawaban tuntas. Menghitung jumlah kombinasinya pun sudah pusing, apalagi kalau harus menentukan, misalnya, lintasan yang terpendek atau terjauh. Kasus pelik, seperti mencari lintasan terpendek pada trip ke sejumlah kota, adalah sebuah contoh kasus, dari gugus problem sejenis, yang oleh para pakar matematika disebut (nonpolymonial)-complete problem. Kasus-kasus NP-complete problem ini mempunyai ciri yang khas: sebuah problem matematik yang jika variabelnya bertambah sedikit saja akan menyebabkan pertambahan waktu komputer yang sangat besar untuk memecahkannya. Pertambahan waktu yang berlipat-lipat itu tak lain disebabkan tidak tersedianya kunci praktis untuk menerobos inti persoalan. Namun, problem tua itu agaknya kini mulai terkuak. Dr. Anang Zaini Gani, 48 tahun, matematikawan ITB, mengemukakan sebuah teori yang disebut "teori interaksi", sebagai kunci pemecah NP-complete problem. Bahkan kasus-kasus paling rumit dalam gugus itu, yang disebut The ravelling Salesman Problem (TSP), oleh Anang Zaini dikatakan bisa ditembus oleh teori temuannya. "Teori saya ini mampu memecahkan problem TSP sampai jumlah variabel 57," ujar dosen teknik industri ITB itu. TSP memang boleh disebut problem matematik yang gila-gilaan. Sepintas, seperti problem mencari lintasan tadi, persoalan tampak sederhana. Tapi program konvensional pada superkomputer pun bisa dibikin menyerah. Bayangkan, untuk lima buah variabel, superkomputer - dengan kemampuan satu juta operasi per detik hanya memerlukan 0,02 detik untuk memecahkan TSP. Jika peubah bebas itu ditambah menjadi sepuluh, waktu yang diperlukan untuk memecahkannya berlipat hingga 10 menit.Namun, Jika variabel itu digandakan menJadi 50, "Waktu yang diperlukan sampai bermilyar-milyar tahun," kata Anang Zaini. Maklum, komputer itu harus membandingkan kombinasi-kombinasi yang jumlahnya mencapai sebuah bilangan yang terdiri atas 65 angka! Teori interaksi rekaan Anang Zaini itu menjelang akhir tahun lalu ditampilkan pada seminar Operation Kesearch, sebuah cabang matematik, di St. Louis, Amerika Serikat. Dalam forum yang oleh Zaini disebut "Olimpiade Matematik" itu, tuturnya, teori interaksi membuat para peserta seminar terperanjat. "Sampai sekarang banyak ahli matematika dari pelbagai tempat minta makalah saya," ujar Anang Zaini, doktor teknik industri lulusan Universitas Pandova, Italia, 1972, ini. Oleh para penggemar matematika, rupanya teori Zaini sedang diuji. Anang Zaini mengembangkan teorinya berdasarkan sebuah gagasan unik: sebuah angka tidaklah mutlak adanya. "Nilai suatu elemen dalam sistem itu sesungguhnya relatif, tidak absolut," kata Zaini. Kenisbian nilai elemen sistem itu, kata ayah tiga anak ini, tergantung lingkungannya. Maka, dalam membangun teorinya, Zaini mengaitkan satu elemen dengan elemen lain di sekelilingnya, sehingga memperoleh koeflsien interaksi. Komponen inilah yang memungkinkan ahli desain industri itu memperoleh nilai-nilai nisbi. Dalam memecahkan persoalan TSP, Zaini tak melakukan pendekatan dengan matematika tinggi. "Cukup dengan aritmatika (ilmu hitung) biasa," ujarnya. Elemen TSP biasanya disusun dalam matriks. Ukuran matriks itu tentu tergantung variabel yang ada. Jika peubah bebasnya 50, matriksnya pun berukuran 50 x 50. Anggota matriks kemudian ditransformasikan dengan mengalikannya terhadap koefisien interaksi. Indeks koefisien itu diperoleh dari pengkuadratan anggota matriks terhadap besaran tertentu. Tahap berikutnya, setelah transformasi, adalah penggarapan terhadap nilai-nilai nisbi dalam tubuh matriks itu. Dan yang paling penting pada metode interaksi itu, "Hasil yang diperoleh dijamin eksak," kata Zaini. Teori baru ini agaknya sulit diterima seketika. Prof. Dr. Achmad Arifin, ahli aljabar linier dari ITB, menyatakan salut terhadap kegigihan Zaini, tapi tentang teori interaksi ia mengaku, "Saya belum paham betul." Lalu tambahnya, "TSP di luar keahlian saya." Tak berarti teori ini tidak diterima di almamaternya sendiri. Bekas Kepala Laboratorium Komputasi Teknik Industri ITB, Ir. Isa Setiasyah, M.Sc., mengakui kesahihan teori interaksi. Aplikasinya juga mudah. "Waktu komputasinya lebih cepat, kualitas jawabannya optimal dan eksak," tuturnya. Teori interaksi mampu pula memecahkan problem optimasi suatu fungsi multivariabel. Umpamanya, untuk menentukan jalur sambungan kabel listrik yang pallng murah atau distribusi barang produksi yang efisien. Ahli-ahli lain mendekati kasus itu dengan linear programming (LP). Setelah Perang Dunia II, LP berkembang sebagai perangkat lunak yang efektif untuk pengambilan keputusan yang berkenaan dengan optimasi. Salah satu metode yang di saat akhir PD II adalah metode simplex temuan matematikawan George B. Dantig, dari Universitas Stanford, Amerika. Setelah hampir empat dasawarsa tak terdengar munculnya teori baru, Kachian, matematikawan Rusia, membuat metode baru yang disebut Ellipsoid Algonthm, di tahun 1979. Namun, Kachian tak sempat lama termasyhur. Empat tahun silam Narendra K. Kamarkar, kini 28 tahun, menemukan terobosan baru dalam LP. Pada teorinya yang disebut projective geometry, Kamarkar juga membuat sejumlah transformasi pada matriks yang dibangun dari deret LP-nya. Hasilnya cukup mengejutkan: perhitungan Kamarkar ternyata 50 sampai 100 kali lebih cepat dibanding cara simplex. Konon, teori pemuda keturunan India warga AS ini mampu melayani sampai 50 variabel. Kamarkar, berkat penemuannya ini, telah 3 disebut-sebut sebagai calon penerima hadiah Nobel. Namun, menurut Isa Setiasyah, teori interaksi lebih baik ketimbang projective geometry. "Teori interaksi lebih cepat, lebih mudah dioperasikan, dan lebih mudah diterima konsep keilmuannya," ujarnya. Sayangnya, teori ini belum diuji secara luas. Bulan Mei dan Juli nanti, Anang Zaini akan mempromosikan lagi temuannya di Washington dan Paris. Di dalam negeri sendiri, sambutan terhadap teori itu masih terasa sepi. Padahal, Anang merasa perlu pengujian-pengujian itu dari rekan senegara. "Bukannya saya menantang," ujarnya, "tapi saya ingin menumbuhkan kegairahan orang terhadap TSP." Putut Tri Husodo (Jakarta) dan Agung Firmansyah (Bandung)