HorusLP-Gurobi: Gurobi için Üst Düzey Optimizasyon Mimarisi

Optimizasyon teknolojileri daha karmaşık hale geldikçe, ticari çözücüler sektörde giderek daha önemli bir rol oynamaya başladı. Açık kaynaklı çözücülerle karşılaştırıldığında, ticari çözümler, gelişmiş ön çözme, sıcak başlatma ve dağıtılmış çözme gibi karmaşık optimizasyon modellerini çözmek için daha fazla özelliğe sahip olma eğilimindedir.

Piyasadaki en popüler ticari çözücülerden biri, her biri ticari çözücü alanında öncü olan kurucu ortaklar Zonghao Gu, Edward Rothberg ve Robert Bixby'nin adını taşıyan Gurobi'dir. Gurobi, yakın tarihte FCC'nin bant genişliği tahsis projesi ve Pennsylvania Eyalet Hapishanesi'nin mahkum yeniden atama projesi de dahil olmak üzere birçok yüksek profilli optimizasyon projesine güç verdi.

Bugün, optimizasyon modellemesi için üst düzey bir bildirimsel arayüz sağlayan bir yazılım paketi olan HorusLP'nin, Gurobi'nin en gelişmiş özelliklerinden yararlanırken kullanıcılara sezgisel bir modelleme deneyimi sunmak için Gurobi'nin API'si ile nasıl bütünleştiğine bakacağız.

Optimizasyon: Hızlı Bir Tazeleme

Optimizasyon veya yöneylem araştırmasına aşina olmayanlar için optimizasyon, bir kısıtlama sistemine tabi bir denklem sistemi içindeki değişkenlerin optimal değerlerini bulan bir matematiksel teknikler koleksiyonunu ifade eder. Yukarıdaki cümle biraz kuru geliyorsa, belki bir örnek açıklamaya yardımcı olabilir.

15 pound taşıma kapasiteli bir sırt çantanız olduğunu varsayalım. Önünüzde her biri belirli bir ağırlık ve parasal değere sahip birkaç eşya var:

1. Kamera: ağırlık 2 libre, değer 5 dolar
2. Heykelcik: ağırlık 4 libre, değer 7 dolar
3. Elma şarabı: ağırlık 7 libre, değer 2 $
4. Boynuz: ağırlık 10 libre, değer 10 dolar.

