Editorial ilmu komputer
Optimasi Berbasis Graf: Metaheuristik Keluarga Rao, OR Klasik, dan Formulasi Berbasis SLM pada Knowledge Graph
Masalah inti
Makalah ini mengusulkan **optimasi berbasis graf**, sebuah paradigma di mana variabel keputusan, kendala, dan koefisien tujuan dari masalah optimasi nyata bersumber dari property knowledge graph (KG) melalui kueri Cypher, bukan disediakan sebagai teks bahasa alami bebas atau masukan tabular statis. Penulis memotivasi paradigma ini dengan meninjau sistem optimasi terkini yang digerakkan LLM/SLM -- OptiMUS, Chain-of-Experts, LLMOPT, OPRO, FunSearch, dan Eureka -- yang tidak satu pun mengonsumsi property graph sebagai modalitas masukan utama. Kesenjangan ini memotivasi perlunya pendekatan native graf untuk formulasi masalah optimasi.
Pertanyaan penelitian intinya adalah apakah grounding masalah optimasi pada knowledge graph, alih-alih teks atau tabel, mengubah karakteristik kinerja solver dan kualitas formulasi yang dihasilkan. Penulis menginstansiasi paradigma ini pada basis data open-source **samyama-graph** dan mengevaluasi tujuh masalah nyata domain publik berbasis KG yang mencakup drug repurposing (KG biomedis 245K node), pemilihan lokasi uji klinis (registri uji 7,78M node), pengalihan rute rantai pasok India (graf jalan OSM 5,34M node), alokasi ekuitas layanan kesehatan (KG WH
Inovasi
Evaluasi pada tujuh masalah nyata menghasilkan tiga temuan utama:
**(i) Tidak ada satu varian Rao pun yang mendominasi.** BMWR menang pada masalah diskret-dengan-tradeoff dan high-dim-dengan-kendala-keras, sedangkan Rao-1 menang pada masalah kontinu berdimensi rendah/menengah. Ini secara empiris mendukung pendekatan portofolio untuk pemilihan metaheuristik. Perbedaan kinerja bergantung pada kelas masalah, dan tidak ada satu varian pun yang mencapai kinerja terbaik di seluruh tujuh masalah.
**(ii) OR-tools mendominasi pada sub-masalah kecil yang ramah linear/MILP tetapi tidak dapat mengodekan tujuan non-linear yang muncul di beberapa pengaturan nyata.** CP-SAT dan GLOP sangat efektif ketika masalah dapat dinyatakan sebagai program linear atau mixed-integer linear. Namun, beberapa masalah berbasis graf melibatkan tujuan non-linear (misalnya, metrik ekuitas, fungsi risiko) yang tidak dapat langsung dikodekan di OR-tools tanpa linearisasi, yang dapat menurunkan kualitas solusi.
**(iii) Formulasi berbasis graf memunculkan masalah kualitas data (properti hilang, agregat degenerat) yang secara diam-diam akan tersembunyi oleh optimasi yang diformulasikan murni dari teks.** Ini temuan kr
Mengapa penting
Temuan ini memiliki beberapa implikasi bagi desain sistem optimasi yang mengonsumsi data nyata.
**Pendekatan Portofolio untuk Metaheuristik:** Hasil bahwa tidak ada satu varian Rao pun yang mendominasi mendukung pendekatan portofolio, di mana beberapa metaheuristik dijalankan dan solusi terbaik dipilih. Ini konsisten dengan teorema No Free Lunch, yang menyatakan bahwa tidak ada satu algoritma pun yang terbaik untuk semua masalah. Implikasi praktisnya adalah sistem optimasi harus menyertakan beragam solver dan mekanisme untuk memilih di antara mereka berdasarkan karakteristik masalah.
**Batasan OR Klasik:** Meskipun OR-tools mendominasi pada sub-masalah linear dan ramah MILP, ketidakmampuannya mengodekan tujuan non-linear secara langsung merupakan batasan signifikan untuk masalah nyata. Banyak tujuan nyata (misalnya, ekuitas, risiko, dampak lingkungan) bersifat non-linear, dan linearisasi dapat menimbulkan galat aproksimasi. Ini menyarankan pendekatan hibrida: gunakan OR-tools untuk bagian linear dan metaheuristik untuk bagian non-linear.
**Umpan Balik Kualitas Data:** Kontribusi paling baru adalah pengamatan bahwa formulasi berbasis graf memunculkan masalah kualitas data. Dalam formulasi berbasis teks, LLM mungkin secara diam-diam mengimputasi nilai yang hilang atau mengabaikan agregat degenerat, menghasilkan solusi yang tidak robust. Grounding graf membuat masalah ini eksplisit, memungkinkan pembersihan dan validasi data sebelum optimasi. Ini memiliki implikasi bagi kepercayaan sistem optimasi yang digerakkan AI.
**Perbandingan dengan Sistem Berbasis LLM/SLM:** Sistem yang ditinjau (OptiMUS, Chain-of-Experts, LLMOPT, OPRO, FunSearch, Eureka) semuanya menggunakan teks atau kode sebagai modalitas masukan utama. Tidak satu pun mengonsumsi property graph. Paradigma berbasis graf bersifat komplementer: ia dapat digunakan bersama formulasi berbasis LLM/SLM, di mana LLM menghasilkan kueri Cypher alih-alih program matematis secara langsung. Pendekatan hibrida ini dapat menggabungkan fleksibilitas LLM dengan keterikatan data knowledge graph.
**Skalabilitas dan Penerapan Praktis:** Evaluasi pada graf hingga 7,78 juta node menunjukkan skalabilitas. Basis data samyama-graph bersifat open-source, yang memfasilitasi reproduksibilitas dan adopsi. Namun, makalah ini tidak melaporkan runtime atau penggunaan memori, yang penting untuk penerapan praktis. Pekerjaan mendatang harus menyertakan benchmark kinerja yang terperinci.
**Pertimbangan Taksonomi:** Makalah ini menyentuh beberapa domain: arsitektur (desain sistem untuk optimasi berbasis graf), keamanan siber (tidak secara langsung, tetapi masalah kualitas data dapat memiliki implikasi keamanan), jaringan (rantai pasok dan perutean evakuasi), dan kriptografi (tidak secara langsung). Kesesuaian taksonomi utama adalah **Arsitektur** untuk desain sistem dan **Jaringan** untuk aplikasi perutean dan rantai pasok.
**Arah Mendatang:** Penulis menyarankan bahwa optimasi berbasis graf dapat diperluas ke graf dinamis, di mana graf berubah seiring waktu, dan ke optimasi multi-tujuan, di mana tradeoff antar tujuan dimodelkan secara eksplisit. Integrasi dengan SLM untuk pembuatan kueri adalah arah menjanjikan lainnya.
Siapa yang sebaiknya membaca
Membuka konten member…