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

G=(N,A,C) یک شبکه جهت دار و همبند با مجموعه رئوسN و کمان های A، c بردارظرفیت وh مبدا s۱,s۲ ,…, sh و l مقصد t۱,t۲,…,tl ،و k برش و مقدار ثابت α داده شده است، در مساله معکوس کمترین برش های چند مبدا - چند مقصد با قید مقدار، ما در پی آن هستیم که با حداقل تغییرات ممکن بردار ظرفیت کمان ها، برش های داده شده با ظرفیت α کمترین برش های جداکننده ی مبداها و مقصدها از یکدیگر باشند. مهم ترین ویژگی این مساله در مقایسه با سایر مساله های معکوس کمترین برش، اضافه کردن قیدی است که در آن بایستی ظرفیت برش های داده شده برابر مقدار مفروض بشود. در این مقاله، مساله بالا تحت فاصله همینگ تنگنایی وزن دار مدل شده و یک الگوریتم چندجمله ای قوی برای حل آن ارائه شده است. الگوریتم پیشنهادی برای به دست آوردن جواب بهینه از جستجوی دودویی بهره برده و در هر تکرار یک مساله جریان شدنی را تحت قیودی مشخص حل می کند.

کلیدواژه ها:

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