• Tam Sayı Optimizasyonu

Değişkenlerden bazılarının tam sayı olmasını gerektiren doğrusal optimizasyon problemlerine Karma Tam Sayı Programları (MIP) adı verilir.

Bu değişkenler birkaç şekilde ortaya çıkabilir:

  • Arabalar veya televizyon setleri gibi öğe sayısını temsil eden tam sayı değişkenleri. Sorun, kârı en üst düzeye çıkarmak için her bir öğeden kaç adet üretileceğine karar vermektir.
    Bu tür problemler genellikle standart doğrusal optimizasyon problemleri olarak oluşturulabilir. Bunun için değişkenlerin tam sayı olması gerekir. Sonraki bölümde bu sorun türünün bir örneği gösterilmektedir.

  • 0-1 değerlerine sahip kararları temsil eden Boole değişkenleri.
    Örnek olarak, çalışanların görevlere atanmasıyla ilgili bir problemi ele alalım (Atama bölümüne bakın). Bu tür bir problem oluşturmak için, i çalışanı j görevine atanmışsa xi,j Boole değişkenlerini 1, aksi halde 0 olacak şekilde tanımlayabilirsiniz.

Tam sayı optimizasyonu hakkında iyi bir yardımcı olması için Mosek modelleme çözüm kitabını öneririz.

Araçlar

Google, MIP sorunlarını çözmek için birkaç yol sunar:

  • MPSolver: Standart dal-bağlama teknikleri kullanan çeşitli üçüncü taraf MIP çözücüler için sarmalayıcıdır.
  • CP-SAT çözücü: SAT (memnuniyet) yöntemlerini kullanan bir kısıtlı programlama çözümüdür.
  • Orijinal CP çözücü: Kısıtlı programlama problemi çözme aracı.

Hangi çözücüyü kullanmalıyım?

MIP çözücü mü yoksa CP-SAT çözücü mü kullanacağınıza da karar vermenin kesin bir kuralı yoktur. Kabaca bir kılavuz olarak:

  • MIP çözücüler, yukarıdaki ilk örnekte olduğu gibi rastgele tam sayı değişkenleri içeren ancak standart LP olarak ayarlanabilen problemler için daha uygundur.
  • CP-SAT çözücü, yukarıdaki ikinci örnekte olduğu gibi, değişkenlerin çoğunun Boole olduğu problemler için daha uygundur.

Hem tam sayı hem de Boole değişkenlerine sahip tipik MIP'lerde iki çözücünün hızları genellikle belirgin değildir. Bu nedenle seçiminiz kişisel tercihe bağlı olabilir.

Hem MIP hem CP-SAT çözücülerin kullanıldığı örnekler için Ödev Sorusunu Çözme bölümüne ve diğer atama bölümlerine bakın.

Tamsayılı programlama problemlerini çözmenin bir başka yolu da ağ akışı çözücülerinden yararlanmaktır.
Örnek için Min. Maliyet Akışı Problemi Olarak Atama bölümüne bakın.
Ağ akışı olarak ayarlanabilen bir problem için minimum maliyet akışı çözücü, MIP veya CP-SAT çözücülerinden daha hızlı olabilir. Ancak tüm MIP'ler bu şekilde ayarlanamaz.