Exact approaches for the knapsack problem with setups

ما یک تعریف از مشکل حلقه ای را در نظر می گیریم که در آن اقلام به کلاس تقسیم می شوند، هر کدام با هزینه ثابت و ظرفیت مشخص می شوند. ما سه فرمول بندی برنامه نویسی صحیح خطی جایگزین را مطالعه می کنیم. برای هر فرمول بندی، ما یک الگوریتم کارآمد برای محاسبه آرام سازی برنامه ریزی خطی (یکی از آنها بر اساس تکنیک های ستون ستون) طراحی شده است. ما از لحاظ نظری توانایی آرامش را مقایسه می کنیم و نتایج خاصی را برای یک پرونده مربوطه که در موارد معین از ادبیات مطرح است، می گیریم. در نهایت، ما الگوریتم های فوق را به یک طرح شمارش ضرایب یکپارچه جاسازی می کنیم که به صورت موازی با یک الگوریتم پیشرفته پویا برنامه ریزی شده به طور موثر برای بهینه سازی مشکل حل می شود. یک تجزیه و تحلیل محاسباتی وسیع نشان می دهد که الگوریتم دقیق جدید ما قادر است به طور موثر حل تمام موارد ادبیات را ارائه دهد و بهترین نمونه برای تعداد نمونه هایی از کلاس ها باشد.