HorusLP ile Optimizasyon Algoritmaları Oluşturma

Yöneylem araştırması ve dışbükey optimizasyon, yıllar içinde geniş kapsamlı ticari uygulamalar bulan uygulamalı matematik alanıdır. Bilgi işlem gücü daha uygun fiyatlı ve yaygın olarak kullanılabilir hale geldikçe, araştırmacılar daha iyi kararlar almalarına yardımcı olmak için giderek daha karmaşık optimizasyon algoritmaları oluşturmaya başladı. Bugün, yöneylem araştırması tarafından desteklenen uygulamalar, küresel lojistikte yönlendirmeden enerji endüstrisinde elektrik üretiminin düzgünleştirilmesine kadar her şeye güç veriyor.

Temel teknolojinin karmaşıklığı arttıkça, araştırmacıların ve geliştiricilerin daha üretken çalışmasına yardımcı olmak için yeni bir dizi araç oluşturuldu. AMPL, CVXPY ve PuLP gibi bu araçlar, geliştiricilerin optimizasyon algoritmalarını hızlı bir şekilde tanımlamasına, oluşturmasına ve çalıştırmasına ve çok çeşitli çözücülerle arayüz oluşturmasına olanak tanır.

Bununla birlikte, optimizasyon teknolojileri ve iş ihtiyaçları karmaşık bir şekilde büyümeye devam ederken, bu araçların çoğu aşağı yukarı aynı kaldı ve endüstri ihtiyaçlarını karşılayacak kadar hızlı gelişmedi. Sonuç olarak, bu algoritmaları geliştirmek, yönetmek, hata ayıklamak ve ayarlamak, özellikle hızlı hareket eden bir iş ortamında, genellikle büyük miktarda bilişsel ek yük gerektirir.

Bugün, algoritma geliştirme iş akışlarının mimarisine yardımcı olan bir Python optimizasyon kitaplığı olan HorusLP'yi tanıtmak istiyorum. Aracın çözmek için tasarlandığı problemler hakkında konuşacağız, ardından Python kitaplığına hızlı bir genel bakış sunacağız ve bazı örnek optimizasyon algoritmaları oluşturacağız.

Optimizasyon Algoritması Geliştiricilerinin Karşılaştığı Sorunlar

Çoğu geliştiricinin karşılaştığı sürekli sorunlardan biri, sürdürülebilir, verimli, deyimsel bir yazılım oluşturma ile projenin zaman kısıtlamaları dahilinde bir ürün teslim etme arasındaki dengedir. Tarayıcı tabanlı bir uygulama, bir web API'si veya bir kullanıcı kimlik doğrulama mikro hizmeti üzerinde çalışıyor olsanız da, hedeflerinize ulaşmanın "doğru" yolu ile "hızlı" yolu arasında genellikle bir ödünleşim vardır. Bu doğal ödünleşim, ürün karmaşıklığı arttıkça daha belirgin hale gelir.

Çoğu disiplinde, bir geliştirici, mimariye yardımcı olan bir çerçeve veya kitaplık seçerek bu sorunu hafifletebilir. Web'e bakan ön uçta, birçok geliştirici React veya Angular'ı seçer; API geliştirme dünyasında, yazılım mühendisleri diğerleri arasından Django, ASP.NET MVC veya Play arasından seçim yapabilir. Bununla birlikte, mütevazı optimizasyon algoritması geliştiricisi söz konusu olduğunda, mimari karmaşıklığı yönetmeye yardımcı olacak çok az mimari araç vardır. Geliştirici, değişkenleri, kısıtlamaları ve çeşitli hedefleri kendi başına yönetmeye bırakılır. Dahası, yöneylem araştırması algoritmalarının içe bakışı genellikle zordur ve bu da sorunu daha da kötüleştirir.

HorusLP'nin temel amacı, optimizasyon algoritmaları geliştirmek için bir mimari çerçeve sağlamaktır. Çerçeve, yapısal tutarlılık sağlayarak organizasyonu kolaylaştırır ve geliştiricilerin en iyi yaptıkları şeye, yani algoritmalar oluşturmaya odaklanmasına olanak tanır.

Tipik Optimizasyon İş Akışı Zorlukları

VEYA algoritmaları geliştirirken birkaç ana karmaşıklık kaynağı vardır:

