$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

유효 절단 부등식을 이용한 오목함수 0-1 배낭제약식 문제의 해법

A Concave Function Minimization Algorithm Under 0-1 Knapsack Constraint using Strong Valid Inequalities

Abstract

The aim of this paper is to develop the B & B type algorithms for globally minimizing concave function under 0-1 knapsack constraint. The linear convex envelope underestimating the concave object function is introduced for the bounding operations which locate the vertices of the solution set. And the simplex containing the solution set is sequentially partitioned into the subsimplices over which the convex envelopes are calculated in the candidate problems. The adoption of cutting plane method enhances the efficiency of the algorithm. These mean valid inequalities with respect to the integer solution which eliminate the nonintegral points before the bounding operation. The implementations are effectively concretized in connection with the branching stategys.

저자의 다른 논문

참고문헌 (19)

  1. Quadratic Functions with Exponential Number of Local Maxima , Kalantari, B. , Operations Research Letters / v.5,pp.47-49, 1986
  2. An Algorithm for Solving Separable Nonconvex Programming , Falk, J. E.;Soland, R. M. , Management Sci. / v.15,pp.550-569, 1969
  3. On the solution of concave knapsack Problem , More, J. J.;Vavasis, S.A. , Math. Prog. / v.49,pp.397-411, 1991
  4. A Successive Underestimation Methods for Concave Minimization Problems , Falk, J. E.;Hoffman, K L. , Math. Oper.Res. / v.1,pp.251-259, 1976
  5. Nemhauser, G.L.;Wolsey, L.A. , Integer and Combinatorial Optimzation / v.,pp., 1988
  6. Concave Minimization via Collapsing Polytopes , Falk, J. E.;Hoffman, K L. , Oper. Res. / v.34,pp.919-929, 1986
  7. On Finding the New Verices and Redundant Constraints in Cutting Plane Algorithms for Global Optimization , Horst, R.;Thoai, N.V.;de Vries, J. , Operations Research Letters / v.7,pp.85-90, 1988
  8. A Method for Globally Minimizing Concave Functions over Convex Sets , Hoffman, K.L. , Math. Programming / v.20,pp.22-32, 1981
  9. A Branch and Bound Algorithm for a Class of Nonlinear Knapsack Problem , Mathur, K.;Salkin, H. M. , Operations Research Letters / v.2,pp.155-160, 1983
  10. 0-1 배낭 제약식을 갖는 오목함수 최소화 문제의 해법 , 오세호;정성진 , 대한산업공학회지 / v.19,pp.3-13, 1993
  11. A finite Algorithm for Concave Minimization over a Polyhedron , Benson, H. P.;Erenguc, S.S. , Naval Research Logistics Quarterly / v.37,pp.515-525, 1990
  12. An Algorithm for Quadratic Zero-One Programs , Kalantari, B.;Bagchi, A. , Naval Research Logisitcs Quarterly / v.37,pp.527-538, 1990
  13. Concave Programming Under Liner Constraints , Tuy, H. , Soviet Math. Dokl. / v.5,pp.1437-1440, 1964
  14. Branch-and-Bound Methods for Solving Systems of Nonlinear Equations and Inequaltites , Horst, R.;Thoai, N.V. , J. Optim. Theory Appl. / v.58,pp.139-146, 1988
  15. An Algorithm for a Singly Constrained Class of Quadratic Programs Subject to upper and lower Bounds , Pardalos, P. M.;Kovddr, N. , Math. Prog. / v.46,pp.321-328, 1990
  16. A General Class of Branch-and-Bound Method in Global Optimization with Some New Approaches for Concave Minimization , Horst, R. , J. Optim. Theory Appl. / v.51,pp.271-291, 1986
  17. Construction of Large-Scale Global Minimum Concave Quadratic Test Problems , Kalantari, B.;Rosen, J.B. , J. Optim. Theory Appl. / v.48,pp.303-313, 1986
  18. A finite Algorithm for Concave Minimization over a Polyhedron , Benson, H. P. , Naval Research Logistics Quarterly / v.32,pp.165-177, 1985
  19. Deterministic Algorithms for Constrained Concave Minimization : A Unified Critical Survey , Benson, H. P. , Naval Research Logistics Quarterly / v.43,pp.756-795, 1996

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일