HorusLP-Gurobi: بنية تحسين عالية المستوى لـ Gurobi

نظرًا لأن تقنيات التحسين أصبحت أكثر تعقيدًا ، فقد بدأت المحاليل التجارية تلعب دورًا متزايد الأهمية في الصناعة. بالمقارنة مع الحلول مفتوحة المصدر ، تميل الحلول التجارية إلى امتلاك المزيد من الميزات لحل نماذج التحسين المعقدة مثل الحل المتقدم والبدء الدافئ والحل الموزع.

يعد Gurobi أحد أشهر الحلول التجارية في السوق ، وقد سمي على اسم المؤسسين المشاركين Zonghao Gu و Edward Rothberg و Robert Bixby ، كل منهم رائد في مجال الحلول التجارية. قام Gurobi بدعم العديد من مشاريع التحسين البارزة في التاريخ الحديث بما في ذلك مشروع تخصيص النطاق الترددي التابع للجنة الاتصالات الفيدرالية ومشروع إعادة تعيين السجناء في سجن ولاية بنسلفانيا.

اليوم ، سننظر في كيفية دمج HorusLP ، وهي حزمة برمجية توفر واجهة تعريفية عالية المستوى لنمذجة التحسين ، مع واجهة برمجة تطبيقات Gurobi لتقديم تجربة نمذجة بديهية للمستخدمين مع الاستفادة من ميزات Gurobi الأكثر تقدمًا.

التحسين: تحديث سريع

بالنسبة لأولئك الذين ليسوا على دراية بالتحسين أو عمليات البحث ، يشير التحسين إلى مجموعة من التقنيات الرياضية التي تجد القيم المثلى للمتغيرات داخل نظام المعادلات الخاضعة لنظام القيود. إذا بدت الجملة أعلاه جافة بعض الشيء ، فربما يساعد المثال في التوضيح.

لنفترض أن لديك حقيبة ظهر بها 15 رطلاً من القدرة الاستيعابية. أمامك عدد قليل من العناصر ، لكل منها وزن معين وقيمة نقدية:

1. الكاميرا: الوزن 2 رطل ، القيمة 5 دولارات
2. التمثال: الوزن 4 أرطال ، القيمة 7 دولارات
3. عصير التفاح: الوزن 7 أرطال ، القيمة 2 دولار
4. القرن: الوزن 10 أرطال ، القيمة 10 دولارات.

أنت تريد اختيار العناصر لوضعها في حقيبة الظهر الخاصة بك بحيث يظل الوزن الإجمالي أقل من 15 رطلاً ولكن يتم تعظيم القيمة. (إذا كنت بحاجة إلى مزيد من السياق حول سبب إلصاقنا بالعناصر عالية القيمة في حقيبة الظهر ، فنحن نشجعك على استخدام خيالك في سرد ​​القصص. تتضمن الروايات المرشحة الجيدة إنقاذ الأشياء من حريق ومزادات العقارات ... أو بعض الأنشطة الشائنة بدلا من ذكر.)

يمكننا صياغة المشكلة على أنها مشكلة التحسين التالية:

 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

بمجرد صياغة هذه المشكلة ، يمكننا تطبيق تقنيات التحسين للعثور على أفضل العناصر لوضعها في حقيبة الظهر الخاصة بنا. يمكنك العثور على مثال للحل من مقالاتي السابقة حول حل مشكلات التحسين باستخدام Python وحل مشكلات التحسين باستخدام واجهة HorusLP API الأساسية.

إن التقنية الرياضية الأساسية رائعة للغاية ، لكنها خارج نطاق هذا المقال. إذا كنت ترغب في معرفة المزيد ، فإنني أوصي بالبحث هنا وهنا ، كلاهما من باب المجاملة Gurobi.

جوروبي

بينما تم حل مشكلات التحسين المبكرة بواسطة فرق من علماء الرياضيات الذين يعملون باستخدام الآلات الحاسبة ، يتم حل معظم مشكلات التحسين اليوم باستخدام برامج متخصصة تسمى أدوات الحل. في حين أن معظم المحولين قادرون بشكل عام على إيجاد حلول لغالبية مشاكل البرمجة الخطية والصحيحة المصاغة جيدًا ، فإن بعض الحلول تكون أكثر قدرة من غيرها. يمكنهم حل فئات من المشكلات التي لا يستطيع الآخرون حلها ، أو حل المشكلات بسرعة أكبر عن طريق تطبيق الرياضيات المتطورة ، أو حل المشكلات الكبيرة والصعبة باستخدام أجهزة الكمبيوتر الموزعة. عادةً ما يتم توفير الميزات الأكثر تقدمًا في المحاليل التجارية التي تم تطويرها وصيانتها بواسطة شركات متخصصة في بناء الحلول الأسرع والأكثر تطورًا.

