- 유효 절단 부등식을 이용한 오목함수 0-1 배낭제약식 문제의 해법
- ㆍ 저자명
- 오세호
- ㆍ 간행물명
- 韓國經營科學會誌
- ㆍ 권/호정보
- 1997년|22권 3호|pp.11-22 (12 pages)
- ㆍ 발행정보
- 한국경영과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
The aim of this paper is to develop the B & B type algorithms for globally minimizing concave function under 0-1 knapsack constraint. The linear convex envelope underestimating the concave object function is introduced for the bounding operations which locate the vertices of the solution set. And the simplex containing the solution set is sequentially partitioned into the subsimplices over which the convex envelopes are calculated in the candidate problems. The adoption of cutting plane method enhances the efficiency of the algorithm. These mean valid inequalities with respect to the integer solution which eliminate the nonintegral points before the bounding operation. The implementations are effectively concretized in connection with the branching stategys.