Microsoft Solver Foundation ve Optimizasyon

Çoğumuz eğitim yaşantımız boyunca matematik, trigonometri, numerik analiz vb dersler gördük. Dersin sizi en sıkan yerinde içinizden geçen şu kelimelerdi değil mi ? "Ne anlamsız bir ders, iyi de biz bunu nerede kullanacağız". Belki durum diğerleri için böyle ama bu yazıyı okuyorsanız muhtemelen sizin için değil. Günler, aylar, yıllar geçer ve o kişi bir yerinden yazılım işine bulaşır ve insanların işlerini otomatize etmek için çalışır. İşler market, muhtar, fatura, belediye takip programı geliştirirken gayet güzeldir. Taki belirli girdilerle çalışan bir sistemin en az(minumum) kaynaklarını kullanarak en fazla(maximum) çıktı üretmek için çalışan bir yapıyla karşılaşıncaya kadar.

Bu durumun adı Optimizasyondur.
Optimizasyon, elimizdeki kaynakları en verimli şekilde kullanarak en iyi sonuca ulaşmak olarak tanımlanabilir.

Yani (Wikipedia) Matematikte matematiksel programlama ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tamsayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder.

Bakınız: http://tr.wikipedia.org/wiki/Optimizasyon

Bir kaç durum senaryosu örnek vermek gerekirse;

• Yatırım maliyeti, kapasitesi, ürünlerinin birim başına karlılığı belirli bir şirketin üretiminden en fazla karı elde etmesi için hangi miktarda ne üretmesi gerektiği durumu.(Profit Optimization) 
• Kargo taşımacılığı yapan bir firmanın yasal taşıma sınırlarını aşmadan en hızlı ve en fazla karlılıkla hangi malları taşıması gerektiği durumu.(Transportation-Logistics Optimization) 
• Ahşap, Pvc veya Cam kesecek bir makinaya sahip olan bir işletmenin elindeki tabakalardan istediği kesim ölçülerinin en az fireyle kesilmesi (Cutting stock)

Bu gibi durumda girdilerin ne olduğu (Decisions, Parameters)hangi şartlar dahilinde çalışılacağı (Constraints) sonuçta ne istendiği çok önemlidir (Goals).

Evet, bundan sonra sorun artık çözülmesi gereken bir matematiksel problemdir. Peki bu problemi nasıl çözeceğiz sorusunu yanıtı ise karşılaştığınız soruna özgü veya benzer ücretsiz veya ücretli algoritmaları bulmanız olası.

Bu algoritmaları kullanabileceğiniz gibi diğer taraftan imdadınıza yetişen matematiksel modelinizi belirli bir sytaxta hazırlayıp (Optimization Modeling Language (OML) gibi) çözüme ulaştıran "solver" lar mevcut. Solverlardan farklı platformda çalışanlar yine ücretli ve ücretsiz olanlar mevcut. Çoğu cross platformu destekliyor hatta birbirleri ile ortak konuşma dilleri de var. Cplex ve gurobiyi de bir inceleyin derim.

Benim makaleme konu olan ise Microsoft Solver Foundation.

Microsoft Solver Foundation Nedir ?

Gerçek optimizasyon modellerini hızlı ve kolay bir şekilde modellemek ve çözmek için kullanılan bir kütüphane. Bu belirlemeyi yaparken Optimization Modeling Language (OML) olarak adlandırılan bir dil kullanıyor. Bu işlemleri yaparken herhangi bir .NET dili kullanabileceğiniz bu kütüphane diğer popüler solverler(çözücü) ile entegre olabiliyor. Yine geliştirilen pluginler ile Excel, SharePoint gibi uygulamalara entegre olabiliyor.

İndirmek için
http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx
http://msdn.microsoft.com/en-us/library/ff524509(v=vs.93).aspx

Sözü fazla uzatmadan bir örnek yaparak pratiğe dökelim.

