b-ACO: Borůvka-based Ant Colony
Optimization for DCMST

Paper ini menyajikan desain dua pendekatan Ant Colony Optimization (ACO) beserta varian-varian perbaikannya untuk masalah degree-constrained minimum spanning tree (d-MST). Pendekatan pertama, yang disebut p-ACO, menggunakan vertex dari graf konstruksi sebagai komponen solusi dan terinspirasi dari algoritma Prim. Pendekatan kedua, k-ACO, menggunakan edge graf sebagai komponen solusi dan terinspirasi dari algoritma Kruskal. Hasil empiris menunjukkan bahwa k-ACO berkinerja lebih baik daripada p-ACO. Enhanced k-ACO secara rata-rata mengungguli F-EA, PSS, SA, B&B, dan ant-based algorithm pada sebagian besar instance.

Bab ini menjelaskan algoritma ACO baru untuk masalah degree-constrained minimum spanning tree (d-MST). Penggunaan tree coding seperti Prüfer code atau Blob code memudahkan ACO yang diusulkan untuk menyelesaikan varian lain dari masalah d-MST dengan batasan batas bawah dan atas pada setiap vertex. Pendekatan ini memungkinkan representasi solusi yang lebih efisien dan memfasilitasi operasi pencarian dalam ruang solusi yang kompleks.

Paper ini mempertimbangkan masalah degree-constrained k-minimum spanning tree (DCkMST): menemukan subtree biaya minimum dari graf G yang terbentuk dengan setidaknya k vertex dimana derajat setiap vertex ≤ d. Metode iteratif eksak diadaptasi, dan diusulkan algoritma ACO dan VNS untuk d=2 dan d=3. Untuk algoritma VNS, diperkenalkan strategi Q-learning tertanam yang memungkinkan pencarian lokal acak berdasarkan pengalaman solusi sebelumnya.

Paper ini mengusulkan NeuroPrim, kerangka kerja baru untuk menyelesaikan berbagai masalah spanning tree dengan mendefinisikan Markov Decision Process (MDP). Pendekatan ini mengurangi ruang aksi dan keadaan menggunakan algoritma Prim dan melatih model menggunakan REINFORCE. Diterapkan pada tiga masalah sulit: degree-constrained MST (DCMST), minimum routing cost spanning tree (MRCST), dan Steiner tree.

Paper ini mengusulkan teknik baru dengan Modified Ant Colony Optimization Algorithm (MACOA) untuk menentukan minimum cost spanning tree dari graf berbobot tak berarah terhubung dengan iterasi lebih sedikit. Metode probabilistik untuk menemukan rute terbaik melalui graf dikombinasikan dengan algoritma Prim dan Kruskal yang sudah terkenal, menghasilkan pendekatan yang lebih efisien untuk masalah MST skala besar.

Paper ini menyajikan dua pendekatan untuk masalah min-degree constrained MST (md_MST): teknik metaheuristik hybrid hABC (menggabungkan artificial bee colony dengan local search) dan Iterated Local Search (ILS). Eksperimen ekstensif pada 105 benchmark instances menunjukkan dominasi terhadap state-of-the-art: hABC menemukan 41 nilai terbaik baru, ILS menemukan 28 nilai terbaik baru.

Dalam paper ini, dibahas dua formulasi untuk Min-degree Constrained Minimum Spanning Tree Problem, yaitu satu berbasis undirected Subtour Elimination Constraints dan satu lagi berbasis Directed Cutset inequalities. Kualitas batas Linear Programming dari kedua formulasi tersebut dianalisis, lalu dikembangkan algoritma Branch-and-cut berdasarkan formulasi yang paling kuat. Hasil eksperimen komputasi menunjukkan bahwa metode ini memberikan kinerja yang baik dibanding pendekatan eksak maupun heuristik lain dalam literatur, baik dari sisi kualitas solusi maupun waktu eksekusi. Paper ini juga menghasilkan beberapa sertifikat optimalitas baru dan batas atas terbaik baru.

