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

In this paper, we propose a practical cut generation method based on the Chvatal-Gomory procedure for the (0, 1)-Knapsack problem with a variable capacity. For a given set N of 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 facilities that can satisfy the sum of weights of all the items in S. We first derive a class of valid inequalities for the problem using Chvatal-Gomory procedure, then analyze the associated separation problem. Based on the results, we develop an affective 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.
Publisher
한국경영과학회
Issue Date
2000-09
Language
KOR
Citation

한국경영과학회지, v.25, no.3, pp.1 - 15

ISSN
1225-1119
URI
http://hdl.handle.net/10203/71692
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 169
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0