Kombinatorial Problem ( Combinatorial Problems)

Combinatorial Problem merupakan suatu permasalahan matematis utuk menyusun, mengelompokan, atau memilih jumlah objek diskrit tertentu.

Kombinatorial Problem atau bisa juga di sebut masalah kombinasi muncul dibanyak penerapan ilmu komputer dan aplikasi domain : 

• finding shortest/cheapest round trips (TSP)  
• finding models of propositional formulae (SAT)  
• planning, scheduling, time-tabling  
• internet data packet routing  
• protein structure prediction  
• combinatorial  winner determination

Kombinatorial Problems melibatkan pencarian a grouping, ordering, atau assignment dari diskrit, dari obyek himpunan berhingga yang memenuhi kondisi tertentu.

Candidate solutions adalah kombinasi dari komponen solusi yang mungkin dihadapi selama upaya solusi, tapi tidak perlu memenuhi semua kondisi yang diberikan. (Solusi-solusi dari calon solusi kandidat yang memenuhi semua kondisi yang diberikan) 

Contoh :

• Given: Set poin dalam Euclidean plane  
• Objective: Find the shortest round trip

Catatan

• Rount trip (RTT) sesuai dengan urutan point (penugasan poin untuk urutan posisi)
• Komponen solusi  : rangkaian yang terdiri dari dua titik yang dikunjungi langsung setelah yang lain 
• Candidate solution: round trip  
• Solusi                    : round trip dengan panjang minimal

Problem vs problem :

Problem  : Mengingat setiap set poin X, menemukan round trip(RTT) terpendek.

Solusi     :  Algoritma yang menemukan perjalanan pulang terpendek untuk setiap X

Problem Instance : Mengingat satu set khusus point P , menumukan roundtrip(RTT) terpendek.

Solusi                   : Routrip(RTT) terpendek di gunakan untuk point P

(Secara teknis, masalah dapat diformalkan sebagai set contoh masalah)

Decision problems: 

Solusi = solusi kandidat yang memenuhi untuk diberikan kondisi logis

Contoh: Grafik Warna Masalah

Setiap masalah keputusan memiliki dua varian:
Search variant     : Mencari solusi untuk di berikan masalah (menentukan bahwa tidak ada solusi)
Decision variant  : Menentukan apakah solusi untuk masalah yang diberikan misalnya ada.

Catatan: Cari dan putuskan varian yang erat terkait algoritma untuk dapat digunakan  memecahkan masalah yang lainnya.

Optimisation problems:

• Dapat dilihat sebagai generalisasi dari masalah keputusan
• Tujuan fungsi F kualitas langkah solusi (Sering didefinisikan pada semua solusi calon)
• Tujuan khas: mencari solusi dengan kualitas optimal 
• minimisation problem:  kualitas optimal = nilai minimal f
• maximisation problem: kualitas optimal = nilai maksimal f

Varian dari masalah optimasi:

Search variant         : Mencari solusi dengan optimal nilai fungsi  untuk diberikan  masalah. 

Evaluation variant: : Menentukan nilai fungsi tujuan yang optimal untuk diberikan masalah

Setiap masalah optimasi telah dikaitkan masalah keputusan

Contoh masalah dan solusi tetap  terikat b, menemukan solusi dengan nilai fungsi tujuan ≤ b (untuk meminimalkan masalah ) atau menentukan bahwa tidak ada solusi. Banyak masalah optimasi memiliki fungsi tujuan serta kondisi logis bahwa solusi harus memenuhi.

Kandidat solusi disebut layak (atau valid) jika memenuhi kondisi logis yang diberikan.

Catatan: kondisi logis selalu dapat ditangkap oleh fungsi tujuan sehingga kandidat solusi yang layak

sesuai dengan solusi dari masalah keputusan yang terkait

Note :

• Algoritma untuk masalah optimasi dapat digunakan untuk memecahkan masalah  terkait keputusan.
• Algoritma untuk masalah keputusan selalu dapat diperpanjang untuk masalah optimasi terkait.
• Tidak selalu memecahkan masalah dengan efisien

Sumber Referensi : Hoos, Holger H & St¨utzle, Thomas , , " STOCHASTIC LOCAL SEARCH FOUNDATIONS AND APPLICATION ( Introduction: Combinatorial Problems and Search )  , http://www.sls-book.net, 3 Oktober 2016 .