Değişkenlerden gelen karmaşıklık

• Ek iş gereksinimlerini karşılamak için genellikle değişkenlerin eklenmesi gerekir ve bunları daha sonra model tanımlarında ve raporlamada kullanım için izlemenin kolay bir yolu yoktur.
• İlgili değişkenlerin gruplandırılması ve izlenmesi gerekir ve bunları yönetmenin açık bir yolu yoktur.

Kısıtlamalardan kaynaklanan karmaşıklık

• Çeşitli senaryoları desteklemek ve hata ayıklama gerçekleştirmek için kısıtlamaların eklenmesi ve kaldırılması gerekir, ancak kısıtlamaları eklemek veya kaldırmak için bariz bir yer yoktur.
• Kısıtlamalar genellikle birbiriyle ilişkilidir/bağlıdır ve ilişkilerini ifade etmenin doğal bir yolu yoktur.

Hedeflerden kaynaklanan karmaşıklık

• Nesnel ifadeler, birden fazla bileşene sahiplerse hantal hale gelebilir. Çeşitli bileşenler ağırlıklandırılırsa ve ağırlıkların iş gereksinimlerine göre ayarlanması gerekiyorsa bu durum daha da kötüleşebilir.

Hata ayıklamanın karmaşıklığı

• Geliştirme sırasında modelin sonuçlarını görmenin kolay bir yolu yoktur. Bir geliştiricinin, sonuçları görmek için açıkça yeni değişkenler ve kısıtlama değerleri yazdırması gerekir. Bu, yinelenen koda ve daha yavaş geliştirmeye yol açar.
• Bir kısıtlama eklenmesi modelin uygulanabilir olmamasına neden olduğunda, kısıtlamanın neden modelin mümkün olmamasına neden olduğu açık olmayabilir. Genellikle, geliştiriciler çeşitli kısıtlamaları ortadan kaldırmak ve deneme yanılma yoluyla uyumsuzluğu araştırmak zorundadır.

HorusLP, geliştirici üretkenliğini ve ürün sürdürülebilirliğini geliştirmek için yapı, araçlar ve en iyi uygulamalar sağlayarak bu zorlukları daha yönetilebilir hale getirmeyi umuyor.

HorusLP Eğitimi: Optimizasyon Algoritması ve API'ye Genel Bakış

Lafı daha fazla uzatmadan konuya girelim ve HorusLP kitaplığının sizin için neler yapabileceğini görelim!

HorusLP, Python ve PuLP'yi temel aldığından, bunları pip kullanarak kurmak isteyeceğiz. Komut satırınızda aşağıdakileri çalıştırın:

 Pip install horuslp pulp

Kurulum tamamlandıktan sonra devam edelim ve bir Python dosyası açalım. Yöneylem araştırması ile ilgili önceki makalemde yer alan sırt çantası problemini uygulayacağız.

HorusLP kitaplığının çok basit bir bildirimsel API'si ve çok az ortak özelliği vardır. Gerekli sınıfları ve değişkenleri içe aktararak başlayalım:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Tüm değişkenleri import ettikten sonra bu problem için ihtiyacımız olan değişkenleri tanımlayalım. Bunu, bir değişken yöneticisi alt sınıfı oluşturarak ve onu ikili değişkenlerle doldurarak yaparız:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Değişkenler tanımlandığına göre, şimdi kısıtlamaları tanımlayalım. Ana kısıtlama sınıfını alt sınıflara ayırarak ve "tanımla" işlevini uygulayarak kısıtlamalar yaratırız.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Tanımlama işlevinde, gerekli değişkenleri ada göre isteyebilirsiniz. Çerçeve, değişken yöneticisinde değişkeni belirleyecek ve onu tanımlama işlevine iletecektir.

Kısıt uygulandıktan sonra hedefi uygulayabiliriz. Basit bir amaç olduğu için ObjectiveComponent kullanacağız:

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

define işlevi, kısıtlama sınıfının define işlevine çok benzer bir kuruluma sahiptir. Ancak bir kısıtlama ifadesi döndürmek yerine, afin bir ifade döndürürüz.

