複数制約非線形ナップザック問題に対するスマートグリーディ法

概要

論文の詳細を見る
Smart Greedy procedure is proposed for solving multi-dimensional nonlinear knapsack problems. Introducing a surrogate multiplier, the multi-dimensional nonlinear knapsack problem can be translated to a surrogate problem, which is an one-dimensional nonlinear knapsack problem. With the surrogate multiplier that is a centroid of the polyhedron of surrogate multiplier, the algorithm MA solves the surrogate problem, and then the algorithm COP optimizes the surrogate multiplier by reducing the polyhedron, repeatedly, untill the polyhedron becomes empty. Smart Greedy generates the Smart Greedy solutions of surrogate problems with the optimal surrogate multiplier. The solutions obtained are feasible to original multi-dimensional nonlinear knapsack problems. The computational experiments show that the proposed method provides high quality solutions.
岡山理科大学の論文