Paper ini membahas varian Min-degree Constrained Minimum Spanning Tree Problem (MDCMST) di mana node central dan terminal telah ditentukan sebelumnya. Penulis menunjukkan bahwa masalah optimasi ini bersifat NP-Hard bahkan pada graf lengkap, sedangkan masalah kelayakannya NP-Complete. Penelitian ini juga mengembangkan beberapa formulasi integer linear programming berdasarkan model MST klasik serta membandingkan kualitas batas bawah dari relaksasi linear yang dihasilkan. Selain itu, tiga pendekatan Lagrangian heuristic diusulkan dan diuji secara komputasional untuk mengevaluasi performa formulasi dan heuristik.

Paper ini membahas model berbasis node untuk masalah Steiner tree dengan biaya edge yang seragam. Pendekatan "thinning out" yang diusulkan bertujuan mengurangi kompleksitas masalah dengan fokus pada representasi node daripada edge. Metode ini relevan untuk berbagai aplikasi dalam desain jaringan dan optimisasi graf, termasuk sebagai fondasi untuk memahami masalah spanning tree dengan degree constraint yang lebih kompleks.

Heuristik berbasis Lagrangian diusulkan untuk masalah degree constrained minimum spanning tree. Heuristik menggunakan informasi Lagrangian relaxation untuk memandu konstruksi solusi feasible. Mekanisme pencegahan infeasibility look ahead memungkinkan penyelesaian instance dimana beberapa vertex dibatasi memiliki derajat 1 atau 2. Eksperimen komputasional menunjukkan bahwa heuristik yang diusulkan kompetitif dengan heuristik dan metaheuristik terbaik dalam literatur.

Paper ini menyajikan algoritma Branch-and-Cut-and-Price untuk Degree Constrained Minimum Spanning Tree Problem (DCMST). Pendekatan ini menggabungkan teknik branch-and-cut dengan column generation untuk menangani formulasi integer programming yang kompleks. Metode eksak ini mampu menyelesaikan instance graf yang cukup besar serta memberikan solusi optimal dengan sertifikat optimalitas.

Tujuan dari Multiperiod Degree Constrained Minimum Spanning Tree (MPDCMST) adalah menentukan spanning tree dengan bobot minimum yang memenuhi kriteria instalasi simpul (vertex installation) pada setiap periode serta mempertahankan persyaratan derajat (degree requirement) pada setiap simpul. Masalah ini muncul sebagai permasalahan koneksi jaringan. Persyaratan derajat menunjukkan tingkat keandalan (reliability) dari setiap simpul, sedangkan persyaratan koneksi/instalasi simpul menunjukkan simpul prioritas yang harus dimasukkan ke dalam jaringan dalam jangka waktu tertentu. Proses instalasi dibagi ke dalam beberapa fase atau tahap. Hal ini dilakukan karena berbagai pertimbangan seperti cuaca ekstrem, keterbatasan anggaran, dan sebagainya. Dalam penelitian ini, diusulkan dua algoritma untuk menyelesaikan masalah MPDCMST, yaitu menggunakan probabilitas yang dihibridisasi dengan modifikasi algoritma Prim, serta analisis sisi (edge analysis). Algoritma tersebut diimplementasikan pada graf lengkap tak berarah dengan orde 10 hingga 100. Solusi yang diperoleh kemudian dibandingkan dengan beberapa heuristik yang telah ada dalam literatur. Hasil penelitian menunjukkan bahwa algoritma yang diusulkan memiliki kinerja yang lebih baik.

Pada graf terhubung berbobot, masalah shortest total path length spanning tree adalah masalah untuk menemukan spanning tree dengan biaya total terendah dari semua jarak berpasangan antar simpul. Masalah ini juga dikenal sebagai Minimum Routing Cost Spanning Tree (MRCST). Dalam penelitian ini, kami membahas Algoritma Sollin yang Dimodifikasi dan Algoritma Dijkstra yang Dimodifikasi untuk menyelesaikan masalah tersebut. Kedua algoritma ini diimplementasikan pada 300 permasalahan, yaitu graf lengkap dengan orde 10 hingga 100 dengan kenaikan 10, di mana setiap orde terdiri dari 30 permasalahan. Hasil penelitian menunjukkan bahwa kinerja Algoritma Dijkstra yang Dimodifikasi dan Algoritma Sollin yang Dimodifikasi relatif mirip. Pada orde 10, 20, 30, 60, dan 80, Algoritma Dijkstra yang Dimodifikasi menunjukkan kinerja yang lebih baik dibandingkan Algoritma Sollin yang Dimodifikasi. Namun, pada orde 40, 50, 70, 90, dan 100, Algoritma Sollin yang Dimodifikasi menunjukkan kinerja yang lebih baik.