Gurobi هي واحدة من الشركات الرائدة في سوق الحلول التجارية ، وتستخدمها قطاعات كبيرة من مجتمع التحسين بما في ذلك الحكومات والمؤسسات الأكاديمية والشركات العاملة في صناعات تتراوح من التمويل إلى الخدمات اللوجستية. من حيث السرعة ، يتفوق gurobi باستمرار في العديد من المعايير المستخدمة للحكم على الحلول التجارية والمفتوحة المصدر.

يأتي Gurobi أيضًا مزودًا بواجهة برمجة تطبيقات Python القوية التي تتيح لك إنشاء نماذج من Python. تتيح هذه الميزة للمصممين الوصول إلى جميع مكتبات معالجة البيانات المفيدة في Python أثناء إنشاء النموذج ، مما يساعد بشكل كبير في عمليتهم. كدليل على gurobi Python API ، إليك كيفية تصميم مشكلة الحقيبة على الظهر:

 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)

سيعطيك تشغيل المثال الناتج التالي:

 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

حورس LP

HorusLP عبارة عن مكتبة نمذجة للتحسين تم إنشاؤها بناءً على تجارب تطوير خوارزميات التحسين. تفتقر مكتبات النمذجة المتاحة حاليًا إلى الأدوات اللازمة للعمل مع نوع المشاكل المعقدة ومتعددة الأوجه التي تواجهها عادةً التطبيقات التجارية لبحوث العمليات.

بينما تقدم معظم مكتبات التحسين واجهة حتمية منخفضة المستوى ، حيث تصبح نماذج التحسين أكثر تعقيدًا ، هناك حاجة إلى أدوات أفضل لإدارة التعقيد. HorusLP هي مكتبة توفر أدوات عالية المستوى لإدارة هذه التعقيدات. يوفر HorusLP أيضًا أدوات قوية لتصحيح الأخطاء وإعداد التقارير التي تسمح بالتطوير والتكرار بشكل أسرع.

تعد HorusLP في جوهرها مكتبة كائنية التوجه توفر بنية تشتد الحاجة إليها حول نماذج التحسين. من خلال الاستفادة من بناء جملة Python الموجه للكائنات ، توفر مكتبة HorusLP بنية يمكن حولها تحسين نماذج التحسين. والنتيجة هي قاعدة بيانات مفصولة وقياسية وسهلة القراءة.

إذا كنت ترغب في الحصول على مقدمة أكثر تفصيلاً عن مكتبة HorusLP الأساسية مع عينات من التعليمات البرمجية ، يمكنك العثور على برنامج تعليمي هنا.

HorusLP-Gurobi التكامل

بينما توفر واجهة برمجة تطبيقات HorusLP الأساسية واجهة برمجة تطبيقات ملائمة وعالية المستوى لبناء نماذج التحسين ، إلا أنها مبنية على PuLP ، والتي بالرغم من قدرتها على الاستفادة من Gurobi كوسيلة للحل ، إلا أنها لا تتمتع بإمكانية الوصول إلى بعض قدرات Gurobi الأكثر تقدمًا.

HorusLP-Gurobi هي نسخة من HorusLP API تم إنشاؤها باستخدام واجهة برمجة تطبيقات Python من Gurobi. يتيح ذلك للمستخدم الوصول المباشر إلى الميزات المتقدمة لـ Gurobi ، مع الحفاظ على اتساق HorusLP API.

كانت إحدى الفلسفات الرئيسية التي وجهت تطوير HorusLP-Gurobi هي الاتساق مع واجهة برمجة تطبيقات HorusLP الأساسية. من خلال الحفاظ على هيكل الحد الأدنى من HorusLP متسقًا ، يمكن لمستخدم حلال المصدر مفتوح الانتقال بسهولة إلى استخدام Gurobi عن طريق تثبيت Gurobi API وتبديل بيانات الاستيراد.

بالنسبة للنماذج البسيطة ، ستستغرق النماذج المستندة إلى HorusLP سطورًا أكثر من التعليمات البرمجية بدلاً من مجرد استخدام Python API بشكل إلزامي. ومع ذلك ، مع استمرار عملية التطوير ومع ازدياد تعقيد النماذج ، ستجعل التصميمات التصريحية والموجهة للكائنات الخاصة بواجهة برمجة تطبيقات HorusLP من السهل تصحيح الأخطاء والتطوير. سيؤدي اتجاه الكائن أيضًا إلى جعل النموذج أكثر قابلية للقراءة ، حيث أن تعريف النموذج ينشئ مركزًا ويحدد بوضوح الأهداف والقيود والمتغيرات ، إلخ.

بدون مزيد من اللغط ، دعنا نتعمق في بعض نماذج التعليمات البرمجية!

