الگوریتم تجزیه بندرز (Benders Decomposition) کلاسیک برای مسائلی MILP ارائه شده و تجزیه بر اساس نوع متغیرها صورت میگیره و مستلزم اونه که یک زیر مسئله کاملا پیوسته باشه. اما در توسعه الگوریتم بندرز، تجزیه میتونه بر اساس ساختار ماتریس فتی نیز صورت بگیره. این حالت دوم میتونه برای هر نوع مسئله باشه. در حالتی که مسئله کاملا پیوسته باشد به الگوریتم L-Shaped معروف هست. برای مسائل کاملا عدد صحیح هم حالت دوم مستلزم تجزیه پذیر بودن مسئله بر اساس ساختار ضرایب/ماتریس فنی هست. به مثال زیر توجه کنید

min c1x1 + c2x2 + c3x3

s.t
Ax1 + Bx2<=b
Vx3 + Kx2<=u

x1 , x2 , x3 are integer

در این مسئله، ساختار ضرایب فنی به صورتی است که مسئله نسبت به متغیر x2 کاملا تجزیه پذیر است و به دو زیر مسئله کوچک تر تجزیه میشه. این نوع تجزیه رو هم چون روی متغیر صورت میگیره به افتخار پروفسور بندرز، تجزیه بندرز میگن (هرچند با فرم کلاسیک تجزیه بندرز فرق داره) دقت کنید در این مثال که عرض کردم اگر فرض کنید بعد دسته متغیرهای x1 و x3 زیاد باشه و بعد متغیر x2 کم باشه، واقعا تجزیه میتونه بسیار کارآمد باشه. یک یاداوری هم کنم اینجا اگر متغیرها همگی پیوسته بودن به تجزیه L-shaped میرسیدیم که اون هم الهام گرفته از تجزیه بندرز است و چند سال بعد از مقاله بندرز چاپ شده.

کتاب پروفسور conejo در گروه قرار داد شده که پیشنهاد میکنم مطالعه کنید.