용량이 변화하는 (0,1)-배낭문제에 대한 절단평면 생성방안 = A Cut Generation Method for the (0,1)-Knapsack problem with a Variable Capacity

다국어 초록 (Multilingual Abstract)

In this paper, we propose a practical cut generation method based on the Chavatal-Gomory procedure for the (0,1)-Knapsack problem with a variable capacity. For a given set N or n items each of which has a positive integral weight and a facility of positive integral capacity, a feasible solution of the problem is defined as a subset S of N along with the number of valid inequalities for the problem using Chvatal-Gomory procedure, then analyze the associated separation problem. Based on the result, we develop an effective cut generation method. We then analyze the theoretical strength of the inequalities which can be generated by the proposed cut generation method. Preliminary computational results are also presented which show the effectiveness of the proposed cut generation method.