در نسخه‌ی ۱۲٫۷ نرم‌افزار  CPLEX رویه‌ی جدیدی جایگزین هسته‌ای اصلی الگوریتم حل یعنی شاخه و برش Branch and Cut مطرح گردید. تحت این رویه مساله‌ی اولیه به یک مساله‌ی اصلی Master و یک یا چند زیرمساله Worker تجزیه می‌شود. این رویه در ادبیات علم بهینه‌سازی به الگوریتم تجزیه بندرز Benders Decomposition مشهور است. در این پست نحوه‌ی بکارگیری رویه بندرز در پلتفرم پایتون PYTHON در رابط کاربری SPYDER نرم‌افزار  ANACONDA به همراه مثال تشریح خواهد شد. جهت کسب اطلاعات بیشتر به راهنمای  Prescriptive Analytics for Python مراجعه نمایید.

تجزیه بندرز رویکردی جهت حل مسایل ریاضی بهینه‌سازی با ساختارهای قابل تجزیه ارائه می‌کند. این رویه در سه سطح عمده قابل دسترسی است:

Full Annotation کاربر تصمیم می‌گیرد که کدام متغیرها یا محدودیت‌ها در مساله‌ی اصلی و کدام‌یک در زیرمسایل قرار گیرند.

Partially Annotated کاربر یک سری تصمیمات در خصوص قرارگیری بعضی متغیرها و محدودیت‌ها و نحوه‌ی تجزیه اخذ می‌کند و مابقی تصمیمات توسط رویه‌ی حل گرفته می‌شود.

Automatic رویه‌ی حل به صورت درون‌زا تمامی تصمیمات را حل‌وفصل می‌کند.

در صورتی که مساله دارای ساختار تجزیه‌ناپذیر باشد نرم‌افزار خطای CPXERR_NO_DECOMPOSITION را برمی‌گرداند. به‌عبارتی این رویه بر روی مسایل برنامه‌ریزی عدد صحیح مختلط خطی MILP (تعدادی از متغیرها پیوسته و تعدادی گسسته) قابل پیاده‌سازی است.

گام اول – نصب پلتفرم پایتون

ابتدا نرم افزار ANACODA را از سایت زیر دانلود و سپس نصب نمایید.

https://www.anaconda.com/downloads

پس از نصب نرم‌افزار کتابخانه DOcplex را با اجرای دستور زیر در command prompt بارگیری نمایید.

conda install -c ibmdecisionoptimization docplex

گام دوم – اشتراک DOcplex

در صورتی که از خدمات IBM Decision Optimization on Cloud به صورت آزمایشی استفاده می‌نمایید با انتخاب گزینه Free Trial حساب کاربری خود را فعال نموده و به مدت ۳۰ روز با حداکثر ۵ کار همزمان و مستقل از حجم مساله از خدمات آن بهره‌مند شوید. در غیراین‌صورت به کمک گزینه‌های پرداخت طرح خود را انتخاب کنید.

https://onboarding-oaas.docloud.ibmcloud.com/software/analytics/docloud/

با ثبت‌نام در این سرویس، Base URL و API Key خود را دریافت نمایید.از حجم

گام سوم – محیط پایتون

اسکریپت زیر برای وارد کردن کتابخانه DOcplex در محیط پایتون بکار می‌رود. هم‌چنین Base URL و URL Key را در متغیرهای جداگانه‌ای ذخیره می‌نماییم.

from docplex.mp.model import Model
SVC_URL = "ENTER YOUR URL HERE"
SVC_KEY = "ENTER YOUR KEY HERE"

گام چهارم – وارد کردن مدل

هدف این گام مدل‌سازی مساله‌ی تخصیص تقاضا (نسخه ساده) در محیط پایتون است. داده‌های این مساله در این لینک بارگذاری شده است. به کمک این داده‌ها، مجموعه‌ها مقداردهی می‌شوند.

R1 = range(1,d1)
R2 = range(1,d2)

تعریف مساله به فرم زیر صورت می‌گیرد.

m = Model(name='benders')

بدین‌ترتیب متغیرهای پیوسته و گسسته تعریف می‌شوند.

X = m.continuous_var_dict([(i,j) for i in R2 for j in R1])
Y = m.integer_var_dict(R1, 0, 1) 

در نهایت بلوک‌های تابع هدف و محدودیت‌ها مشخص می‌شوند.

m.minimize( sum( Costs[i][j]*X[i,j] for i in R2 for j in R1) + sum(Y[i] for i in R1) )
m.add_constraints( sum( X[i,j] for j in R1) ==1 for i in R2)
m.add_constraints( X[i,j] - Y[j] <= 0 for i in R2 for j in R1)

گام پنجم – اطلاعات خروجی

دستورات زیر برای فراخوانی اطلاعات خروجی بکار گرفته می‌شوند.

m.print_information()
msol = m.solve(url=SVC_URL, key=SVC_KEY)
m.report()
obj1 = m.objective_value

توجه شود که اطلاعات اجرای کد، از لحظه‌ی ارسال آن به سرور به صورت لحظه‌ای به‌روز رسانی می‌شود. کاربر قادر است تمامی مسایل ارسال شده به سرور را در داشبورد خود مشاهده نماید.

گام ششم – رویه بندرز خودکار

تا این مرحله از رویه‌ی پیش‌فرض نرم‌افزار CPLEX برای حل مساله استفاده شد. همانطور که اشاره شد، رویه‌ی بندرز سه استراتژی عمده بکار گرفته شده است. مقدار یک به معنی Full Annotation، مقدار ۲ به معنی Partially Annotated و مقدار ۳ به مفهوم Automatic می‌باشد. در این گام مقدار ۳ را انتخاب می‌کنیم.

m.parameters.benders.strategy = 3
m.print_information()
msol = m.solve(url=SVC_URL, key=SVC_KEY, clean_before_solve=True)
m.report()
obj2 = m.objective_value

تحت این شرایط، رویه کل متغیرهای پیوسته را در مساله‌ی اصلی و متغیرهای گسسته را در زیرمساله جای می‌دهد.

گام هفتم – رویه بندرز سفارشی

نحوه قرارگیری متغیرها در مساله‌ی اصلی یا زیرمساله با اعداد صفر، یک یا بیش از یک مشخص می‌شود. به کمک خاصیت benders_annotation هر متغیر، این مقادیر را می‌توان مشخص کرد. در صورتی که برای متغیری مقدار این خاصیت را برابر صفر قرار دهیم، متغیر به مساله‌ی اصلی master تحصیص داده می‌شود. در صورتی که به متغیری عددی بزرگتر مساوی با عدد یک اختصاص یابد، این عدد نشان‌دهنده‌ی شماره‌ی زیر‌مساله است.

اسکریپت سفارشی زیر را به انتهای کد اعمال می‌کنیم.

m.parameters.benders.strategy = 1
for i in R2:
for j in R1:
X[i,j].benders_annotation = i%2
m.print_information()
msol = m.solve(url=SVC_URL, key=SVC_KEY, clean_before_solve=True)
m.report()
obj3 = m.objective_value

پس از اجرای مساله با سه نوع تنظیم (عادی، بندرز خودکار و بندرز سفارشی شده) نتایج زیر قابل مشاهده است:

Normal_Branch_and_Cut (79803 iter, 8812.23 ticks, 21.55 sec.)
Normal_Full_Automatic_Benders (21317 iter, 1145.77 ticks, 3.21 sec.)
Normal_Annotated_benders (18909 iter, 1072.28 ticks, 2.65 sec.)

---------------------------------

منبع : ortimes.ir