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. 이 논문을 인용한 문헌 없음