Değişkenler, kısıtlamalar ve hedefler tanımlandığına göre, şimdi modeli tanımlayalım:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Modeli oluşturmak için Problem sınıfının bir alt sınıfı olan bir sınıf yaratırız ve değişkenleri, amaçları, kısıtlamaları ve anlamı belirtiriz. Belirtilen sorunla sorunu çözebiliriz:

 prob = KnapsackProblem() prob.solve()

Çözdükten sonra, problem sınıfının print_results fonksiyonunu kullanarak sonuçları yazdırabiliriz. result_variables sınıfına bakarak da belirli değişkenlerin değerine erişebiliriz.

 prob.print_results() print(prob.result_variables)

Komut dosyasını çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

Problem durumunu, değişkenlerin son değerini, amaç değerini ve kısıtlama ifadesinin değerini görmelisiniz. Değişkenlerin elde edilen değerlerini de sözlük olarak görüyoruz.

Ve işte karşınızda, yaklaşık 35 satırdaki ilk HorusLP problemimiz!

Önümüzdeki örneklerde, HorusLP kitaplığının daha karmaşık bazı özelliklerini keşfedeceğiz.

VariableGroups'u Kullanma

Bazen değişkenler birbiriyle ilişkilidir ve mantıksal bir gruba aittir. Sırt çantası sorunu durumunda, tüm değişkenler bir nesne grubuna yerleştirilebilir. Değişken grubunu kullanmak için kodu yeniden düzenleyebiliriz. Sonraki derslerde değineceğimiz için önceki bölümdeki kodu kaydettiğinizden emin olun!

İçe aktarma ifadelerini şu şekilde değiştirin:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Şimdi, sırt çantası değişken bildirimlerini de şu şekilde değiştirmemiz gerekiyor:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

İlk argüman, değişken grubunun adıdır, ikinci değişken, o gruptaki değişkenlerin isimlerinin bir listesidir.

Şimdi kısıtlama ve nesnel tanımları değiştirmemiz gerekiyor. Tek tek adları sormak yerine, anahtarların adlar ve değerlerin değişkenler olduğu bir sözlük olarak iletilecek olan değişken grubunu ele alacağız. Kısıtlama ve nesnel tanımları şu şekilde değiştirin:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Şimdi aynı problem tanımını kullanabilir ve komutları çalıştırabiliriz:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Bunu çıktınızda görmelisiniz:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Çoklu Kısıtlamaları Yönetme

Tek bir kısıtlamaya sahip modeller nispeten nadirdir. Birden fazla kısıtlamayla çalışırken, kolayca izlenip yönetilebilmesi için tüm kısıtlamaların tek bir yerde olması iyidir. HorusLP bunu doğal kılar.

Örneğin, modeli sırt çantamıza bir kamera eklemeye zorlarsak sonuçların nasıl değişeceğini görmek istediğimizi varsayalım. Ek bir kısıtlama uygular ve onu problem tanımımıza eklerdik.

İlk öğreticide uyguladığımız modele geri dönün. Aşağıdaki kısıtlamayı ekleyin:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Kısıtlamayı modele eklemek için, onu problem tanımına şu şekilde eklememiz yeterlidir:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Sorunu çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Stdout'ta yazdırılan yeni kısıtlamayı ve değişen optimal değişken değerlerini görmelisiniz.

Bağımlı Kısıtlamaları ve Kısıtlama Gruplarını Yönetme

Kısıtlamalar genellikle ya birbirlerine bağımlı oldukları için ya da mantıksal olarak aynı gruba ait oldukları için birbirleriyle ilişkilidir.

Örneğin, bir değişkenler kümesinin mutlak değerinin toplamını sınırlamak için bir kısıtlama ayarlamak istiyorsanız, önce amaçlanan değişkenler arasındaki mutlak değer ilişkilerini ifade etmek için kısıtlamalar belirlemeli, ardından mutlak değer sınırlarını belirtmelisiniz. Bazen, değişkenler arasında belirli bir ilişkiyi ifade etmek için bir grup değişkene benzer kısıtlamalar uygulamanız gerekir.

