Lompat ke konten

Matematika

PDFP, algoritma berbasis GPU, dirancang percepat pencarian solusi awal masalah MILP

Redaksi ARSTEMA · · 3 menit baca

Ruofeng Liu, Haihao Lu, dan Rahul Mazumder mengunggah pracetak arXiv tentang PDFP, metode feasibility pump di GPU untuk menemukan solusi awal program linear bilangan bulat campuran lebih cepat. Hasilnya masih tahap awal.

Tiga peneliti, Ruofeng Liu, Haihao Lu, dan Rahul Mazumder, mengunggah makalah pracetak di arXiv dengan tanggal pengajuan 3 November 2026. Makalah itu memperkenalkan PDFP, algoritma feasibility pump yang berjalan di GPU untuk mencari solusi awal program linear bilangan bulat campuran (mixed-integer linear programming, MILP). Menurut BioScience, para penelitinya berasal dari Massachusetts Institute of Technology (MIT).

Apa itu MILP dan feasibility pump

MILP adalah kerangka matematika untuk persoalan yang sebagian variabelnya harus bilangan bulat. BioScience menyebut kerangka ini mendasari penjadwalan penerbangan, perencanaan jaringan listrik, dan pengelolaan rantai pasok. Mencari satu solusi yang valid pada persoalan seperti itu sering sulit, sehingga solver memakai heuristik, yaitu cara pintas yang tidak menjamin hasil optimal.

Feasibility pump (FP) adalah salah satu heuristik primal yang paling banyak dipakai untuk MILP. Menurut abstrak makalah, FP bergantian dalam dua langkah. Langkah pertama membulatkan titik yang layak pada relaksasi LP, yaitu versi persoalan tanpa syarat bilangan bulat. Langkah kedua memproyeksikan titik bulat itu kembali ke daerah layak relaksasi tersebut.

Yang diusulkan PDFP

Pompa generasi terbaru menghitung proyeksi dengan PDHG (primal-dual hybrid gradient), metode yang skalabel di GPU. Namun, menurut para penulis, mereka merumuskan proyeksi itu sebagai program linear yang memerlukan variabel dan kendala tambahan untuk bilangan bulat umum. Setelah proyeksi berjalan di GPU, tahap pembulatan constraint-propagation rounding (CPR) pun memakan porsi besar pada tiap iterasi.

PDFP menjawab dua sisi itu:

  • Proyeksi: PDFP adalah metode orde pertama khusus yang menyelesaikan masalah proyeksi pump secara langsung, tanpa variabel atau kendala primal tambahan. Penulis membuktikan metode ini mempertahankan laju linear terakselerasi dari Halpern PDHG yang di-restart.
  • Pembulatan: Prosedur baru disebut lebih efisien daripada CPR dan, dengan asumsi tertentu, tetap menghasilkan pembulatan CPR. Nilai bulatnya dipilih berdasarkan pelanggaran kendala, sehingga dapat menghasilkan pembulatan layak pada kasus yang tidak terselesaikan oleh pembulatan ke bilangan terdekat. Menurut BioScience, prosedur ini mengelompokkan variabel yang nilai relaksasinya sudah bulat dan memprosesnya sekaligus.
  • Dua lintasan: Pump menjalankan dua lintasan independen secara bersamaan pada satu GPU lewat sinkronisasi CPU-GPU. Cara ini memanfaatkan variasi panjang lintasan, sehingga pump rata-rata berhenti lebih cepat.

Hasil uji dan batasannya

Abstrak di arXiv hanya menyebut eksperimen pada instans MIPLIB 2017 menunjukkan hasil awal yang menjanjikan, berupa percepatan penemuan solusi inkumben pertama, yakni solusi layak pertama yang ditemukan. Abstrak tidak memuat angka perbandingan.

Angka rinci datang dari BioScience. Media itu melaporkan evaluasi pada 142 instans besar dari pustaka MIPLIB 2017. Dengan lintasan bersamaan, algoritma ini menyelesaikan lebih banyak instans dan mencapai rata-rata geometrik waktu eksekusi yang bergeser 1,18 kali lebih cepat daripada implementasi acuan. BioScience juga menulis bahwa kecepatannya 1,72 kali lebih tinggi daripada alternatif komersial seperti NVIDIA cuOpt. Angka-angka ini belum tercantum di abstrak makalah, dan makalahnya sendiri masih berstatus pracetak.

Ada selisih kecil soal tanggal. Halaman arXiv mencatat pengajuan versi pertama pada 3 November 2026, sedangkan BioScience menulis studi itu diunggah pada 2 November 2026. Kode PDFP, menurut penulis, tersedia untuk publik di GitHub.

Apa artinya bagi pembaca

Bagi teknisi dan mahasiswa yang bersentuhan dengan penjadwalan produksi, perencanaan jaringan listrik, atau logistik, makalah ini menunjukkan arah riset: langkah awal pencarian solusi MILP dipindahkan ke GPU dan dirancang agar tidak membebani perangkat keras dengan variabel tambahan. Karena hasilnya masih awal dan berupa pracetak, klaim kecepatannya perlu diuji lebih lanjut dan belum dapat dianggap berlaku untuk semua jenis persoalan.

Sumber

  1. PDFP: GPU-Accelerated Feasibility Pump via PDHGarXiv · 3 November 2026
  2. New GPU Algorithm Solves Complex Math Optimization Puzzles FasterBioScience · 3 November 2026

Pelajari lebih dalam di ARSTEMA Academy