A finite algorithm for concave minimization over a polyhedron. (English) Zbl 0581.90080

Benson, Harold P.

Nav. Res. Logist. Q. 32, 165-177 (1985).

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.

MSC:

90C30	Nonlinear programming
65K05	Numerical mathematical programming methods

Keywords:

polyhedral domain; nonseparable concave function; branch-and-bound type; globally optimal extreme point solution; linear programming subproblems; computational experience; bilinear programming

Software:

IMSL Numerical Libraries

References:

[1]	Al-Khayyal, Mathematics of Operations Research 8 pp 273– (1983)
[2]	Altman, Bulletin de l’Academie Polonaise des Sciences 16 pp 741– (1968)
[3]	Cabot, Naval Research Logistics Quarterly 21 pp 265– (1974)
[4]	Carrillo, Mathematical Programming 13 pp 69– (1977)
[5]	”Minimization of Concave Functions Subject to Linear Constraints,” Report ORC-3, Operations Research Center, University of California, Berkeley, CA, 1972.
[6]	Falk, Mathematics of Operations Research 1 pp 251– (1976)
[7]	Falk, Management Science 15 pp 550– (1969)
[8]	Gallo, Mathematical Programming 12 pp 173– (1977)
[9]	Horst, Mathematical Programming 10 pp 312– (1976)
[10]	International Mathematical and Statistical Libraries, Inc., The IMSL Library Reference Manual, IMSL, Houston, TX, 1982.
[11]	Program for Interactive Multiple Process Simulation (PIMPS) Users Guide, mimeographed notes, Gainesville, FL, 1976.
[12]	Konno, Mathematical Programming 11 pp 14– (1976)
[13]	Konno, Mathematical Programming 11 pp 117– (1976)
[14]	Majthay, Discrete Mathematics 9 pp 35– (1974)
[15]	Murty, Operations Research 16 pp 268– (1968)
[16]	Raghavachari, Operations Research 17 pp 680– (1969)
[17]	Convex Analysis, Princeton U.P., Princeton, NJ, 1970.
[18]	Rosen, Mathematics of Operations Research 8 pp 215– (1983)
[19]	Sherali, Mathematical Programming 19 pp 14– (1980)
[20]	Soland, Operations Research 22 pp 373– (1974)
[21]	Taha, Naval Research Logistics Quarterly 20 pp 533– (1973)
[22]	Thieu, Acta Mathematica Vietnamica 5 pp 106– (1978)
[23]	Thoai, Mathematics of Operations Research 5 pp 556– (1980)
[24]	Tuy, Soviet Mathematics 5 pp 1437– (1964)
[25]	Vaish, Naval Research Logistics Quarterly 23 pp 303– (1976)
[26]	Vaish, Naval Research Logistics Quarterly 24 pp 83– (1977)
[27]	Zwart, Operations Research 22 pp 602– (1974)