다중 선택 배낭 제약식 하에서의 오목 함수 최소화 문제
An Concave Minimization Problem under the Muti-selection Knapsack Constraint
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 연구에서는 다중 선택 배낭 모형의 최적해를 찾는 해법을 제시하고자 한다. 다중 선택은 동일한 집단에 소속된 구성원들이 동시에 선택되거나 동시에 배제되는 상황에서 관찰된다. 각 집단 간 관련성의 측정치인 오목 함수가 의사결정기준으로 설정되었다. 다중 선택은 비선형 제약식으로 모형화 되는데 일반 배낭 제약식으로 변환될 수 있다. 따라서 최적 해법 개발을 위해 오목함수 최소화 문제와 배낭 문제의 일반적인 해법들에서 채택하고 있는 분지 한계 접근법을 이용하였다. 단체상에서 오목함수를 가장 근접하게 하한추정하는 함수가 1차식이라는 사실이 한계 전략의 이론적 토대가 된다. 또한 하위 단계에서도 1차식 목적함수가 유일하게 결정되도록, 후보 단체를 두 개의 초평면에 투사시킴으로써 1차원 낮은 두 개의 하위 단체로 분할하는 방법이 분지 전략의 핵심이다. 앞으로 본 연구의 결과는 다양한 형태의 배낭 제약식 하에서의 오목 함수 최소화 문제의 해법을 개발하는데 응용될 수 있을 것이다.
Abstract
This paper defines a multi-selection knapsack problem and presents an algorithm for seeking its optimal solution. Multi-selection means that all members of the particular group be selected or excluded. Our branch-and-bound algorithm introduces a simplex containing the feasible region of the original problem to exploit the fact that the most tightly underestimating function on the simplex is linear. In bounding operation, the subproblem defined over the candidate simplex is minimized. During the branching process the candidate simplex is splitted into two one-less dimensional subsimplices by being projected onto two hyperplanes. The approach of this paper can be applied to solving the global minimization problems under various types of the knapsack constraints.
참고문헌 (17)
- B. Kalantari, "An Algorithm for Quadratic Zero-One Programs", Naval Research Logistics Quarterly, 37, pp.527~538 (1990)
- J. J. More, "On the Solution of Concave Knapsack Problem", Math. Prog, 49, pp.397~411 (1991)
- S. H. Oh, "A Branch-and-Bound Algorithm for Concave Minimization Problem with Upper Bounded Variables", International Journal of Engineering Technology, 7(2), pp.333~337 (2018)
- X. L. Sun, "Exact Algorithm for Concave Knapsack Problems: Linear Underestimation and Partition Method", Journal of Global Optimization, 33, pp.15~30 (2005)
- T. V. Tieu, "Convergent Algorithms for Minimizing a Concave Function", Acta Mathematica Vietnamica, 5, pp.106~113 (1978)
- J. E. Falk, "A Successive Underestimation Method for Concave Minimization Problems", Math. Opns. Res, 1, pp.251~259 (1976)
- R. M. Soland, "Optimal Facility Location with Concave Costs", Opns. Res, 22, pp.373~382 (1974)
- H. P. Benson, "Deterministic Algorithms for Constrained Concave Minimization: A Unified Critical Survey", Naval Research Logistics Quarterlyl, 43, pp.756~795 (1996)
- 홍진근, "Review on Security Communication Environment in Intelligent Vehicle Transport System", 융합정보논문지, 7(6), pp.97~102 (2017), 중소기업융합학회[DOI]
- 정윤수, "블록 체인 기반의 다중 그룹 요소를 이용한 사용자 프라이버시 관리 모델", 융합정보논문지, 8(5), pp.107~113 (2018), 중소기업융합학회[DOI]
- S. H. Oh, "An Algorithm for Globally Minimization of a Linearly Constrained Concave Function over a Parallelepiped", European Journal of Scientific Research, 123(4), pp.404~411 (2014)
- H. P. Benson, "A Finite Algorithm for Concave Minimization over a Polyhedron", Naval Research Logistics Quarterly, 32, pp.165~177 (1985)
- 최민욱, "A Study on the Equity of Regulation in Advertising", 디지털융복합연구, 16(11), pp.275~280 (2018), 한국디지털정책학회[DOI]
- R. Horst, "A General Class of Branch-and-bound Methods in Global Optimization with Some New Approachs for Concave Minimization", J. Optim. Theory Appl, 51, pp.271~291 (1986)
- 양은목, "퍼지와 인공 신경망을 이용한 침입탐지시스템의 탐지 성능 비교 연구", 디지털융복합연구, 15(6), pp.391~398 (2017), 한국디지털정책학회[DOI]
- H. Tui, "Concave Programming under Linear Constraints", Soviet Math. Dokl, 4, pp.1437~1440 (1964)
- B. Kalantari, "An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions", Math. Opns. Res, 12, pp.544~560 (1987)