Minimum Routing Cost Spanning Tree (MRCST) adalah sebuah spanning tree yang meminimalkan jumlah jarak berpasangan antar simpul pada suatu graf berbobot. Dalam penelitian ini, kami menggunakan Algoritma Campos dengan sedikit modifikasi pada koefisien spanning potential. Algoritma tersebut diimplementasikan pada data masalah berbentuk tabel acak dari graf lengkap dengan orde 10 hingga 100 dengan kenaikan 10. Tujuan penelitian ini adalah untuk menemukan diameter (jarak lintasan terpendek terbesar) dan maximum link (jumlah maksimum sisi yang menghubungkan dua simpul) pada solusi spanning tree dari masalah MRCST. Hasil penelitian menunjukkan bahwa sedikit modifikasi pada koefisien spanning potential menghasilkan solusi yang lebih baik.

Minimum Spanning Tree (MST) merupakan salah satu masalah yang terkenal dan sering digunakan sebagai tulang punggung (backbone) dalam berbagai permasalahan desain jaringan. Diberikan suatu graf 𝐺 ( 𝑉 , 𝐸 ) G(V,E), di mana 𝑉 V adalah himpunan simpul (vertices) dan 𝐸 E adalah himpunan sisi (edges) yang menghubungkan simpul-simpul dalam 𝑉 V, serta untuk setiap sisi 𝑒 𝑖 𝑗 e ij ​ terdapat bobot terkait 𝑐 𝑖 𝑗 ≥ 0 c ij ​ ≥0. Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST) adalah masalah untuk menemukan MST dengan tetap mempertimbangkan batasan derajat (degree constraint) pada setiap simpul, serta memenuhi persyaratan instalasi simpul pada setiap periode. Dua algoritma, yaitu WWM1 dan WWM2, diusulkan untuk menyelesaikan masalah ini. GNU OCTAVE digunakan untuk proses pemrograman dan visualisasi. GNU merupakan akronim rekursif dari “GNU's Not Unix!”, dan nama tersebut dipilih karena sistem ini mirip dengan Unix, tetapi berbeda karena bersifat bebas (free) dan tidak mengandung kode Unix. Algoritma-algoritma tersebut diimplementasikan menggunakan 300 masalah yang dihasilkan secara acak. Selain itu, algoritma WWM1 dan WWM2 juga dibandingkan menggunakan data yang telah ada dalam literatur, dan hasil penelitian menunjukkan bahwa algoritma WWM2 memberikan kinerja terbaik.

Di Indonesia, dana untuk suatu proyek atau kegiatan biasanya dibagi ke dalam beberapa tahap pencairan, yang umumnya terdiri dari dua atau tiga tahap. Oleh karena itu, untuk mengoptimalkan pemanfaatannya, tim proyek perlu merancang proyek tersebut agar dapat digunakan secepat mungkin tanpa melanggar batasan yang ditetapkan oleh pemerintah. Multi Periods Degree Constrained Minimum Spanning Tree Problem (MPDCMST) adalah suatu masalah yang berkaitan dengan pencarian instalasi jaringan dengan biaya minimum untuk suatu komoditas tertentu, sehingga jaringan tersebut tidak melanggar batasan keandalan (reliability restriction) serta memenuhi keterbatasan dana pada setiap tahap instalasi. Dalam makalah ini, kami mengusulkan tiga algoritma dengan memodifikasi algoritma Kruskal dan Prim. Algoritma tersebut diimplementasikan pada 300 masalah yang dihasilkan secara acak dengan orde simpul (vertex order) antara 10 hingga 100, dan kemudian dibandingkan dengan metode yang telah ada dalam literatur. Hasil penelitian menunjukkan bahwa algoritma yang diusulkan memberikan kinerja yang lebih baik.

Paper ini menyajikan dua metode pencarian untuk menyelesaikan DCMST: Tabu Search dan Modified Penalty Method. Tabu Search menggunakan memori untuk menghindari solusi yang baru saja dikunjungi. Modified Penalty Method menggunakan fungsi penalti yang dimodifikasi untuk menangani pelanggaran batasan derajat. Kedua metode diuji pada berbagai instance dan dibandingkan dengan metode eksak dan heuristik lainnya.