Bu gruplamaları ifade etmek için, kısıtlama tanımlarımızın bağımlı kısıtlamalar özelliğini kullanabiliriz. Bağımlı kısıtlama özelliğinin nasıl kullanılabileceğini görmek için önceki sorunun SizeConstraint değerini şu şekilde yeniden düzenleyin:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Ve şimdi, bağımlı kısıtlamaların otomatik olarak uygulandığını test etmek için, MustHaveItemConstraint problem tanımından çıkaralım:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Kodu tekrar çalıştırın ve stdout'ta aşağıdakileri görmelisiniz:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Görünüşe göre MustHaveItemConstraint uygulanmış! Bağımlı kısıtlamanın nasıl kullanılabileceğine dair daha karmaşık bir örnek için öğreticinin sonundaki personel alımı örneğine bakın.

Çoklu Ağırlıklı Hedefleri Yönetme

Çoğu zaman, optimizasyon algoritmalarımızın geliştirilmesi sırasında, birden çok parçadan oluşan nesnel bir ifadeyle karşılaşacağız. Deneyimizin bir parçası olarak, algoritmayı istenen sonuca doğru yönlendirmek için çeşitli nesnel bileşenlerin ağırlığını değiştirebiliriz. CombinedObjective bunu ifade etmenin temiz ve basit bir yolunu sunar.

Algoritmayı heykelcik ve elma şarabını seçmek için yönlendirmek istediğimizi varsayalım. CombinedObjective kullanmak için önceki bölümdeki kodu yeniden düzenleyelim.

İlk olarak, CombinedObjective sınıfını şu şekilde içe aktarın:

 from horuslp.core import CombinedObjective

Bunun gibi bağımsız bir nesnel bileşen uygulayabiliriz:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Şimdi bir CombinedObjective uygulayarak değer hedefini ve elma şarabı/heykelcik hedefini birleştirebiliriz:

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Şimdi problem tanımını şu şekilde değiştirelim:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Sorunu çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Çıktı, birleşik amaç değerini, hedef bileşenlerin her birinin değerini, ağırlığını ve tabii ki tüm kısıtlamaların değerini ana hatlarıyla belirtecektir.

Uyumsuz Kısıtlamaları Bulma

Algoritma geliştirirken çoğu zaman uygulanabilir olmayan modellerle karşılaşırız. Model karmaşıksa, modelin neden birdenbire olanaksız olduğunu belirlemek zor olabilir. HorusLP, bu durumlarda size yardımcı olacak kullanışlı bir araca sahiptir.

Diyelim ki kısıtlamalar ekledik ve aşağıdaki kısıtlamalarla sonuçlandık:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Sırt çantasındaki öğelerin toplam boyutuyla ilgili birkaç kısıtlamamız var, elma şarabının sırt çantasında olmasını gerektiren bir kısıtlama ve kameranın hem sırt çantasında hem de sırt çantasında olmamasını gerektiren uyumsuz bir dizi kısıtlamamız var. (Elbette, gerçek dünya algoritmasında, kısıtlamalar genellikle o kadar açık değildir ve karmaşık değişken ilişkileri ve kısıtlamaları içerir.)

Ayrıca, kısıtlamaların aşağıdaki şekilde gruplandırıldığını ve belki de algılamayı daha zor hale getirdiğini varsayalım:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

İşte problem tanımı:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Sorunu çalıştırın ve aşağıdaki sonucu görmelisiniz:

 KnapsackProblem: Infeasible

Oh hayır! Biz ne yaptık? Çoğu aracı kullanıyorsak, potansiyel olarak çelişen kısıtlamaları birer birer daralttığımız zor bir hata ayıklama oturumuna başlamalıyız. Neyse ki HorusLP, uyumsuz kısıtlamaları daha hızlı daraltmanıza yardımcı olacak bir uyumsuzluk arama özelliğine sahiptir. Uyumsuzluk arama özelliğini kullanmanın en basit yolu print_results çağrısını şu şekilde değiştirmektir:

 prob.print_results(find_infeasible=True)

Bu kadar basit! Kodu çalıştırın ve şimdi çıktı olarak aşağıdakileri görmelisiniz:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Harika! Şimdi, uygunsuzluğun nedeninin MustHaveItemConstraint olmadığını ve sorunun CombinedConstraints1 ve CombinedConstraints2 nedeniyle olduğunu belirledik.

