Branch and Bound Algorithm

Giriş

Operasyonel Araştırmalar I dersinde, gerçek hayatta karşılaştığımız problemlerin matematiksel modellemesini ve bu modellerin nasıl çözüleceğini öğrendik. Başlangıçta Doğrusal Programlama (Linear Programming - LP) üzerine odaklandık ve daha sonra Tamsayılı Programlama (Integer Programming - IP) konusuna geçtik. Bu makalede, Branch and Bound Algoritması ile tamsayılı programlama problemlerini nasıl çözeceğimizi inceleyeceğiz.

Doğrusal Programlama ve Çözüm Yöntemleri

LP problemlerini çözerken genellikle aşağıdaki yöntemleri kullandık:

• Grafik Yöntemi: İki değişkenli LP problemlerinde kullanılır. Kısıtları grafik üzerinde göstererek, feasible region (uygulanabilir bölgeyi) belirleriz. Optimal çözüm, bu bölgenin köşe noktalarından birinde bulunur.
• Simplex Yöntemi: Daha yüksek boyutlu LP problemleri için kullanılır.
  • Two-Phase Simplex
  • Big M Method
  • Dual Simplex
  • Revised Simplex

Bu yöntemlerin hepsi LP problemlerinin çözümü için geliştirilmiştir.

Tamsayılı Programlamaya Giriş

LP ve IP arasındaki temel fark, IP'de karar değişkenlerinin tamsayı olması gerektiğidir. Ancak, LP'de kullandığımız grafik yöntemi veya simplex yöntemi, değişkenlerin tamsayı olma şartını doğrudan ele alamaz. Bu nedenle, tamsayı kısıtlarını dikkate alan özel yöntemlere ihtiyaç duyarız.

Branch and Bound Algoritması Nedir?

Branch and Bound (Dallan ve Sınırla) Algoritması, tamsayılı programlama problemlerini çözmek için kullanılan bir yöntemdir. Bu algoritma, problemi daha küçük alt problemlere bölerek ve belirli bir sırayla bu alt problemleri çözerek optimal tamsayı çözümü bulmayı hedefler.

Ana Fikir

• Branching (Dallanma): Karar değişkenlerinin tamsayı olmaması durumunda, bu değişkenler üzerinde dallanmalar yaparız. Örneğin, değişken $x$ tamsayı değilse, $x \leq \lfloor x^* \rfloor$ ve $x \geq \lceil x^* \rceil$ şeklinde iki yeni alt problem oluştururuz.
• Bounding (Sınır Koyma): Alt problemlerin hedef fonksiyon değerlerini kullanarak, daha kötü sonuçlar verecek dalları budarız (prune).

Örnek Bir Problem ve Çözümü

Bir örnek üzerinden Branch and Bound algoritmasını inceleyelim.

Problem:

Maksimize edin:

$$Z = 5x_1 + 6x_2$$

Kısıtlar:

$$\begin{cases} 2x_1 + 3x_2 \leq 12 \\ x_1 + x_2 \leq 5 \\ x_1, x_2 \geq 0 \\ x_1, x_2 \text{ tamsayı} \end{cases}$$

Adım 1: LP Relaxation Çözümü

İlk olarak, tamsayı kısıtlarını göz ardı ederek LP problemini çözelim.

Çözüm:

LP'nin optimal çözümü $x_1^* = 2.4$, $x_2^* = 2.6$ ve $Z^* = 5 \times 2.4 + 6 \times 2.6 = 27.6$ bulunur.

Ancak, $x_1^*$ ve $x_2^*$ tamsayı değildir.

Adım 2: Dallanma

Tamsayı olmayan $x_1$ değişkeni üzerinde dallanalım.

• Dal 1: $x_1 \leq 2$
• Dal 2: $x_1 \geq 3$

Dal 1: $x_1 \leq 2$

Bu kısıtı LP problemimize ekleyerek çözüyoruz.

Çözüm:

Yeni LP'nin optimal çözümü $x_1 = 2$, $x_2 = 2.\overline{6}$, $Z = 5 \times 2 + 6 \times 2.\overline{6} = 26$.

$x_2$ hala tamsayı değil.

Tamsayı olmayan $x_2$ üzerinde dallanırız:

• Dal 1.1: $x_2 \leq 2$
• Dal 1.2: $x_2 \geq 3$

Dal 1.1: $x_2 \leq 2$

Kısıtlarımız:

$$\begin{cases} 2x_1 + 3x_2 \leq 12 \\ x_1 + x_2 \leq 5 \\ x_1 \leq 2 \\ x_2 \leq 2 \\ x_1, x_2 \geq 0 \end{cases}$$

Çözüm:

Optimal tamsayı çözüm elde edilir: $x_1 = 2$, $x_2 = 2$, $Z = 5 \times 2 + 6 \times 2 = 22$.

Bu bir Candidate Solution (Aday Çözüm) olarak saklanır.

Dal 1.2: $x_2 \geq 3$

Kısıtlarımız:

$$\begin{cases} 2x_1 + 3x_2 \leq 12 \\ x_1 + x_2 \leq 5 \\ x_1 \leq 2 \\ x_2 \geq 3 \\ x_1, x_2 \geq 0 \end{cases}$$

Bu kısıtlar altında feasible (uygulanabilir) bir çözüm yoktur. Bu dal Pruned (Budanır).

Dal 2: $x_1 \geq 3$

Kısıtlarımız:

$$\begin{cases} 2x_1 + 3x_2 \leq 12 \\ x_1 + x_2 \leq 5 \\ x_1 \geq 3 \\ x_1, x_2 \geq 0 \end{cases}$$

Çözüm:

Yeni LP'nin optimal çözümü $x_1 = 3$, $x_2 = 2$, $Z = 5 \times 3 + 6 \times 2 = 27$.

Her iki değişken de tamsayı olduğundan, bu çözüm yeni Candidate Solution'ımız olur.

Adım 3: Sonuç

En iyi tamsayı çözüm $Z = 27$ ile $x_1 = 3$, $x_2 = 2$ olarak bulunur.

Branch and Bound Algoritmasının Özellikleri

• Kesin Çözüm: Branch and Bound, optimal tamsayı çözümü garanti eden bir yöntemdir.
• Esneklik: Hem maksimizasyon hem de minimizasyon problemlerinde kullanılabilir.
• Etkililik: Büyük ölçekli problemler için hesaplama yükü artabilir, ancak dalları budama stratejileri ile etkinlik artırılabilir.

Özet

Branch and Bound algoritması, tamsayılı programlama problemlerini efektif bir şekilde çözmek için kullanılan güçlü bir yöntemdir. Ana fikir, problemi alt problemlere bölmek ve uygun olmayan dalları elemek üzerine kuruludur. Bu sayede, optimal tamsayı çözümüne ulaşılır.