أمثلة التعليمات البرمجية

واجهة برمجة تطبيقات HorusLP الأساسية

نظرًا لأن HorusLP-Gurobi تحافظ على اتساق واجهة برمجة التطبيقات ، يمكن نقل الكود من البرنامج التعليمي الأساسي HorusLP مع تغيير بسيط في الواردات. لاستخدام HoruLP-Gurobi ، ستحتاج إلى التأكد من تثبيت مُحسِّن Gurobi وواجهة Gurobi Python. يمكنك الحصول على Gurobi من خلال الاتصال بهم هنا.

بمجرد تثبيت Gurobi ، يمكننا البدء في البرمجة باستخدام HorusLP-Gurobi! لنبدأ بتثبيت الحزمة المطلوبة:

 Pip install horuslp horuslp-gurobi

بمجرد اكتمال التثبيت ، يمكننا البدء في استخدام HorusLP-Gurobi! أذكر مثال مشكلة حقيبة الظهر من وقت سابق. يمكننا استخدام HorusLP-Gurobi لنمذجة المشكلة على النحو التالي:

أولاً ، قم باستيراد المكتبات ذات الصلة.

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

حدد بعض المتغيرات.

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

الآن ، يمكننا تحديد القيود باستخدام فئة القيود.

 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

يمكننا بعد ذلك تنفيذ الهدف بطريقة مماثلة.

 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

وأخيرًا ، يمكننا تحديد المشكلة.

 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

وننشئ المشكلة ونطلق على دالة الحل. هذا هو المكان الذي يحدث السحر.

 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

قم بتشغيل الكود وسترى الإخراج التالي:

 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}

الجزء الأول هو Gurobi solver ، والجزء الثاني هو الإخراج من HorusLP. كما ترى ، توصي الخوارزمية بأن نأخذ التمثال والبوق ، مما ينتج عنه 14 رطلاً من العناصر بقيمة 17 دولارًا.

تتمثل إحدى مزايا استخدام HorusLP مع Gurobi في حصولك على الكثير من المعلومات "مجانًا". يتم حساب وإخراج الكثير من المعلومات التي يرغب المرء عادة في الاطلاع عليها أثناء التطوير ، مثل قيمة كل متغير وقيمة الهدف النهائية وقيم القيد تلقائيًا وإخراجها بتنسيق سهل القراءة.

إذا كنت قد قرأت المقالة السابقة عن HorusLP core ، فستلاحظ أن هذا هو نفس واجهة برمجة التطبيقات تقريبًا. للحفاظ على واجهة برمجة التطبيقات بسيطة ، فإن واجهات HorusLP core و HorsLP-Gurobi متطابقة ، مع وجود اختلافات بين المحاليل المستخرجة في تطبيق الطبقة الفائقة.

وهكذا ، سنترك مقدمة HorusLP لهذا المثال البسيط ؛ يمكن العثور على أمثلة أكثر تعقيدًا توضح الميزات المتقدمة لـ HorusLP في المقالة السابقة.

ميزات Gurobi

يوفر Gurobi العديد من الميزات المتقدمة لحل المشكلات المعقدة. يمكن الوصول إلى معظم الميزات من خلال كائن النموذج. للسماح بالتوافق الكامل مع Gurobi API ، يمكن الوصول بسهولة إلى كائن النموذج من فئة المشكلة model .

على سبيل المثال ، إذا أردت كتابة ملف MPS لنموذج الحقيبة ، في Gurobi يمكنك كتابة شيء مثل m.write('knapsack.mps') . أثناء استخدام HorusLP-Gurobi ، يمكنك ببساطة:

 # 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!

ويجب أن ترى ملف MPS في دليل العمل الخاص بك.

يمكنك استخدام هذه الواجهة للوصول إلى ميزات Gurobi المتقدمة مثل حساب IIS أو إنشاء عمليات رد نداء أو إعطاء تلميحات متغيرة.

ميزات Gurobi المتقدمة في خدمتك

نظرنا اليوم إلى نسخة من مكتبة HorusLP مبنية على واجهة Gurobi Python API. بالإضافة إلى ميزات إعداد التقارير وتصحيح الأخطاء الخاصة بـ HorusLP الأساسي ، يمكنك الآن الوصول إلى جميع الميزات المتقدمة لـ Gurobi التي يمكن الوصول إليها بسهولة من خلال التكامل مع واجهة برمجة تطبيقات Python من Gurobi.

إذا كنت من مستخدمي Gurobi الحاليين أو شخصًا مهتمًا باستخدام تحسين Gurobi ، آمل أن تجرب HorusLP! يمكنك العثور على مثال للكود أو تقديم اقتراحات أو المساهمة في HorusLP-Gurobi على GitHub.