Bu bize biraz bilgi verir, ancak birleşik kısıtlamalar arasında dört bağımlı kısıtlama vardır. Dört kısıtlamadan hangisinin uyumsuz olduğunu belirleyebilir miyiz? İyi evet. print_results çağrınızı şu şekilde değiştirin:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Bu, fizibilite araştırmasının bağımlı kısıtlamaları genişletmesini sağlayacak, böylece fizibilitesizliğe neyin neden olduğuna dair çok daha ayrıntılı bir resim elde edeceğiz. Bunu çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Çok sayıda toplam kısıtlamaya sahip gerçekçi problemler için her seferinde derin fizibilite araması yapmak cazip gelse de, derin fizibilite araması çok kaynak yoğun ve zaman alıcı hale gelebilir. Bu nedenle, olasılığı daraltmak için temel fizibilite araştırmasını çalıştırmak ve bazı manuel incelemeler yaptıktan sonra derin fizibilite araştırmasını daha küçük bir alt kümede çalıştırmak en iyisidir.

Veri Dosyalarından Algoritmalar Oluşturma

Modeller oluştururken, nadiren her kısıtlamayı ve değişkeni sabit kodlama lüksüne sahibiz. Çoğu zaman programımız, girdi verilerine bağlı olarak modeli değiştirebilecek kadar esnek olmalıdır. Sabit kodlanmış girdi yerine sırt çantası sorunumuzu aşağıdaki JSON'dan oluşturmak istediğimizi varsayalım:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Bunu, kısıtlamalar ve hedefler için uyguladığımız “tanımlama” işlevine kwargların desteğine güvenerek yapabiliriz.

Basit sırt çantası problemindeki kodu değiştirelim (eğitimin 1. bölümünde uyguladığımız problem). İlk olarak JSON stringini dosyaya koyalım. Tabii ki, normalde onu harici bir kaynaktan okurduk, ancak basitlik adına her şeyi tek bir dosyada tutalım. Aşağıdakileri kodunuza ekleyin:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

Ayrıca programımızın onu ayrıştırabildiğinden emin olalım. İçe aktarma ifadelerinize aşağıdakileri ekleyin:

 Import json

Şimdi değişken kurulum kodumuzu şu şekilde değiştirelim:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Bu, JSON'daki öğelerin her biri için bir değişken tanımlayacak ve uygun şekilde adlandıracaktır.

Kısıtlama ve nesnel tanımları şöyle değiştirelim:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Belirli değişkenler yerine **kwargs , define işlevi tüm değişkenleri ada göre içeren bir sözlük alır. Kısıtlama tanımlama işlevi daha sonra sözlükten değişkenlere erişebilir.

Not: Değişken grupları için, ilk düzeyin grup adı ve ikinci düzeyin değişken adı olduğu iç içe bir sözlük olacaktır.

Gerisi oldukça basit:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Bu programı çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

HorusLP'de Özel Metrikleri Tanımlama

Bazen, hem hata ayıklama hem de raporlama amaçları için, doğrudan hedefte veya kısıtlama olarak ifade edilmeyen özel metrikler oluşturacağız. HorusLP, özel metrikleri belirlemeyi kolaylaştıran bir özelliğe sahiptir.

Bir önceki bölümümüzdeki modelin sırt çantasına kaç tane meyve koyduğunu takip etmek istediğimizi varsayalım. Bunu takip etmek için özel bir metrik tanımlayabiliriz. Metrics temel sınıfını içe aktararak başlayalım:

 From horuslp.core import Metric

Şimdi özel metriği tanımlayalım:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Gördüğünüz gibi, tanımlanan arayüz, kısıtlama ve nesnel bileşen sınıfınınkilere çok benziyor. Şimdiye kadar öğreticiyi izlediyseniz, bu size oldukça tanıdık gelecektir.

Şimdi metriği problem tanımına eklememiz gerekiyor. Buradaki arayüz yine kısıtlama tanımına çok benzer:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Bunu çalıştırın ve aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Altta basılan meyve sayısını görebilirsiniz.

Daha Karmaşık Bir Problem Üzerinde Çalışmak: İki Sırt Çantası

