DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Paek, Sung-Soo | - |
dc.contributor.advisor | 박성수 | - |
dc.contributor.author | Park, Kyung-Chul | - |
dc.contributor.author | 박경철 | - |
dc.date.accessioned | 2011-12-14T04:17:54Z | - |
dc.date.available | 2011-12-14T04:17:54Z | - |
dc.date.issued | 1993 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=68803&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/41391 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 산업공학과, 1993.2, [ [iii], 73 p. ] | - |
dc.description.abstract | This paper considers a generalized knapsack problem where the required sets of activities are not necessarily mutually exclusive. This problem appears in several applications including the capital budgeting problem, FMS production planning problem and database design problem. We formulate this problem as a nonlinear knapsack problem with polynomial objective function. After linearizing the nonlinear terms, we analyze the polyhedral structure of the convex hull of integral feasible solutions. Some classes of strong valid inequalities for this polytope are suggested. We show that these inequalities can define facets of the polytope under certain conditions. Additionally, we show that some subset of these inequalities is sufficient to cut off all the fractional vertices of the natural linear programming relaxation. Using these polyhedral results, we develop a strong cutting plane algorithm for the problem. The algorithm is tested on several sets of test problems. The computational result shows that this algorithm can be used to solve proatical problems in reasonable time. Moreover, this approach can be generalized to the cases where more than one type of resource constraints are needed. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | (A) strong cutting plane algorithm for a nonlinear knapsack problem | - |
dc.title.alternative | 다항식 목적함수를 갖는 비선형배낭문제의 절단평면 알고리듬 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 68803/325007 | - |
dc.description.department | 한국과학기술원 : 산업공학과, | - |
dc.identifier.uid | 000911226 | - |
dc.contributor.localauthor | Paek, Sung-Soo | - |
dc.contributor.localauthor | 박성수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.