Toplam ağırlığı 15 librenin altında kalacak, ancak değeri maksimum olacak şekilde sırt çantanıza yerleştireceğiniz öğeleri seçmek istiyorsunuz. (Yüksek değerli eşyaları bir sırt çantasına neden koyduğumuza dair daha fazla bağlama ihtiyacınız varsa, bir anlatı için hayal gücünüzü kullanmaya teşvik edilirsiniz. İyi aday anlatılar, bir yangından ve emlak müzayedelerinden bir şeyler kurtarmayı veya yaptığımız bazı hain faaliyetleri içerir. ' bahsetmemeyi tercih ederim.)

Problemi aşağıdaki optimizasyon problemi olarak formüle edebiliriz:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Bu sorunu formüle ettikten sonra, sırt çantamıza yerleştirilecek en iyi öğeleri bulmak için optimizasyon tekniklerini uygulayabiliriz. Çözümün bir örneğini Python kullanarak optimizasyon problemlerini çözme ve çekirdek HorusLP API kullanarak optimizasyon problemlerini çözme konusundaki önceki makalelerimden bulabilirsiniz.

Altta yatan matematiksel teknik oldukça etkileyici, ancak bu makalenin kapsamı dışında. Daha fazlasını öğrenmek isterseniz, her ikisi de Gurobi'nin izniyle buraya ve buraya bakmanızı öneririm.

Gurobi

En eski optimizasyon problemleri, hesap makineleriyle çalışan matematikçi ekipleri tarafından çözülürken, günümüzde çoğu optimizasyon problemi, çözücü adı verilen özel yazılımlar kullanılarak çözülmektedir. Çoğu çözücü genellikle iyi formüle edilmiş doğrusal ve tamsayılı programlama problemlerinin çoğunun çözümlerini bulabilirken, bazı çözücüler diğerlerinden çok daha yeteneklidir. Başkalarının çözemediği problem sınıflarını çözebilir, son teknoloji matematik uygulayarak problemleri daha hızlı çözebilir veya dağıtılmış bilgisayarlar kullanarak büyük, zor problemleri çözebilirler. En gelişmiş özellikler genellikle en hızlı, en karmaşık çözücüleri oluşturma konusunda uzmanlaşmış şirketler tarafından geliştirilen ve sürdürülen ticari çözücülerde sağlanır.

Gurobi, hükümetler, akademik kurumlar ve finanstan lojistiğe kadar çeşitli sektörlerde faaliyet gösteren şirketler de dahil olmak üzere optimizasyon topluluğunun geniş kesimleri tarafından kullanılan ticari çözücüler pazarındaki liderlerden biridir. Hız açısından, gurobi, ticari ve açık kaynaklı çözücüleri değerlendirmek için kullanılan çeşitli kriterlerde sürekli olarak daha iyi performans gösterir.

Gurobi ayrıca Python'dan modeller oluşturmanıza olanak tanıyan güçlü bir Python API'si ile birlikte gelir. Bu özellik, modelcilerin, model oluşturma sırasında Python'un tüm kullanışlı veri işleme kitaplıklarına erişmelerini sağlar ve bu, süreçlerine büyük ölçüde yardımcı olur. Gurobi Python API'sinin bir gösterimi olarak, sırt çantası problemini şu şekilde modelleyebilirsiniz:

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

Örneği çalıştırmak size aşağıdaki çıktıyı verecektir:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP, optimizasyon algoritmaları geliştirme deneyimleri üzerine kurulmuş bir optimizasyon modelleme kitaplığıdır. Halihazırda mevcut modelleme kitaplıkları, yöneylem araştırmasının ticari uygulamalarında tipik olarak karşılaşılan karmaşık, çok yönlü sorunlarla çalışmak için gerekli araçlardan yoksundur.

Optimizasyon kitaplıklarının çoğu düşük seviyeli zorunlu bir arayüz sunarken, optimizasyon modelleri daha karmaşık hale geldikçe, karmaşıklığı yönetmek için daha iyi araçlara ihtiyaç duyulur. HorusLP, bu karmaşıklıkları yönetmek için daha üst düzey araçlar sağlayan bir kitaplıktır. HorusLP ayrıca daha hızlı geliştirme ve yineleme sağlayan güçlü hata ayıklama ve raporlama araçları sağlar.

Özünde HorusLP, optimizasyon modelleri etrafında çok ihtiyaç duyulan mimariyi sağlayan nesne yönelimli bir kitaplıktır. Python nesne yönelimli sözdiziminden yararlanan HorusLP kitaplığı, optimizasyon modellerinin optimize edilebileceği bir yapı sağlar. Sonuç, ayrıştırılmış, modüler ve okunması kolay bir kod tabanıdır.

Kod örnekleriyle temel HorusLP kitaplığına daha ayrıntılı bir giriş yapmak isterseniz, burada bir eğitim bulabilirsiniz.

HorusLP-Gurobi Entegrasyonu

HorusLP'nin çekirdek API'si, optimizasyon modelleri oluşturmak için uygun, yüksek seviyeli bir API sağlarken, Gurobi'yi bir çözücü olarak kullanma yeteneğine sahip olsa da, Gurobi'nin daha gelişmiş bazı yeteneklerine erişimi olmayan PuLP üzerine kurulmuştur.

HorusLP-Gurobi, HorusLP API'nin Gurobi'nin Python API'si kullanılarak oluşturulmuş bir sürümüdür. Bu, HorusLP API'sini tutarlı tutarken, kullanıcının Gurobi'nin gelişmiş özelliklerine doğrudan erişmesini sağlar.

HorusLP-Gurobi'nin geliştirilmesine rehberlik eden kilit felsefelerden biri, HorusLP çekirdek API'si ile tutarlılıktı. HorusLP'nin minimalist yapısını tutarlı tutarak, bir açık kaynak çözücünün kullanıcısı Gurobi API'sini yükleyerek ve import ifadelerini değiştirerek Gurobi'yi kullanmaya kolayca geçebilir.

Basit modeller için, HorusLP tabanlı modeller, Python API'sini zorunlu olarak kullanmaktan daha fazla kod satırı alacaktır. Ancak, geliştirme süreci devam ettikçe ve modeller daha karmaşık hale geldikçe, HorusLP API'nin nesne yönelimli ve bildirimsel tasarımları, hata ayıklama ve geliştirmeyi kolaylaştıracaktır. Model tanımı hedefleri, kısıtlamaları ve değişkenleri vb. merkezileştirir ve net bir şekilde betimlediğinden, nesne yönelimi de modeli daha okunabilir hale getirecektir.

Lafı fazla uzatmadan bazı kod örneklerine geçelim!

Kod Örnekleri

Temel HorusLP API

HorusLP-Gurobi, API'yi tutarlı tuttuğundan, HorusLP çekirdek eğitimindeki kod, içe aktarmada basit bir değişiklikle taşınabilir. Ancak HoruLP-Gurobi'yi kullanmak için Gurobi optimizer'ın ve Gurobi'nin Python arayüzünün kurulu olduğundan emin olmanız gerekir. Gurobi'yi buradan kendileriyle iletişime geçerek alabilirsiniz.

Gurobi'yi kurduktan sonra HorusLP-Gurobi ile kodlamaya başlayabiliriz! Gerekli paketi yükleyerek başlayalım:

 Pip install horuslp horuslp-gurobi

Kurulum tamamlandıktan sonra HorusLP-Gurobi'yi kullanmaya başlayabiliriz! Daha önceki örnek sırt çantası problemini hatırlayın. Problemi şu şekilde modellemek için HorusLP-Gurobi kullanabiliriz:

İlk olarak, ilgili kitaplıkları içe aktarın.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Bazı değişkenleri tanımlayın.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Şimdi, kısıtlamalar sınıfını kullanarak kısıtlamaları tanımlayabiliriz.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Daha sonra hedefi benzer bir şekilde uygulayabiliriz.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Ve son olarak, sorunu tanımlayabiliriz.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

Ve problemi somutlaştırıyoruz ve çözme fonksiyonunu çağırıyoruz. Sihir yapılan yer burasıdır.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

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

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

İlk kısım Gurobi çözücü, ikinci kısım ise HorusLP çıktısıdır. Gördüğünüz gibi, algoritma heykelcik ve kornayı almamızı öneriyor ve sonuçta 17 dolar değerinde 14 pound ürün elde ediliyor.

HorusLP'yi Gurobi ile kullanmanın faydalarından biri, birçok bilgiyi "ücretsiz" olarak almanızdır. Her bir değişkenin değeri, nihai amaç değeri ve kısıtlama değerleri gibi geliştirme sırasında normalde bakmak isteyebileceğiniz birçok bilgi otomatik olarak hesaplanır ve okunması kolay bir formatta verilir.

HorusLP çekirdeği ile ilgili önceki makaleyi okuduysanız, bunun neredeyse aynı API olduğunu fark edeceksiniz. API'yi basit tutmak için, HorusLP çekirdeğinin ve HorsLP-Gurobi'nin arayüzleri, üst sınıf uygulamasında soyutlanan çözücüler arasındaki farklarla aynıdır.

Bu nedenle HorusLP'nin tanıtımını bu basit örneğe bırakacağız; HorusLP'nin gelişmiş özelliklerini gösteren daha karmaşık örnekler önceki makalede bulunabilir.

Gurobi Özellikleri

Gurobi, karmaşık sorunları çözmek için birçok gelişmiş özellik sunar. Özelliklerin çoğuna Model nesnesi aracılığıyla erişilebilir. Gurobi API ile tam uyumluluğu sağlamak için model nesnesine problem sınıfından model olarak kolayca erişilebilir.

Örneğin, sırt çantası modelinin MPS dosyasını yazmak istiyorsanız, m.write('knapsack.mps') gibi bir şey yazabilirsiniz. HorusLP-Gurobi'yi kullanırken şunları yapabilirsiniz:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Ve çalışma dizininizde MPS dosyasını görmelisiniz.

IIS hesaplama, geri arama oluşturma veya değişken ipuçları verme gibi gelişmiş Gurobi özelliklerine erişmek için bu arabirimi kullanabilirsiniz.

Gelişmiş Gurobi Özellikleri Hizmetinizde

Bugün HorusLP kitaplığının Gurobi Python API'si üzerine kurulmuş bir versiyonuna baktık. Çekirdek HorusLP'nin raporlama ve hata ayıklama özelliklerine ek olarak, artık Gurobi'nin Python API'si ile entegrasyon yoluyla sorunsuz bir şekilde erişilebilen Gurobi'nin tüm gelişmiş özelliklerine erişebilirsiniz.

Mevcut bir Gurobi kullanıcısıysanız veya Gurobi optimizasyonunu kullanmakla ilgilenen biriyseniz, umarım HorusLP'yi denersiniz! GitHub'da örnek kod bulabilir, önerilerde bulunabilir veya HorusLP-Gurobi'ye katkıda bulunabilirsiniz.