۵

تعیین اولویت شاخه زنی برای متغیرهای عدد صحیح

اکثر سالورهایی که مسائل مرتبط با متغیرهای integer را حل می کنند، از الگوریتم شاخه و کران یا branch and bound استفاده می کنند (در صورتی که با این الگوریتم آشنایی ندارید می توانید با جستجو مقداری در مورد آن اطلاعات کسب کنید).
در این الگوریتم، در هر نقطه روی یک متغیر شاخه می زند. اینکه کدام متغیر برای شاخه زنی انتخاب شود، به صورت دیفالت توسط خود سالور انتخاب می شود. در صورتی که روی مسئله خود تسلط داشته باشید و به الگوریتم شاخه و کران اشراف داشته باشید، ممکن است متوجه شوید که مثلا در صورتی که اگر اول روی متغیر x شاخه بزنید، ممکن است روند الگوریتم صحیح تر و سریعتر ادامه پیدا کند، می توانید به این متغیر اولویت شاخه زنی دهید. این اولویت دهی یکی از ویژگی های متغیرها است که در توسط .prior مشخص می شود. مثال زیر نشان می دهد که ما به گمز دستور داده ایم که ابتدا متغیر x و سپس متغیر y(‘3’ و سپس متغیر z(i را در اولویت قرار دهد.

integer variables
x,y(j),z(i);
x.prior=1;
y.prior('3')=2;
z.prior(i)=3;

اینکه کدام متغیر باید اولویت اول باشد مسئله ای است که بسته به ساختار مسئله دارد. مثلا در مسائل مکانیابی منطقی تر است که y(k که متغیر احداث است در اولویت اول باشد و متغیر x که متغیر تخصیص است در اولویت دوم (در مکانیابی ابتدا تسهیل احداث شده و سپس نقاط تقاضا به آن تخصیص داده می شوند.)
با تشکر

گمزبوک

5 دیدگاه در “تعیین اولویت شاخه زنی برای متغیرهای عدد صحیح

  1. سلام. از روشی که گفتین استفاده کردم. خطاهای زیادی داد. مثل خطاهای زیر
    ۱۴۲- ۱۹۵-۹۶
    integer variables
    fd.prior=1;

    از سایت خوبتون ممنونم

    • سلام
      متن خطاها رو بذارین لطفا. کسی حفظ نیست این شماره ها رو. به این هم دقت کنین که قبل از اینکه fx.prior=1 رو بنویسین، اول باید خود متغیر رو تعریف کرده باشین و سپس سیمیکالون رو گذاشته باشین. بعد این خط آخرتون رو اضافه کنین.

  2. با سلام و عرض خسته نباشید….سوال من در خصوص حل گر CPLEX و ارتباط آن با الگوریتم branch-and-bound هستش…در سایت نرم افزار گمز اشاره شده که حل گر CPLEX برای حل مسایل MIP از branch-and-bound استفاده میکنه…سوال من این است که در رسیدن به پاسخ بهینه جامع نقش branch-and-bound چیه و آیا نقشی داره؟ آیا ممکنه مساله چند پاسخ بهینه داشته باشه؟ و دستور optcr و صفر کردنش چقدر در دستیابی به بهینه جامع تاثیر گذاره؟….با تشکر فراوان

    • سلام
      یعنی چی نقشش چیه؟ خب الگوریتمش اینه. از این رویه داره پیروی میکنه که زودتر به جواب برسه.
      ممکنه چند پاسخ بهینه هم داشته باشیم بله. ولی گمز یه دونه ش رو به ما نشون میده. اگه حس کردیم که جوابا ممکنه چندگانه باشه و بخوایم بقیه جوابا رو هم ببینیم، اونوقت باید یه سری حرکت بزنیم که اینا رو نشون بده. دیفالتش همچین کاری انجام نمیده.
      optcr خطا رو نشون میده. تصور بفرمایین که مسئله شما زمان بر هست. یعنی مثلا ۱۰ ساعت طول میکشه. ولی زمان توقف نرم افزار به صورت دیفالت ۱۰۰۰ ثانیه هست. پس منطقیه که مسئله به جواب کامل نمیرسه. و گمز تو ۱۰۰۰ ثانیه متوقف میشه و گپپ رو گزارش میکنه. حالا اگه بهش بگیم که زمان رو بزن رو صد هزار ثانیه و گپ هم صفر کن. شروع به حل میکنه و تا جایی حل ادامه پیدا میکنه که یکی از این دو شرط ارضا بشن. گپ اگه صفر بشه یعنی مسئله حل شده، اگه زمان تموم بشه بازم متوقف میشه ولی مقداری گپ رو گزارش میکنه.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *