توسعه مهارت‌های گمز و بهینه‌سازی

#part_307=e= Bounding cuts

سلام و روز بخير. طي روزهاي گذشته موضوعي را ديدم كه سوال خيلي جالبي بود و حتي براي خود من سوال شده بود كه چطور ميشه تاثير ان را در مدلسازي ديد.

موضوع اين بود كه فرض كنيد يك محدوديت به فرم زير داريم (اين نوع محدوديتها خيلي براي دوستاني كه مدلسازي ميكنند اشنا است):

sum_{i} x_{i} <= M*y

به اين محدوديتها كه ميشه جمع چندين متغيير را در قالب يك حد بالا و به كمك يك يا چند متغيير باينري محدود كرد اصطلاحا implied bound گفته ميشود. در بالا متغييرهاي x ميتونند از هر نوعي باشند و متغيير y هم باينري هست.

اين نوع محدوديتها را ميشه به دو صورت نوشت. حالت اول به فرم بالاست كه اصطلاحا aggrigate شده هستند و حالت دوم به فرم باز شده يا همان حالت عادي نوشتار محدوديت براي هر تركيب ميشه نوشته بشه.

فرض كنيد يك مسئله مكانيابي مثل FCLP يا تعيين اندازه دسته توليدي LSP داريم. اين محدوديتها در اين مسايل خيلي كاربرد دارند. نمونه هاش را ميتونيد به سادگي سرچ كنيد و ببينيد. معمولا گفته ميشه كه حالت عمومي ان كه به فرم زير هم نوشته ميشه داراي LP-relaxation بهتري هست و تايت تر هم هست.

x_{i} <= y      forall i

براي ديدن دليلش هم كافيه فرض كنيد به سادگي متغييرهاي x باينري هستند و متغيير(هاي) y هم باينري هست. انديس i هم براي 5 شمارش هست. جوابي به فرم:

x1 = 1, ... x4=1, x5 = 0
M = 5

در اين حالت اين جواب در فرم تجميعي صادق هست با فرض y=0.8 كه يك جواب غيرموجه براي مسئله اصلي هست اما در حالت دوم چنين چيزي صادق نيست. (نمونه ديگري از محدوديتهاي معتبر و قويترين نامساويها).

سوالي كه اينجا مطرح هست اين هست كه ايا همواره فرم اول (تجميعي) بدتر از فرم دوم عمل ميكند؟

در واقعيت اينطوري نيست. واقعا بسته به نوع مدلسازي و در كنار محدوديتهاي ديگر مدل ميشه اين موضوع را تست كرد و در مواردي حالت اول بهتر هست و در مواردي حالت دوم.

در پست بعدي كمي راجب نحوه برخورد سالورها با اين نوع محدوديتها صحبت ميكنيم.


با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

#part_306=e= Iff-then constraints


✅✅ پاسخ:
سلام. به كمك متغييرهاي اندكاتور z1 تا z4 و اضافه كردن معادلات زير ميتوان عبارت زير را براي دو بست اول خطي سازي كرد. براي باقي موارد نيز روش مشابه همين حالت است:

c1:  + z1 - y2 + z2 - y1 >= -1;
c2:  + x1 + 5 z2 <= 10;
c3:  - 8 x1 - 3 z3 <= -8;
c4:  + x2 + 6 z1 <= 10;
c5:  - 9 x2 - 5 z4 <= -9;
c6:  - z4 - z1 + y2 + z2 - y1 >= -2;
c7:  + z1 - y2 - z3 - z2 + y1 >= -2;
c8:  + z4 - y2 + z2 - y1 >= -1;
c9:  + z1 - y2 + z3 - y1 >= -1;
c10:  - z4 - z1 + y2 - z3 - z2 + y1 >= -3;
c11:  - z4 - z1 + y2 + z3 - y1 >= -2;
c12:  + z4 - y2 - z3 - z2 + y1 >= -2;
c13:  + z4 - y2 + z3 - y1 >= -1;

با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

#part_306=e= Iff-then constraints


⚠️⁉️ سوال:
سلام. به چه صورت ميشه معادله زير را به فرم خطي نوشت:

[y_1 = 1 <=> L_1 <= a_1/x_1 <= U_1] v [y_2 = 1 <=> L_2 <= a_2/x_2 <= U_2] v ... v [y_n = 1 <=> L_n <= a_n/x_n <= U_n]

where: 
y is binary
x is positive
a, L, and U are constants.

لطفا در صورت تمايل پاسخ هاي خودتون را به اشتراك قرار بديد.


با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

سلام دوستان. روزتون بخير.
درخصوص زمان برگزاري اين جلسه با تاريخ:

چهارشنبه اين هفته 1403/06/28 ساعت 6 تا 7:30 عصر موافق هستيد؟

دوستاني كه ثبت نام نكردند و علاقه مند هستند لطفا به اي دي داده شده پيام بدند. جلسه رايگان هست.

با تشكر

✅✅ Hands on column generation

سلام خدمت همه دوستان و اعضای محترم کانال.

⚠️⚠️: میدانیم که توسعه الگوریتم‌های حل دقیق برای مسایل بزرگ مقیاس عموما چالش برانگیز هست و نیاز به ریزه کاری بالا و دانستن برخی موضوعات و مفاهیم عمیق‌تر حوزه بهینه سازی دارد.


🔆🔆: از اینرو اگر خدا توفیق و توان بده، قصد داریم یک تا دو جلسه تخصصی پرسش و پاسخ در خصوص دو مبحث ایجاد ستون (column generation) و شاخه و قیمت (branch & price) را برگزار کنیم.

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

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

@Abbas_Omidi

🍺🍺: تلاشمون این هست که این جلسات بدون هزینه و به منظور ارتقاء سطح علمی اعضای کانال باشد.

-------------------
کانال توسعه مهارتهای بهينه سازي و گمز
@gamsbook
www.gamsbook.ir

✅✅ Supply Chain Network Design

يكي از كتب مناسب و با كيفيت درخصوص طراحي شبكه در زنجيره تامين كه عمدتا مثالهاي مناسب و تقريبا در اسكيل واقعي را دارد، كتاب (Supply Chain Network Design: Understanding the Optimization behind Supply Chain Design Projects) است.


به تازگي نويسندگان اين كتاب، سوالات و منابع ان را به همراه كدنويسي مرتبط در پايتون (و همچنين در كولب) و جهت اموزش عمومي در اين لينك منتشر كردند كه بسياري از انها واقعا ارزش ديدن و تست كردن را دارند.


✳️ به تمامي علاقه مندان توسعه شبكه پيشنهاد ميكنم حتما نگاهي به اين كتاب و مدلسازي و روشهاي حل ان داشته باشند.


کانال توسعه مهارتهای بهينه سازي و گمز
@gamsbook
www.gamsbook.ir

سلام و روز بخير دوستان.

سوالی داشتم:
درخصوص امكان تبديل يك محدوديت از نوع disjunction به نظير پوسته محدب ان ميخواستم بدونم ايا امكان تبديل بدون استفاده از bigM هم وجود دارد؟

معمولا محدوديتهاي اشتقاقي را به فرم bigM خطي سازي ميكنند كه ان هم داستانهاي خودش در تبديل و تايت بودن دارد. براي تبديل به حالت پوسته محدب هم باز بايستي از bigM استفاده كنيم. دليل ان را ميخواستم بدونم كه آیا راه دیگری هم هست؟

ممنون میشم دوستانی که در این زمینه تجربه دارند نظر بدهند.
🙏🙏

فایل تکمیلی جهت بررسی فضای جواب در سه حالت داده شده. دو حالت 2 و 3 دارای فضای جوابی با تعداد 15 ترکیب مختلف هستند و یکسان. (فایل پیوست بخش اول) و حالت 1 فضای جوابی با تعداد 75 ترکیب مختلف دارد.

واقعا وقتی میگیم کاتی تایت کننده فضا است به این مفهوم هست. اختلاف بین 15 ترکیب و 75 ترکیب در زمان حل کاملا مشهود هست.
.

#part_305=e= Iff-then constraints


⚠️⁉️ سوال:
سلام. به چه صورت ميشه معادله زير را به فرم خطي نوشت:

(x1 <= x3) or (x2 <= x3) or (x1 <= x4)
where x1, ... , x4 in {1,0}

✅✅ پاسخ:
به کمک تعریف متغییرهای باینری، عبارت شرطی فوق خطی سازی خواهد گردید.:

c1:    w1 + w2 + w3 >= 1;
c2:  - x3 + x1 + w3 <= 1;
c3:  - x3 + x2 + w2 <= 1;
c4:  - x4 + x1 + w1 <= 1;

همینطور حالت ثانویه دیگری نیز میتوان برای عبارت فوق درایو کرد:

x4 - x2 + 2*x3 - 2*x1 >= -2;

چطور کات فوق از حالت شرطی استخراج شده؟ 🧐

نکته جالبی که الان به ذهنم رسید این هست که میشه این کات را با استفاده از قاعده کاتهای چاوال-گوموری به فرم دیگری هم نوشت:

x3 + x4 - x1 - x2 >= -1;

که در ان طرفین به ضریب 2 تقسیم و عبارات کسری به عدد صحیح بالا گرد بشوند.

با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

✅✅ The Olympic 2024 games use AI to generate 3D replay

مسابقات المپیک پاریس چند روزی هست که شروع شده است. در کنار میزبانی نامناسب فرانسه که تقریبا داد همه رسانه ها را دراورده، موارد جالبی هم وجود دارد. یکی از انها استفاده تکنولوژی هوش مصنوعی برای تهیه صحنه های سه بعدی تکرارها است. این مسابقات به صورت کامل روی بستر کلود مجموعه علی بابا در حال استریم شدن هست و به کمک هوش مصنوعی به کار گرفته شده برای تحلیل تصاویر و تکرار انها به فرم سه بعدی با استفاده از روشهای ماشین لرنینگی در ترکیب با شبکه عصبی عمیق در این مجموعه، اینکار صورت میگیره.

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

✳️ امیدوارم از دیدن مسابقات لذت ببرید. (🥇🥈🥉)


کانال توسعه مهارتهای بهينه سازي و گمز
@gamsbook
www.gamsbook.ir

#part_305=e= Iff-then constraints


⚠️⁉️ سوال:
سلام. به چه صورت ميشه معادله زير را به فرم خطي نوشت:

(x1 <= x3) or (x2 <= x3) or (x1 <= x4)
where x1, ... , x4 in {1,0}

لطفا در صورت تمايل پاسخ هاي خودتون را به اشتراك قرار بديد.


با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

✅✅ A Practical Guide to Network Optimization

در مقاله پيوست كه به قلم خانم ماريانا وايدرويچ نوشته شده است و در مجله INFORMS به چاپ رسيده است، ايشان درخصوص برخي از مهمترين تصميمات مكانيابي در سطح استراتژيك و تاثير انها در نتيجه بهينه سازي انجام شده را بيان مينمايد.

در مقاله سعي گرديده است با بيان شفاف و ساده به اهميت تصميم گيري و تاثير ان بر نتيجه بهينه سازي در سطح استراتژيك پرداخته شود.

خواندن اين مقاله را به تمامي علاقه مندان حوزه طراحي شبكه پيشنهاد ميكنيم.



کانال توسعه مهارتهای بهينه سازي و گمز
@gamsbook
www.gamsbook.ir

#part_304=e= Finding a tight cut


⚠️⁉️ سوال:
سلام. فرض كنيد سيستم معادلات زير مفروض است.

آيا ميتوان برشي تعريف كرد كه حالات زير را در بر داشته باشد؟

* براي هيچ يك از چهار سيستم با جواب فوق صادق نباشد.
* تنها براي دو مورد از جوابهاي فوق صادق باشد.
* براي هر چهار سيستم صادق باشد.
* تنها براي زير سيستمهاي 1 و 4 صادق باشد.
* تنها براي زير سيستمهاي 2 و 3 صادق باشد.

✅✅ پاسخ:
1) باتوجه به شكل (1) هر محدوديتي به فرم x>1 و y>1 ميتواند در قالب چنين كاتي قرار گيرد.

2) كاتهايي نظير x=1 و y=1 در چنين دسته اي قرار دارند.

3) كاتهايي مانند x<=1 و y<=1 در اين خانواده قرار دارند.

4) كاتهايي در خانواده نامساوي هاي اشتقاقي در اين دسته قرار ميگيرند. به عنوان مثال x=y را ميتوان به عنوان دو كات اشتقاقي (x>=y or x<= y) نوشت كه دو نقطه قطري را در بر خواهد داشت. متناظر ان كات اشتقاقي (y= 1-x) است.

5) باتوجه به شكلهاي 2 و 3 و 4 و دستگاه نامعادلات ذيل ميتوان فضا را به سه نقطه تعميم داد. شرايط ذكر شده براي اين دستگاه نيز قابل بررسي است.
پليتوپ دستگاه در شكل و توسط دو معادله اول ساخته ميشود. كات سوم (محدوديت سوم) امكان برقراري حالت پنجم را نيز خواهد داشت. اگر (0و1) و (1و0) را در اين محدوديت جايگزاري كنيم به ترتيب دو محدوديت اول و حد بالاي متغيير z را نقض خواهد كرد كه نتيجه ان، برقراري حالت پنجم خواهد بود. البته بند اخر بخش چهارم نيز بيانگر همين موضوع با استفاده از كاتهاي اشتقاقي است.

x-y+z <=1
-x+y+z <=1
0.5x-0.5y+z <=1
x,y,z in {0,1}

با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

#part_304=e= Finding a tight cut


⚠️⁉️ سوال:
سلام. فرض كنيد سيستم معادلات زير مفروض است.

Ax <= b
0 <= x <= 1

و اين سيستم داراي 4 زير سيستم با جوابهاي زير است:

1) (0,0)
2) (1,0)
3) (0,1)
4) (1,1)

آيا ميتوان برشي تعريف كرد كه حالات زير را در بر داشته باشد؟

* براي هيچ يك از چهار سيستم با جواب فوق صادق نباشد.
* تنها براي دو مورد از جوابهاي فوق صادق باشد.
* براي هر چهار سيستم صادق باشد.
* تنها براي زير سيستمهاي 1 و 4 صادق باشد.
* تنها براي زير سيستمهاي 2 و 3 صادق باشد.

✳️✳️ لطفا پاسخ هاي خودتون را در صورت تمايل به اشتراك بگذاريد.


با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

#part_303=e= Mathematical Optimization (A Powerful Prescriptive Analytics Technology That Belongs In Your Data Science Toolbox)

دانش بهينه سازي به عنوان يك ابزار تحليلي (prescriptive) يك عامل مهم در تعيين و ساخت تصميمهات دقيق است.

اين ابزار در تعامل با ديگر ابزارهاي هوش مصنوعي امكان بازخوردهاي مناسبي در پاسخ به تغييرات را خواهد داشت.

فايل پيوست درخصوص نحوه به كارگيري اين ابزار در كنار هوش مصنوعي (ML) و به منظور تسهيل در تصميم گيري درخصوص سيستمهاي پيچيده و با تلفيق اين ابزارها در قالب چند مثال تشريحي، تقديم ميگردد.



با تشكر
کانال توسعه مهارتهای گمز
@gamsbook
www.gamsbook.ir

✅✅ Undrestanding fleet management

در مقاله پيوست كه به قلم اقاي احسان خدابخش نوشته شده است، درخصوص مهمترين فاكتورهاي مورد نياز جهت تخصيص و بهره برداري از ناوگان حمل و نقل و نحوه بهينه سازي انها، اشاره شده است.

خواندن اين مقاله را به تمام اعضاي علاقه مند به بهينه سازي ناوگان حمل و نقل توصيه ميكنيم.



کانال توسعه مهارتهای بهينه سازي و گمز
@gamsbook
www.gamsbook.ir

✅ همراهان گرامی ✅

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

(امیدوارم اینبار دیگه برادران روسی دست از سر ما بردارن😁)
GamsBook.ir
@GamsBook