Paper ini menyajikan algoritma paralel untuk masalah Minimum Spanning Tree menggunakan pendekatan Local Linear Programming (LLP). Pendekatan ini memecah masalah MST global menjadi subproblem lokal yang dapat diselesaikan secara independen. Menunjukkan skalabilitas yang baik pada arsitektur multi-core modern dan memberikan kontribusi pada pemahaman teoritis hubungan antara linear programming dan algoritma graf paralel.

Paper ini menyajikan varian paralel, platform-independen dari algoritma Borůvka dengan inti kontraksi graf yang efektif dan eksplisit. Implementasi CPU multi-core menskalakan secara linear hingga 8 thread, sedangkan implementasi GPU berkinerja jauh lebih baik. Implementasi ini mengungguli semua implementasi MST-solver paralel lainnya untuk berbagai set graf jaringan jalan yang tersedia secara publik.

Paper ini menyajikan implementasi paralel dari algoritma Minimum Spanning Tree Borůvka. Algoritma Borůvka secara alami cocok untuk paralelisasi karena setiap komponen dapat memilih edge keluar terbaik secara independen pada setiap iterasi. Implementasi menunjukkan speedup yang signifikan dibandingkan versi sekuensial. Paper membahas trade-off antara komunikasi dan komputasi dalam konteks algoritma graf paralel.

Borůvka menyajikan pada tahun 1926 solusi pertama dari Masalah MST yang dianggap sebagai tonggak Optimisasi Kombinatorial. Paper ini menyajikan terjemahan bahasa Inggris pertama dari kedua karya perintisnya, diikuti survei perkembangan masalah MST, komentar, dan perspektif sejarah. Dari banyak algoritma yang tersedia, algoritma Borůvka adalah dasar dari algoritma tercepat yang diketahui.

Buku ini memperkenalkan bidang yang berkembang pesat dari ant colony optimization. Memberikan gambaran luas tentang ide-ide yang mendasari ACO, penerapannya pada berbagai masalah optimisasi kombinatorial, dan menjelaskan banyak algoritma ACO beserta aplikasi utamanya. Bab 4 melaporkan apa yang diketahui tentang teori algoritma ACO, membuktikan konvergensi untuk kelas spesifik algoritma ACO.

Paper ini memperkenalkan Ant System (AS), algoritma awal dari Ant Colony Optimization (ACO), yang meniru perilaku koloni semut dalam menemukan jalur terpendek melalui mekanisme pheromone trail. Metode ini menggunakan konsep positive feedback, distributed computation, dan eksplorasi berbasis heuristik untuk menyelesaikan masalah optimisasi kombinatorial seperti Traveling Salesman Problem (TSP). Paper ini merupakan salah satu karya seminal yang menjadi dasar perkembangan algoritma swarm intelligence modern.

Disajikan MAX-MIN Ant System (MMAS), perbaikan dari AS original. MMAS berbeda dalam: (i) hanya semut terbaik yang memperbarui pheromone; (ii) jumlah pheromone dibatasi pada interval [τ_min, τ_max] untuk menghindari stagnasi; (iii) trail pheromone diinisialisasi ke τ_max. MMAS efektif membimbing heuristik pencarian lokal menuju wilayah yang menjanjikan dan termasuk algoritma berkinerja terbaik untuk TSP dan QAP.

Survey ini menyediakan overview dan perbandingan konseptual dari metaheuristics utama: Simulated Annealing, Tabu Search, Genetic Algorithms, Evolutionary Strategies, Ant Colony Optimization, dan Particle Swarm Optimization. Membahas karakteristik umum, kekuatan dan kelemahan masing-masing pendekatan, serta hubungan dan perbedaan di antara mereka. Menjadi referensi penting bagi peneliti dan praktisi di bidang optimisasi kombinatorial.

Masalah yang dipertimbangkan adalah menghubungkan sekumpulan terminal dengan jaringan link langsung sependek mungkin. Prosedur sederhana dan praktis diberikan untuk menyelesaikan masalah ini baik secara grafis maupun komputasional. Prosedur-prosedur ini juga memberikan solusi untuk kelas masalah yang jauh lebih luas. Algoritma ini sekarang dikenal sebagai algoritma Prim dan merupakan salah satu algoritma paling fundamental dalam teori graf.

