ورود به حساب کاربری

نام کاربری *
رمز عبور *
یاداوری

الگوریتم تجزیه بندرز خودکار CPLEX

امتیاز کاربران

ستاره غیر فعالستاره غیر فعالستاره غیر فعالستاره غیر فعالستاره غیر فعال
 

 

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

 

 

توجه !
این راهنما برای کاربرانی قابل استفاده است که اشتراک نسخه‌ی ابری Decision Optimization on the Cloud شرکت IBM را تهیه نموده‌اند.

 

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

 

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

شرکت دانش بنیان رایانش سریع هزاره ایرانیان به منظور طراحی، ساخت و گسترش کاربردهای رایانش سریع در علوم مختلف پایه گذاری شده است. این شرکت به دنبال ایجاد بستری با ظرفیت محاسباتی و ذخیره سازی بالا مبتنی بر CPU و GPU می باشد تا بتواند از آن طریق سرویسهای متعددی را به محققین، اساتید، دانشجویان تحصیلات تکمیلی و سایر علاقه مندان این حوزه ارائه نماید.

 

سایت مرتبط : " بنیاد توسعه رایانش سریع و ابری "

 

 

آخرین مقالات

کامپایل و نصب mfix-2016.1

درک عملکرد دستگاه های انرژی، محیط زیست و فرایندها...

ماشین هوشمند بدون کمک انس...

یک ماشین هوشمند با حل معمای مکعب روبیک بدون هیچ آم...

معرفی lammps

اصطلاح شناسی شبیه ساز: فراهم کننده ی بستری برای شب...

آموزش نرم افزار amber (زب...

در اینجا تعدادی از آموزش های آماده شده توسط توسعه...

HPC Moves to the Cloud –...

While some domains that rely on computing systems...

یکسان سازی یا نرمال سازی...

در متن کاوی منظور از پردازش زبان طبیعی (NLP)، قابل...

پردازش متن با Jhazm نسخه...

jHazm نسخه جاوایی هضم از کتابخانه پایتون برای پردا...

Why Demand for In-Memory...

The demand for in-memory computing (IMC) and new...

آموزش عملی گراف کاوی و تح...

networkx یک بسته پایتون برای ایجاد، دستکاری و مطا...

معرفی مختصر مدل اقلیمی CW...

CWRF نسخه توسعه یافته اقلیمی مدل WRF می باشد که د...

بالاخره بعد از سالها یکه...

از سال 2013، ماشین های چینی در رتبه قدرتمندترین اب...

کاربردها و خطرات کلان داد...

داده شامل اطلاعات است؛ اما این همه‌ي ماجرا نیست....

Case Study: Supercomputin...

Hyperion Research has published a new case study...

داده کاوی بزرگ مقرون به ص...

چکیده : کاوش داده ی بزرگ، اغلب نیازمند منابع محاس...

Python: Unlocking the Pow...

The programming language Python is being used to...

Opportunities Abound: HPC...

The is the first entry in a five-part insideHPC s...

آموزش کد محاسباتی سیستا (...

در این آموزش سعی داریم انرژی کل و طول پیوند مولکو...

درمورد مدل‌های آب و هوایی...

دو اصطلاح اقلیم‌شناسی و هوا‌شناسی بیشتر مواقع به‌ج...

الگوریتم تجزیه بندرز خودک...

در نسخه‌ی ۱۲٫۷ نرم‌افزار CPLEX رویه‌ی جدیدی جایگز...

نرم افزار tecplot

معرفی : Tecplot در واقع یک ابزار تجسمی و رسم نمودا...

تجزیه گر یا پارسر متون و...

آپاچی تیکا: آپاچی تیکا یکی از پروژه‌های متن باز A...

OpenFOAM v5 User Guide: I...

This guide accompanies the release of version 5.0...

OpenFOAM User Guide - Ver...

Introduction The OpenFOAM User Guide provides an...

How to Prepare Weather an...

In this video from the NVIDIA GPU Technology Conf...

مثالی از داده کاوی و تحلی...

در این پست یک تحلیل و بصری سازی خوب از گراف ۶۰،۰۰...

نرم افزار سیپلکس

معرفی : Cpelx یک بسته ی نرم افزاری شامل مجموعه ای...

تلاش AMD برای ساخت تراشه‌...

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

معرفی، آموزش و لینک دانلو...

معرفی : ابزاری به منظور آنالیز فنی و طراحی کامپیوت...

Neurala Reduces Training...

Today Neurala announced a breakthrough update to...

با 10 باور نادرست در ارتب...

برای آنکه اطمینان حاصل کنید برنامه‌های سازمان شما...

گالری تصاویر