http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
元重淵,鄭聖進 한국경영과학회 1990 韓國經營科學會誌 Vol.15 No.2
An efficient algorithm is developed for the linear programming relaxation of generalized multiple choice knapsack problem. The generalized multiple choice knapsack problem is an extension of the multiple choice knapsack problem whose relaxed LP problem has been studied extensively. In the worst case, the computational complexity of the proposed algorithm is of order 0((n·n_max)^2), where n is the total number of variables and n_max denotes the cardinality of the largest multiple choice set. The algorithm can be easily embedded in a branch-and-bound procedure for the generalized multiple choice knapsack problem. A numerical example is presented and computational aspects are discussed.
원중연 경기대학교부설 산업기술종합연구소 1998 산업기술종합연구소 논문집 Vol.15 No.-
We consider the generalized problem of the continuous multiple choice knapsack problem. The generalized problem belongs to the NP-complete class as the other IP problems, so we propose an approximate branch and bound algorithm by exploiting its generalized properties. At first, we develop an O(n²logn) search algorithm which can find good approximate solutions of relative error less than 25% from candidate problems, where n is the total number of variables. Next, by embedding the branching rule which generates the candidate problems not more than O(n), we present an approximate branch and bound algorithm which runs in polynomial time. The proposed approximate branch and bound algorithm has a computational complexity of O(n³logn) in the worst case.
元重淵 경기대학교부설 산업기술종합연구소 1989 산업기술종합연구소 논문집 Vol.5 No.-
This article is intended to present a simple heuristic approach to obtaining a good feasible approximate solution for the multidimensional zero-one knapsack problem. Theoretical aspects of this Lagrangian based heuristic are studied. Its time complexity is polynomial and an upper bound on the objective value of the optimal solution can be easily obtained.
원중연 경기대학교 1999 論文集 Vol.43 No.2
We present a two-dimensional linear knapsack problem with the box constraint. The presented Problem is an extension of the cardinality constrained linear knapsack problem[4.5] and the two-dimensional linear knapsack problem with the GUB constraint.[2] We identify some new properties of the presented problem and derive a solution algorithm based on the parametric analysis for the knapsack right-hand-side. A numerical example is given.
원중연 경기대학교 부설 산업기술종합연구소 2002 산업기술종합연구소 논문집 Vol.23 No.-
We present a heuristic algorithm for solving the 0-1 integer knapsack problem with cardinality constraint. The integer knapsack problem (P) studied in this paper is a variant of the classical knapsack problem where a cardinality is imposed on the number of items that should be selected. The heuristic algorithm is based on the LP optimal solutions, which can easily be obtained from the LP relaxed problem of (P). The heuristic algorithm searches for a feasible integer solution by rounding off the LP optimal fractional solution. It has a worst case time complexity of order O(n^2logn), where n is the number of total variables. A numerical example is given.