روشي كارا براي كاهش فاصله ثانويه در حل نوع خاصي از مسئله كوله پشتي

An Efficient Algorithm for Reducing the Duality Gap in a Special Class of the Knapsack Problem

يكي از انواع مسئله كوله پشتي مسئله كوله پشتي جدايي پذير غير خطي نام دارد. اين مسئله به دليل كاربردهاي فراوان مورد توجه محققان قرار گرفته است. يكي از روشهاي اصلي حل اين مسئله برنامه ريزي پويا است اما به دليل آنكه فضاي متغير حالت به سرعت رشد مي‌كند مشكل ابعادي را بوجود مي‌آورد. در اين مقاله روشي كارا ارائه مي‌شود تا ضرايب جانشين را در هر مرحله از برنامه‌ريزي پويا بيابد و با اين كار مسئله اصلي را به مسئله‌ايي با يك محدوديت موسوم به مسئله جانشين تبديل كند. بر طبق نتايج محاسباتي حاصله حدود بالايي و پاييني ناشي از حل مسئله جانشين مي‌تواند متغيرهاي حالت بسياري را در برنامه ريزي پويا حذف كرده و فاصله ثانويه را به نحو چشمگيري كاهش دهد.

A special class of the knapsack problem is called the separable nonlinear knapsack problem. This problem has received considerable attention recently because of its numerous applications. Dynamic programming is one of the basic approaches for solving this problem. Unfortunately, the size of state-pace will dramatically increase and cause the dimensionality problem. In this paper, an efficient algorithm is developed to find surrogate multipliers in each stage of dynamic programming in order to transform the original problem to a single constraint problem called surrogate problem. The upper and lower bounds obtained by solving the surrogate problem can eliminate a large number of state variables in dynamic programming and extremely reduce the duality gap according to our computational results.