서지주요정보
(A) strong cutting plane algorithm for a nonlinear knapsack problem = 다항식 목적함수를 갖는 비선형배낭문제의 절단평면 알고리듬
서명 / 저자 (A) strong cutting plane algorithm for a nonlinear knapsack problem = 다항식 목적함수를 갖는 비선형배낭문제의 절단평면 알고리듬 / Kyung-Chul Park.
발행사항 [대전 : 한국과학기술원, 1993].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8004061

소장위치/청구기호

학술문화관(문화관) 보존서고

MIE 93006

휴대폰 전송

도서상태

이용가능(대출불가)

사유안내

반납예정일

리뷰정보

초록정보

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.

본 논문은 일반화된 배낭문제의 해법을 다루고 있다. 일반화된 배낭문제는 각각의 프로젝트에 대한 필요자원의 집합이 교집합을 가질 수 있는 경우의 배낭문제가 된다. 즉, 한 가지 자원이 하나의 프로젝트에 고유한 것이 아니고, 여러 개의 프로젝트에 공통으로 작용할 수 있는 경우이다. 이 문제는 자본배분문제, 유연생산 시스템의 생산계획문제, 데이터베이스의 설계 등의 문제에 응용될 수 있다. 일반화된 배낭문제는 보통의 배낭문제와 달리 비선형의 목적함수를 가진다. 본 논문에서는 이와같은 비선형배낭문제를 0-1 정수계획법문제로 바꾸어 이 문제에 대한 절단평면 알고리듬을 제안하고 있다. 먼저 정수계획문제의 정수가능해들이 정의하는 볼록집합(convex hull)의 기본성질에 대하여 분석하고, 정수해들에 의해서는 만족되면서, 부분해들을 절단 할 수 있는 적법한 부등식들을 제안하였다. 또한, 이들 부등식들의 성질에 대해 규명하고, 이들의 유용성을 이론적으로 증명하였다. 위의 결과를 이용하여 절단평면 알고리듬을 개발하였고, 다양한 자료들에 대해 시험해 본 결과 이 알고리듬이 대형문제를 짧은 시간내에 효율적으로 해결할 수 있음이 증명되었다.

서지기타정보

서지기타정보
청구기호 {MIE 93006
형태사항 [iii], 73 p. : 삽화 ; 26 cm
언어 영어
일반주기 Appendix : Proof of proposition 14
저자명의 한글표기 : 박경철
지도교수의 영문표기 : Sung-Soo Paek
지도교수의 한글표기 : 박성수
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 72-73
주제 Mathematical analysis.
Nonlinear programming.
Nonlinear theories.
수리 계획법. --과학기술용어시소러스
절단 평면법. --과학기술용어시소러스
비선형 계획법. --과학기술용어시소러스
QR CODE

책소개

전체보기

목차

전체보기

이 주제의 인기대출도서