Metode Branch and Bound

From Systems analysis Wiki
Jump to navigation Jump to search

Metode cabang dan batas (Ingg. Branch and Bound, singk. B&B atau BnB) adalah suatu paradigma umum untuk membangun algoritma eksak guna menyelesaikan masalah optimasi diskret dan kombinatorial, khususnya masalah NP-sulit[1]. Metode ini merupakan strategi pencacahan terarah, di mana seluruh himpunan solusi yang layak secara berurutan dibagi menjadi subhimpunan-subhimpunan (percabangan), dan untuk masing-masing subhimpunan tersebut dihitung estimasi (batas) nilai fungsi tujuan. Estimasi ini memungkinkan untuk membuang (memotong) subhimpunan yang jelas-jelas tidak mengandung solusi optimal, sehingga ruang pencarian berkurang secara signifikan[2].

Metode ini pertama kali diusulkan oleh A. Land dan A. Doig pada tahun 1960 untuk menyelesaikan masalah pemrograman bilangan bulat[3]. Sejak saat itu, metode ini menjadi salah satu pendekatan paling fundamental dalam riset operasi dan ilmu komputer. Keunggulan utama metode ini adalah fleksibilitasnya: metode ini bukan merupakan algoritma tertentu, melainkan suatu kerangka kerja (framework) strategis tingkat tinggi yang adaptif terhadap struktur masalah yang diselesaikan.

Komponen Utama Metode

Inti dari metode ini adalah tiga operasi fundamental yang diterapkan pada subhimpunan ruang solusi yang diorganisasikan dalam bentuk pohon pencarian.

  • Percabangan (Ingg. Branching) — adalah proses pemisahan rekursif himpunan solusi layak saat ini Si menjadi beberapa subhimpunan yang lebih kecil, umumnya tidak saling tumpang tindih Si1,Si2,…,Sik. Setiap subhimpunan tersebut berkorespondensi dengan submasalah baru dan direpresentasikan sebagai simpul anak dalam pohon pencarian. Misalnya, pada masalah pemrograman bilangan bulat, percabangan sering dilakukan berdasarkan variabel yang memiliki nilai pecahan dalam solusi relaksasi LP.
  • Penghitungan batas (Ingg. Bounding) — untuk setiap simpul pohon pencarian (yaitu untuk setiap submasalah) dihitung estimasi nilai fungsi tujuan. Untuk masalah minimisasi, ini adalah batas bawah (lower bound), yang merupakan estimasi terjamin dari bawah untuk sembarang solusi dalam subhimpunan tersebut. Paling sering, estimasi ini diperoleh dengan menyelesaikan relaksasi dari submasalah asal — versi yang disederhanakan di mana beberapa kendala sulit (misalnya, kendala bilangan bulat) sementara diabaikan. Yang paling umum digunakan adalah relaksasi LP.
  • Pemangkasan (Ingg. Pruning) — adalah proses pengecualian dari pertimbangan simpul-simpul (beserta seluruh subpohon yang bersesuaian) yang jelas-jelas tidak dapat mengandung solusi optimal. Sebuah simpul dipangkas dalam salah satu kasus berikut:
  1. Pemangkasan berdasarkan batas: Batas bawah untuk simpul ini ternyata tidak lebih baik (yaitu lebih besar atau sama dengan, untuk masalah minimisasi) daripada nilai solusi layak terbaik yang ditemukan saat ini, yang disebut rekor (incumbent).
  2. Pemangkasan berdasarkan kelayakan: Solusi relaksasi dari simpul tersebut layak untuk masalah asal (misalnya, semua variabel bernilai bilangan bulat). Solusi ini dibandingkan dengan rekor saat ini, dan jika lebih baik, rekor diperbarui. Percabangan lebih lanjut dari simpul ini tidak diperlukan.
  3. Pemangkasan berdasarkan ketidaklayakan: Submasalah yang berkorespondensi dengan simpul tidak memiliki solusi yang layak.

Algoritma Umum

Algoritma umum metode cabang dan batas untuk masalah minimisasi dapat dijelaskan dengan langkah-langkah berikut:

  1. Inisialisasi: Temukan solusi layak awal (misalnya, dengan menggunakan heuristik) dan tetapkan nilainya sebagai batas atas awal (rekor) U. Buat antrian simpul aktif Q yang berisi simpul akar (masalah asal).
  2. Perulangan utama: Selama antrian Q tidak kosong:
    • Pilih sebuah simpul dari Q sesuai dengan strategi pencarian (misalnya, pencarian mendalam atau pencarian terbaik).
    • Selesaikan relaksasi untuk simpul ini, sehingga diperoleh batas bawah L.
    • Pangkas simpul jika L≥U.
    • Jika solusi relaksasi layak untuk masalah asal, perbarui rekor: U←L.
    • Jika simpul tidak dipangkas dan solusinya tidak layak, lakukan percabangan, bagi simpul menjadi simpul-simpul anak, dan tambahkan ke antrian Q.
  3. Penyelesaian: Ketika antrian Q menjadi kosong, algoritma berakhir. Solusi yang ditemukan, berkorespondensi dengan rekor U, adalah solusi optimal global.

Sifat dan Teorema Utama

  • Kebenaran dan konvergensi: Algoritma ini dijamin menemukan solusi optimal global dalam jumlah langkah yang terhingga, jika himpunan solusi layak berhingga dan prosedur percabangan bersifat konvergen (yaitu, saat pemisahan rekursif, subhimpunan "menyusut" menuju titik-titik)[4].
  • Strategi pencarian: Efisiensi algoritma sangat bergantung pada strategi pemilihan simpul berikutnya untuk percabangan (misalnya, pencarian mendalam, pencarian melebar, pencarian terbaik) dan pada pemilihan variabel untuk percabangan. Solver modern sering menggunakan strategi hibrida[5].

Contoh

  • Masalah pemrograman bilangan bulat: Aplikasi klasik dari metode ini. Sebagai relaksasi digunakan pemrograman linear. Percabangan dilakukan berdasarkan variabel pecahan xj, menghasilkan dua submasalah dengan kendala tambahan xj≤⌊xj∗⌋ dan xj≥⌈xj∗⌉.
  • Masalah Salesman Keliling: Ruang solusi adalah semua siklus Hamilton yang mungkin dalam graf. Percabangan dapat dilakukan berdasarkan sisi (sertakan/kecualikan sisi dari rute). Sebagai batas bawah dapat digunakan solusi dari masalah yang lebih sederhana, seperti masalah penugasan atau pembangunan pohon rentang minimum[6].

Konsep Terkait dan Aplikasi

  • Metode Cabang dan Potongan (Branch-and-Cut): Metode hibrida yang menggabungkan B&B dengan metode bidang potong. Pada setiap simpul pohon pencarian, selain menyelesaikan relaksasi, dihasilkan ketidaksamaan tambahan (potongan) yang memperkuat batas bawah, sehingga menghasilkan pemangkasan cabang yang lebih efisien.
  • Pencarian dengan Backtracking (Backtracking): Metode cabang dan batas dapat dipandang sebagai generalisasi algoritma ini untuk masalah optimasi.
  • Pemangkasan Alfa-Beta: Analogi konseptual yang digunakan dalam pohon permainan untuk memangkas cabang yang jelas-jelas kalah.

Lihat Juga

  • Pemrograman bilangan bulat
  • Optimasi kombinatorial
  • Masalah Salesman Keliling
  • Masalah NP-sulit
  • Metode simpleks

Catatan

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.info/int/index.php?title=Metode_Branch_and_Bound&oldid=4314"