Soru: bir fabrika 3 farklı ürün üretmektedir. 3 ürünün de maliyet, kar ve stoklama kapasitesi bellidir. Buna göre 5000 TL bir bütçeyle en fazla kar sağlayacak üretim yapmamız için hangi üründen ne kadar üretmeliyiz ?

 class Urun
    {
        public string Ad;
        public int Maliyet;
        public int Satis;
        public int MaksimumStok;

        public int Kar
        {
            get { return Satis - Maliyet; }
        }
    }

 class Program

    {
        static void Main(string[] args)

        {

            //En fazla 5000 TL üretim yapabiliriz. 

            int UretimButce = 5000;

            //Örnek basit ve anlaşılır olsun diye collection kullanılmadı.

            //İstenilirse collection türünden nesne kabul eden versiyonlarıda var 

            //Urunlerimiz : Decision

            Urun A_Urun = new Urun { Ad = "A_Ürünü", Maliyet = 5, Satis = 8, MaksimumStok = 1350 };

            Urun B_Urun = new Urun { Ad = "B_Ürünü", Maliyet = 8, Satis = 13, MaksimumStok = 875 };

            Urun C_Urun = new Urun { Ad = "C_Ürünü", Maliyet = 3, Satis = 5, MaksimumStok = 1100 };

            Decision DecisionA = new Decision(Domain.IntegerNonnegative, A_Urun.Ad);

            Decision DecisionB = new Decision(Domain.IntegerNonnegative, B_Urun.Ad);

            Decision DecisionC = new Decision(Domain.IntegerNonnegative, C_Urun.Ad);

            // Çözücü

            var solver = SolverContext.GetContext();


            //Model Tanımı Decision + Constraint

            var model = solver.CreateModel();

            model.AddDecision(DecisionA);

            model.AddDecision(DecisionB);

            model.AddDecision(DecisionC);


            //Kısıtlamalar, Şartlar

            model.AddConstraint("Butce_Kisitlamasi",

                           A_Urun.Maliyet * DecisionA +

                           B_Urun.Maliyet * DecisionB +

                           C_Urun.Maliyet * DecisionC <= UretimButce);

            //Ürettiğimiz ürünlerin toplam maliyeti üretim bütcemizden kücük veya eşit olmalı



            model.AddConstraint("A_Urunu_Stoklama_Kapasitemiz", DecisionA < A_Urun.MaksimumStok);

            model.AddConstraint("B_Urunu_Stoklama_Kapasitemiz", DecisionB < B_Urun.MaksimumStok);

            model.AddConstraint("C_Urunu_Stoklama_Kapasitemiz", DecisionC < C_Urun.MaksimumStok);

            //Üreteceğimiz ürünler depomuza sığmalı



            //Girdiler tanımlandı.

            //Şimdi sonuç olarak ne istediğimizi tanımlayalım

            //Üreteceğimiz ürünlerin karlığının en fazla olduğu optimizasyonu istiyoruz

            model.AddGoal("En_iyi_uretim_stok", GoalKind.Maximize,

            (A_Urun.Kar * DecisionA) +

            (B_Urun.Kar * DecisionB) +

            (C_Urun.Kar * DecisionC));


            Stopwatch sw = new Stopwatch();

            sw.Start();

            Console.WriteLine("Lütfen Bekleyiniz");


            // Çöz

            Solution solution = solver.Solve();


            // Get our decisions

            Console.WriteLine("Çözüm Kalitesi : " + solution.Quality.ToString());

            Console.WriteLine("A Ürününden {0} adet ", DecisionA);

            Console.WriteLine("B Ürününden {0} adet ", DecisionB);

            Console.WriteLine("C Ürününden {0} adet ", DecisionC);


            double gerceklesen_toplam_maliyet =

            DecisionA.ToDouble() * A_Urun.Maliyet +

            DecisionB.ToDouble() * B_Urun.Maliyet +

            DecisionC.ToDouble() * C_Urun.Maliyet;

            double toplam_satis_fiyat =

            DecisionA.ToDouble() * A_Urun.Satis +

            DecisionB.ToDouble() * B_Urun.Satis +

            DecisionC.ToDouble() * C_Urun.Satis;


            Console.WriteLine("Üretim: Harcanan : {0} Planlanan: {1}", gerceklesen_toplam_maliyet, UretimButce);

            Console.WriteLine("Satış Değeri : {0} Kar: {1}", toplam_satis_fiyat, toplam_satis_fiyat - gerceklesen_toplam_maliyet);

            Console.WriteLine("Optimizasyon {0} milisaniyede tamamlandı" , sw.ElapsedMilliseconds);

            Console.ReadLine();


        }

    }

Peki bu tarz optimizasyon hesapları enterprise projlerde nasıl kullanılabilir sorusunun zihninizde canlandığını düşünerek cevap vermek gerekirse;

ERP projelerinde üretim maliyetlerini minimize etmek adına kaynaklardan ham madde, depolama, iş gücü hesaplamalarında, üretim çizelgeleme ve planlanmasında.

MRP projelerinde üretim - stok miktarlarını optimum tutmakta.

Navigasyon uygulamalarında en kısa , en hızlı route hesaplamalarında.

Gemicilik - Logistik sektöründe yine route planının yapılıp, yükün yükleneceği ve indirileceği yere göre araç içindeki en ideal yere yüklenmesi.

Call Center uygulamalarında otomatik çağrı başlatılması ve dağıtımı senaryosunda kestirimde bulunurken. 

Yani neredeyse sınırsız kullanım alanı var. Kütüphaneyi yapanlar oldukça zengin örnekler hazırlamışlar. 

İlgimi çeken hisse senedi portföy yönetimi ile ilgili bir örneğin ekran görüntüsü. Bu kadar karmaşık ve yoğun bir algoritmanın çok kolay modellenip hesaplandığını görünce şaşırmamak elde değil.

Google' da biraz araştırma yaptığımda bu kütüphaneyi kullanarak Einstein Puzzle olarak bilinen zebra bulmacasını, sudoku bulmacaları çözen eğlenceli örnekler var. 

Sonuç olarak Microsoft Solver Foundation probleminizi belirleyip modelledikten sonra işinizi oldukça kolaylaştıracak bir kütüphane. Örnekte kod içerisindeki açıklamalarda mümkün olduğu kadar açıklama yapmaya çalıştım. 

Size tavsiyem kütüphaneye ait örnekleri de mutlaka inceleyin. Bundan sonraki makalelerde bilindik optimizasyon türlerini modelleyip çözmeye çalışacağım. 

Görüşmek üzere...

Örnek Proje