B$^3$-PWL: Branch-and-Bound Terbatch GPU untuk Optimasi Piecewise-Linear dengan Kendala SOS2

Kerangka branch-and-bound terbatch berbasis GPU yang menyelesaikan relaksasi LP secara bersamaan dengan metode primal-dual orde pertama, mencapai percepatan geometric-mean 9,25x dibandingkan NVIDIA cuOpt pada tolok ukur PWL-MIP.

Yilin Guan; Shuqing Luo; Pingzhi Li; Tianlong Chen; Kaidi Xu· 2026· DOI 10.48550/arXiv.2608.28988

Masalah inti

Masalah optimasi piecewise-linear (PWL) muncul dalam banyak aplikasi pemrograman mixed-integer (MIP), termasuk optimasi portofolio, penjadwalan tenaga kerja, dan alokasi sumber daya. Menyelesaikan masalah ini hingga optimalitas global tetap mahal secara komputasi karena branch-and-bound berulang kali menyelesaikan submasalah relaksasi LP. Solver yang ada sebagian besar berbasis CPU, sehingga skalabilitas GPU modern kurang dimanfaatkan. Pendekatan branch-and-bound yang dipercepat GPU sebelumnya menargetkan jaringan neural, yang tidak cocok untuk optimasi PWL umum, atau hanya mempercepat subrutin tambahan seperti heuristik strong branching dalam solver MIP berbasis CPU. Penelitian ini menjembatani celah tersebut dengan mengusulkan B^{3} -PWL, kerangka branch-and-bound terbatch berbasis GPU untuk optimasi piecewise-linear dengan kendala Special Ordered Set tipe 2 (SOS2). Gagasan utamanya adalah menyelesaikan sekumpulan submasalah relaksasi LP secara bersamaan di GPU menggunakan solver primal-dual orde pertama, dimungkinkan oleh kernel matriks sparse block-tiled terbatch khusus. Untuk melengkapi komputasi batas, penulis memperkenalkan modul pencarian kelayakan terpadu yang menggabungkan

Inovasi

Penulis mengevaluasi B^{3} -PWL pada tolok ukur 43 instans PWL-MIP. Metode ini mencapai percepatan geometric-mean 9,25x dibandingkan NVIDIA cuOpt sekaligus mencapai incumbent layak berkualitas tinggi pada setiap instans yang diuji. Pada tolok ukur valve-point unit-commitment publik, B^{3} -PWL lebih unggul dari NVIDIA cuOpt dan solver CPU sumber terbuka SCIP dan HiGHS. Hasil ini menunjukkan potensi metode LP orde pertama sebagai mesin utama branch-and-bound yang dipercepat GPU. Percepatan ini disebabkan oleh penyelesaian relaksasi LP secara bersamaan di GPU dan efektivitas modul pencarian kelayakan terpadu dalam menemukan incumbent layak dengan cepat, yang meningkatkan efisiensi pemangkasan.

Masalah optimasi piecewise-linear (PWL) muncul dalam banyak aplikasi pemrograman mixed-integer (MIP), termasuk optimasi portofolio, penjadwalan tenaga kerja, dan alokasi sumber daya. Menyelesaikan masalah ini hingga optimalitas global tetap mahal secara komputasi karena branch-and-bound berulang kali menyelesaikan submasalah relaksasi LP. Solver yang ada sebagian besar berbasis CPU, sehingga skalabilitas GPU modern kurang dimanfaatkan. Pendekatan branch-and-bound yang dipercepat GPU sebelumnya menargetkan jaringan neural, yang tidak cocok untuk optimasi PWL umum, atau hanya mempercepat subrutin tambahan seperti heuristik strong branching dalam solver MIP berbasis CPU. Penelitian ini menjembatani celah tersebut dengan mengusulkan B^{3} -PWL, kerangka branch-and-bound terbatch berbasis GPU untuk optimasi piecewise-linear dengan kendala Special Ordered Set tipe 2 (SOS2). Gagasan utamanya adalah menyelesaikan sekumpulan submasalah relaksasi LP secara bersamaan di GPU menggunakan solver primal-dual orde pertama, dimungkinkan oleh kernel matriks sparse block-tiled terbatch khusus. Untuk melengkapi komputasi batas, penulis memperkenalkan modul pencarian kelayakan terpadu yang menggabungkan heuristik primal perbaikan SOS2 dengan feasibility pump terbatch untuk memperoleh incumbent layak dengan cepat dan meningkatkan efisiensi pemangkasan.

B^{3} -PWL adalah kerangka branch-and-bound terbatch berbasis GPU yang dirancang untuk optimasi PWL dengan kendala SOS2. Arsitekturnya terdiri dari tiga komponen utama: (1) solver relaksasi LP terbatch, (2) modul pencarian kelayakan terpadu, dan (3) lapisan orkestrasi branch-and-bound yang mengelola pohon pencarian di GPU.

Mengapa penting

Hasil menunjukkan bahwa branch-and-bound terbatch berbasis GPU dengan metode LP orde pertama dapat secara signifikan mempercepat optimasi PWL dengan kendala SOS2. Percepatan geometric-mean 9,25x dibandingkan NVIDIA cuOpt patut dicatat karena cuOpt adalah solver yang dipercepat GPU mutakhir. Pendekatan ini juga lebih unggul dari solver CPU mapan SCIP dan HiGHS pada tolok ukur valve-point unit-commitment, menunjukkan bahwa manfaatnya melampaui satu kelas masalah. Inovasi utamanya adalah penggunaan solver primal-dual orde pertama untuk relaksasi LP, yang menghindari sifat sekuensial simplex dan aljabar linear mahal dari metode interior-point. Hal ini memungkinkan penyelesaian banyak submasalah LP secara paralel di GPU. Kernel matriks sparse block-tiled terbatch sangat penting untuk efisiensi, karena menangani struktur sparse formulasi PWL. Modul pencarian kelayakan terpadu mengatasi tantangan menemukan incumbent layak dalam branch-and-bound. Dengan menggabungkan heuristik perbaikan SOS2 dengan feasibility pump terbatch, metode ini dengan cepat memperoleh solusi layak yang dapat digunakan untuk memangkas pohon pencarian. Hal ini sangat penting untuk masalah PWL di mana kendala SOS2 dapat membuat kelayakan menjadi sulit. Batasan meliputi ketergantungan pada metode orde pertama, yang mungkin konvergen lambat untuk masalah berkondisi buruk, dan fokus pada kendala SOS2, yang mungkin tidak mencakup semua formulasi PWL. Penelitian selanjutnya dapat mengeksplorasi perluasan ke jenis disjungsi lain dan pendekatan hibrida yang menggabungkan metode orde pertama dan orde kedua. Secara keseluruhan, B^{3} -PWL merupakan langkah signifikan menuju solver MIP yang sepenuhnya dipercepat GPU untuk optimasi PWL, dengan potensi dampak pada optimasi portofolio, penjadwalan tenaga kerja, dan alokasi sumber daya.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…