A finite algorithm for concave minimization over a polyhedron
作者： Harold P. Benson
关键词: Cornacchia's algorithm 、 Concave function 、 Source code 、 Polyhedron 、 Linear programming 、 Algorithm 、 Mathematical optimization 、 Criss-cross algorithm 、 Mathematics 、 Feasible region 、 Algorithm design
摘要: We present a new algorithm for solving the problem of minimizing nonseparable concave function over polyhedron. The is branch-and-bound type. It finds globally optimal extreme point solution this in finite number steps. One major advantages that linear programming subproblems solved during search each have same feasible region. discuss and other disadvantages algorithm. also some preliminary computational experience we had with our computer code implementing This involved several bilinear problems code.
sci-hub.se 参考文章(20)
A. Victor Cabot, Variations on a cutting plane method for solving concave minimization problems with linear constraints Naval Research Logistics Quarterly. ,vol. 21, pp. 265- 274 ,(1974) , 10.1002/NAV.3800210206
James E. Falk, Karla R. Hoffman, A Successive Underestimation Method for Concave Minimization Problems Mathematics of Operations Research. ,vol. 1, pp. 251- 259 ,(1976) , 10.1287/MOOR.1.3.251
VAN NGUYEN, HOANG TUY, Convergent Algorithms for Minimizing a Concave Function Mathematics of Operations Research. ,vol. 5, pp. 556- 566 ,(1980) , 10.1287/MOOR.5.4.556
Hanif D. Sherali, C. M. Shetty, A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts Mathematical Programming. ,vol. 19, pp. 14- 31 ,(1980) , 10.1007/BF01581626
Manuel J. Carrillo, A RELAXATION ALGORITHM FOR THE MINIMIZATION OF A QUASICONCAVE FUNCTION ON A CONVEX POLYHEDRON Mathematical Programming. ,vol. 13, pp. 69- 80 ,(1977) , 10.1007/BF01584324
Reiner Horst, An algorithm for nonconvex programming problems Mathematical Programming. ,vol. 10, pp. 312- 321 ,(1976) , 10.1007/BF01580678
Hiroshi Konno, Maximization of a convex quadratic function under linear constraints Mathematical Programming. ,vol. 11, pp. 117- 127 ,(1976) , 10.1007/BF01580380
Giorgio Gallo, Aydin Ülkücü, Bilinear programming: An exact algorithm Mathematical Programming. ,vol. 12, pp. 173- 194 ,(1977) , 10.1007/BF01593787
Faiz A. Al-Khayyal, James E. Falk, Jointly Constrained Biconvex Programming Mathematics of Operations Research. ,vol. 8, pp. 273- 286 ,(1983) , 10.1287/MOOR.8.2.273
Katta G. Murty, Solving the Fixed Charge Problem by Ranking the Extreme Points Operations Research. ,vol. 16, pp. 268- 279 ,(1968) , 10.1287/OPRE.16.2.268