Paper oleh Joseph Kruskal (1928–2010) menandai langkah awal dari riset operasi menuju ilmu komputer. Algoritma yang disajikan sebagai Construction A, sekarang dikenal sebagai algoritma Kruskal, menemukan minimum-cost spanning tree dalam graf tak berarah dengan menumbuhkan forest, menambahkan edge satu per satu dari terpendek ke terpanjang, tidak termasuk edge yang akan membuat cycle.

Artikel ini merupakan edisi lanjutan dari kolom berkala yang bertujuan memperbarui daftar masalah NP-complete dan masalah komputasi sulit lainnya yang sebelumnya dikompilasi dalam buku Computers and Intractability oleh Garey dan Johnson (1979). Kolom ini memberikan pembaruan mengenai hasil penelitian terbaru terkait NP-hardness, PSPACE-hardness, serta perkembangan metode pembuktian kompleksitas komputasi. Penulis juga mengundang kontribusi komunitas riset untuk melaporkan hasil baru atau masalah terbuka dalam bidang teori kompleksitas.

Paper pertama yang secara formal mendefinisikan masalah DCMST. Masalah diformulasikan sebagai masalah integer programming linear 0-1. Prosedur heuristik primal dan dual (construction) dan algoritma branch-and-bound diusulkan untuk membangun DCMST. Paper ini menjadi fondasi untuk seluruh penelitian selanjutnya di bidang degree-constrained spanning trees.

Paper ini mengembangkan algoritma approximation untuk MST dengan batasan derajat non-uniform, menggabungkan metode primal-dual dengan local search. Memberikan kontribusi penting pada pemahaman teoritis trade-off antara kualitas solusi dan waktu komputasi untuk DCMST. Hasil menunjukkan bahwa kombinasi teknik primal-dual dan local search dapat memberikan jaminan approximation yang baik.

Paper ini mengembangkan tiga heuristik untuk DCMST: simulated annealing, genetic algorithm, dan metode berdasarkan problem space search. Diusulkan representasi tree alternatif untuk memfasilitasi pencarian neighbourhood pada genetic algorithm — representasi ini dapat digeneralisasi ke masalah optimisasi tree lainnya. Kinerja komputasional dari semua pendekatan dibandingkan terhadap solusi eksak dalam literatur.

Paper ini memperkenalkan pendekatan evolusioner baru untuk DCMST menggunakan representasi berbasis edge dan operator genetik yang dirancang khusus untuk mempertahankan feasibility constraint derajat. Hasil eksperimen pada masalah benchmark menunjukkan pendekatan ini dapat bersaing dengan heuristik tradisional. Paper juga memperkenalkan M-graph dataset yang menjadi benchmark standar untuk evaluasi algoritma DCMST.

Paper ini mengusulkan edge sets sebagai coding evolusioner yang efektif untuk spanning trees dalam genetic algorithm. Berbeda dengan Prüfer numbers atau predecessor arrays, edge sets secara langsung merepresentasikan edge-edge dalam tree. Representasi ini memiliki lokalitas yang lebih baik dan kemudahan dalam menerapkan operator crossover dan mutasi yang bermakna. Genetic algorithm dengan edge sets coding berkinerja baik pada berbagai masalah spanning tree.

Paper ini menyediakan pendekatan terpadu untuk berbagai masalah constrained spanning tree, termasuk degree-constrained, diameter-constrained, dan hop-constrained. Paper memperkenalkan SHRD (Structured Hard Random Distance) dataset yang telah menjadi benchmark standar untuk evaluasi algoritma DCMST — dirancang untuk membuat masalah yang sulit bagi algoritma greedy dengan memiliki satu hub murah dan edge lainnya yang lebih mahal.

Paper ini menyajikan metode branch and cut untuk DCMST, menggabungkan branch-and-bound dengan cutting planes untuk memecahkan formulasi integer programming. Paper ini mengembangkan kelas valid inequalities baru yang memperkuat formulasi LP relaxation. Efektif untuk instance berukuran sedang dan dapat memberikan solusi optimal yang terverifikasi. Digunakan sebagai baseline untuk mengevaluasi kualitas solusi heuristik.