최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.20 no.6, 2010년, pp.755 - 760
윤유림 (서울대학교 컴퓨터공학부) , 김용혁 (광운대학교 컴퓨터소프트웨어학과)
In general, Lagrangian method for discrete optimization is a kind of technique to easily manage constraints. It is traditionally used for finding upper bounds in the branch-and-bound method. In this paper, we propose a new Lagrangian search method for the 0-1 knapsack problem with multiple constrain...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
서브그래디언트 알고리즘은 무엇을 생성하기 위해 사용되나? | 그동안의 연구는 이러한 문제를 극복하려는 시도로 주로 서브그래디언트(subgradient) 알고리즘에 초점을 두어 왔다. 서브그래디언트 알고리즘은 분지 한계법을 위한 상한(upper bound)을 생성하기 위해 사용된다. 이러한 방법을 라그랑지안 완화법(Lagrangian relaxation)이라 부른다[19,25]. | |
배낭 문제는 무엇인가? | 다중 배낭 문제는 NP-완전(complete) 문제로 잘 알려진 배낭 문제의 확장된 형태로 이해할 수 있다[1]. 배낭 문제는 크기(size)와 가치(profit)를 갖는 물건(object)의 집합이 주어지면 배낭의 용량(capacity)을 넘지 않는 선에서 가치가 최대가 되도록 물건을 배낭에 담는 방법을 찾는 문제이다. 다중 배낭 문제의 경우에는 용량에 대한 제약조건이 둘 이상이 된다. | |
이 논문에서 제안한 새로운 라그랑지안 방법은 어떤 방법인가? | 그림 2는 이 논문에서 제안한 새로운 라그랑지안 방법(NLS)을 보여준다. 제안한 방법은 반복적으로 임의의 하나의 라그랑지 승수를 변화시키는 방법이다. 기존의 MO-CONS는 결정적 알고리즘인데 이는 변화시킬 라그랑지 승수가 매 단계마다 유일하게 결정되기 때문이다. |
M. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
A. Caprara, H. Kellerer, U. Pferschy, and D. Pisinger, "Approximation algorithms for knapsack problems with cardinality constraints," European Journal of Operational Research, Vol.123, pp. 333-345, 2000.
H. Kellerer and U. Pferschy, "A new fully polynomial approximation scheme for the knapsack problem," In Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 123-134, 1998.
E. L. Lawler, "Fast approximation algorithms for knapsack problems," In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pp. 206-213, 1997.
S. Sahni, "Approximate algorithms for the 0/1 knapsack problem," Journal of the ACM, Vol. 22, pp. 115-124, 1975.
C. Chekuri and S. Khanna, "A PTAS for the multiple knapsack problem," In Proceedings of the Symposium on Discrete Algorithms, pp.213-222, 2000.
P. C. Chu, A genetic algorithm approach for combinatorial optimization problems. PhD thesis, The management school, imperial college of science, London, 1997.
A. Freville and G. Plateau, "An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem," Discrete Applied Mathematics, Vol. 49, pp. 189-212, 1994.
A. M. Frieze and M. R. B. Clarke, "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses," European Journal of Operational Research, Vol. 15, pp. 100-109, 1984.
B. Gavish and H. Pirkul, "Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality," Mathematical Programming, Vol. 31, pp. 78-105, 1985.
M. J. Magazine and O. Oguz, "A heuristic algorithm for the multidimensional zero-one knapsack problem," European Journal of Operational Research, Vol. 16, pp. 319-326, 1984.
G. R. Raidl, "An improved genetic algorithm for the multiconstrained 0-1 knapsack problem," In Proceedings of the IEEE Conference on Evolutionary Computation, pp. 207-211, 1998.
M. Vasquez and J.-K. Hao, "A hybrid approach for the 0-1 multidimensional knapsack problem," In Proceedings of the 17th International Joint Conference on Articial Intelligence, pp. 328-333, 2001.
D. G. Luenberger, Optimization by Vector Space Methods. John Wiley & Sons, Inc., 1969.
G. L. Nemhauser and L. A. Wolsey, Inter and Combinatorial Optimization. John Wiley & Sons, Inc., 1988.
L. A. Wolsey, Integer Programming, John Wiley & Sons, Inc., 1998.
Y.-J. Chang and B. W. Wah, "Lagrangian techniques for solving a class of zero-one integer linear programs," In Proceedings of the Computer Software and Applications Conference, pp. 156-161, 1995.
B. Gavish, "On obtaining the 'best' multipliers for a Lagrangean relaxation for integer programming," Computers & Operations Research, Vol. 5, pp. 55-71, 1978.
D. Schuurmans, F. Southey, and R. C. Holte, "The exponentiated subgradient algorithm for heuristic boolean programming," In Proceedings of the International Joint Conferences on Artificial Intelligence, pp. 334-341, 2001.
B. W. Wah and Y. Shang, "A discrete Lagrangian-based global-search method for solving satisability problems," In D.-Z. Du, J. Gu, and P. Pardalos, editors, Satisability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 365-392. 1997.
B. W. Wah and Z. Wu, "The theory of discrete Lagrange multipliers for nonlinear discrete optimization," In Principles and Practice of Constraint Programming, pp. 28-42, 1999.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., 1990.
G. R. Raidl, "Weight-codings in a genetic algorithm for the multiconstraint knapsack problem," In Proceedings of the Congress on Evolutionary Computation, Vol. 1, pp. 596-603, 1999.
R. K. Martin, Large Scale Linear and Integer Optimization: A Unified Approach. Kluwer Academic Publishers, 1998.
M. L. Fisher, "The Lagrangian relaxation method for solving integer programming problems," Management Science, Vol. 27, No. 1, pp. 1-18, 1981.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.