Kombinatoryal Optimizasyon (Combinatorial Optimization)

Kombinatoryal optimizasyon nedir?

Combinatorial optimization, sonlu ama çoğu zaman devasa bir olası çözüm kümesi içinden, bir maliyet (cost) fonksiyonunu en küçük ya da en büyük yapan çözümü bulma problemidir. Üç parçadan oluşur: bir temel eleman kümesi, bu elemanlardan kurulabilen geçerli (feasible) çözümler ailesi ve her çözüme bir sayı atayan maliyet fonksiyonu.

Amaç tek bir "en iyi" kombinasyonu bulmaktır — ama çözüm sayısı o kadar büyük olabilir ki hepsini tek tek denemek pratikte imkansızlaşır.

Nasıl çalışır?

Zorluğun kaynağı şu: ilginç problemlerde geçerli çözüm sayısı eleman sayısıyla üstel (exponential) büyür. Bu yüzden kaba kuvvet (brute force) sayma işe yaramaz ve daha akıllı yöntemler gerekir:

• Kesin (exact) yöntemler: branch-and-bound çözüm uzayını alt problemlere böler, alt ve üst sınırlar hesaplayıp umut vermeyen dalları budar. branch-and-cut buna cutting plane''leri ekleyerek gevşetmeyi sıkılaştırır. Uygun yapıdaki problemlerde dynamic programming kullanılır.
• Heuristic ve metaheuristic''ler: greedy, local search, simulated annealing, genetic algorithm gibi yöntemler optimali garanti etmez ama makul sürede iyi çözümler üretir.
• Approximation algoritmaları: bulduğu çözümün optimale ne kadar yakın olacağını matematiksel olarak garanti eder.

Neden önemli?

Pek çok klasik problem bu çatıya oturur ve büyük bölümü NP-hard''dır; yani bilinen hiçbir algoritma onları her girdi için hızlı çözemez. Integer linear programming (tamsayılı doğrusal programlama) de NP-hard sınıfındadır. Bu yüzden pratikte "garantili en iyi" ile "yeterince iyi ve hızlı" arasında bilinçli bir seçim yapılır — kombinatoryal optimizasyonu hem teorik hem de mühendislik açısından ilginç kılan da budur.

Kullanım alanları

• Gezgin satıcı problemi (TSP), en kısa yol, minimum spanning tree
• Rota ve lojistik planlama, araç çizelgeleme
• Üretim ve vardiya çizelgeleme (scheduling)
• Atama (assignment) ve kaynak dağıtımı
• Sırt çantası (knapsack) tipi bütçe ve kapasite problemleri