Biraz daha karmaşık bir örnek üzerinde çalışalım. Tek bir sırt çantası yerine bir çantamız ve bir valizimiz olduğunu varsayalım. Ayrıca dayanıklı ve kırılgan olmak üzere iki sınıf nesnemiz var. Bavul daha koruyucu olduğu için hem kırılgan hem de dayanıklı malları tutabilir. Çanta ise sadece dayanıklı malları tutabilir. Ayrıca, öğeler için verilerin aşağıdaki JSON'da verildiğini varsayalım:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Bunun modeli nasıl değiştirdiğini görelim. Model oldukça farklı olacağı için boş bir sayfa ile başlayalım. Sorunun kurulumuyla başlayın:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Şimdi değişkenleri ayarlayalım. Her olası öğe/konteyner kombinasyonu için bir ikili değişken ayarlayacağız.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Şimdi hem bavul hem de çanta için ağırlık kısıtlamaları uygulamak istiyoruz.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Şimdi biraz daha karmaşık bir kısıtlama uygulamamız gerekiyor—bir öğenin hem bavula hem de çantaya gitmemesini sağlayan kısıtlama—yani, "bavuldaki" değişken 1 ise, "çantadaki" değişkenin sıfır olması gerekir ve bunun tersi de geçerlidir. Elbette, öğenin hiçbir kapsayıcıda bitmediği durumlara da izin verildiğinden emin olmak istiyoruz.

Bu kısıtlamayı eklemek için, tüm dayanıklı öğeleri tekrarlamamız, “valizdeki” değişkeni ve “çantadaki” değişkeni bulmamız ve bu değişkenlerin toplamının 1'den küçük olduğunu iddia etmemiz gerekiyor.

HorusLP'de bağımlı kısıtlamaları dinamik olarak oldukça kolay bir şekilde tanımlayabiliriz:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Kısıtlamalar tanımlandığına göre şimdi hedefi oluşturalım. Amaç, kaplardaki tüm öğelerden elde ettiğimiz tüm değerlerin basit toplamıdır. Böylece:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Ayrıca, çantaya ve bavula ne kadar ağırlık konulduğunu ve bavul ağırlığının ne kadarının dayanıklı mallardan ve kırılgan mallardan geldiğini bir bakışta görebilmemiz için bazı özel ölçüler de tanımlayalım:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Şimdi tüm parçaları bitirdik, hadi problemi somutlaştıralım ve modeli çalıştıralım:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Bunu çalıştırın ve stdout'unuzda aşağıdaki çıktıyı görmelisiniz:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Böylece kamera, gözlük, elma ve muz toplam 15 ağırlık birimi için bavula giriyor, heykelcik, boynuz ve derici toplam 17 ağırlık için çantaya giriyor. Malların toplam değeri 32 değer birimine çıkıyor. İlginç bir şekilde, dayanıklı malların hiçbiri bavula girmedi, çünkü büyük olasılıkla çanta tüm dayanıklı malları alacak yeterli kapasiteye sahipti.

Daha Büyük ve Daha Gerçekçi Bir Senaryo: İstihdam Sorunu

HorusLP eğitimimizde bu noktaya kadar geldiyseniz, tebrikler! Artık HorusLP'yi nasıl kullanacağınız konusunda iyi bir fikriniz var.

Ancak, şu ana kadar üzerinde çalıştığımız tüm örnekler sırt çantası sorununun permütasyonlarıydı ve bazı gereksinimler ve parametreler biraz gerçekçi değil. HorusLP'nin daha gerçekçi bir sorunu nasıl çözebileceğini görmek için birlikte bir sorunu daha çözelim. Bir önceki Toptal makalemin ikinci yarısında özetlenen personel sorunu üzerinde çalışacağız.

Zamanın yararına, doğrudan modelin son versiyonuna geçeceğiz (kişisel çatışmalar, iş düzenlemeleri ve geçici işçi ödenekleri ile), ancak daha basit olan ilk modelin uygulanması GitHub'da da mevcut.

Öyleyse sorunu ayarlayarak başlayalım:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Şimdi değişkenleri tanımlayalım, bu durumda bir işçinin vardiyasında çalışıp çalışmayacağını belirleyen ikili değişkenler ve her vardiya için kaç dothrakis işe alacağımızı belirleyen tamsayı değişkenleri olacak:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Şimdi her vardiya için yeterli sayıda personel çalıştırmamızı gerektiren kısıtlamayı uygulayalım:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Şimdi, belirli kişilerin birbirleriyle çalışmasını engelleyen kısıtlamaları uygulamamız gerekiyor:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Toplama

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!