본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

유효 절단 부등식을 이용한 오목함수 0-1 배낭제약식 문제의 해법
A Concave Function Minimization Algorithm Under 0-1 Knapsack Constraint using Strong Valid Inequalities

오세호    (청주대학교 산업공학과  );
  • 초록

    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,
    2. An Algorithm for Solving Separable Nonconvex Programming , Falk, J. E.;Soland, R. M. , Management Sci. / v.15,pp.550-569,
    3. On the solution of concave knapsack Problem , More, J. J.;Vavasis, S.A. , Math. Prog. / v.49,pp.397-411,
    4. A Successive Underestimation Methods for Concave Minimization Problems , Falk, J. E.;Hoffman, K L. , Math. Oper.Res. / v.1,pp.251-259,
    5. Nemhauser, G.L.;Wolsey, L.A. , Integer and Combinatorial Optimzation / v.,pp.,
    6. Concave Minimization via Collapsing Polytopes , Falk, J. E.;Hoffman, K L. , Oper. Res. / v.34,pp.919-929,
    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,
    8. A Method for Globally Minimizing Concave Functions over Convex Sets , Hoffman, K.L. , Math. Programming / v.20,pp.22-32,
    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,
    10. 0-1 배낭 제약식을 갖는 오목함수 최소화 문제의 해법 , 오세호;정성진 , 대한산업공학회지 / v.19,pp.3-13,
    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,
    12. An Algorithm for Quadratic Zero-One Programs , Kalantari, B.;Bagchi, A. , Naval Research Logisitcs Quarterly / v.37,pp.527-538,
    13. Concave Programming Under Liner Constraints , Tuy, H. , Soviet Math. Dokl. / v.5,pp.1437-1440,
    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,
    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,
    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,
    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,
    18. A finite Algorithm for Concave Minimization over a Polyhedron , Benson, H. P. , Naval Research Logistics Quarterly / v.32,pp.165-177,
    19. Deterministic Algorithms for Constrained Concave Minimization : A Unified Critical Survey , Benson, H. P. , Naval Research Logistics Quarterly / v.43,pp.756-795,

 저자의 다른 논문

  • 오세호 (13)

    1. 1987 "이자율(利子率)을 고려한 부분(部分) 부재고(負在庫) 재고(在庫) 모형(模型)에 관한 연구" 대한산업공학회지 = Journal of Korean institute of industrial engineers 13 (2): 1~8    
    2. 1993 "0-1 배낭 제약식을 갖는 오목 함수 최소화 문제의 해법" 대한산업공학회지 = Journal of Korean institute of industrial engineers 19 (2): 3~13    
    3. 1995 "강판 절단 생산에서의 CSP" 공업경영학회지 = Journal of the Society of Korea Industrial and Systems Engineering 18 (35): 47~52    
    4. 2004 "구간 공정 시간을 갖는 작업들의 일괄처리 일정계획문제" 산업경영시스템학회지 = Journal of society of Korea industrial and systems engineering 27 (1): 47~50    
    5. 2004 "노령자의 작업수행능력 평가" 산업경영시스템학회지 = Journal of society of Korea industrial and systems engineering 27 (1): 51~56    
    6. 2004 "사고 위험성을 고려한 운행중지 결정 모형" 산업경영시스템학회지 = Journal of society of Korea industrial and systems engineering 27 (4): 1~6    
    7. 2005 "동적 도착의 총 납기 지연 최소화 문제" 산업경영시스템학회지 = Journal of society of Korea industrial and systems engineering 28 (1): 92~96    
    8. 2006 "처리속도가 가변적인 작업들의 일괄처리 일정 계획 문제" 대한안전경영과학회지 = Journal of the Korea safety management & science 8 (4): 195~204    
    9. 2006 "고령화가 노동 생산성에 미치는 영향" 대한안전경영과학회지 = Journal of the Korea safety management & science 8 (2): 81~90    
    10. 2009 "좌석의 인간공학적 설계를 위한 인체 등부위 형상 정보 취득에 관한 연구" 대한안전경영과학회지 = Journal of the Korea safety management & science 11 (4): 69~75    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
  • 한국경영과학회 : 저널
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기