- 용량이 변화하는 (0, 1)-배낭문제에 대한 절단평면 생성방안
- ㆍ 저자명
- 이경식,박성수
- ㆍ 간행물명
- 韓國經營科學會誌
- ㆍ 권/호정보
- 2000년|25권 3호|pp.1-15 (15 pages)
- ㆍ 발행정보
- 한국경영과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
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.