Computational experience using an edge search algorithm for linear reverse convex programs. (English) Zbl 0868.90092
Summary: This paper presents computational experience with a rather straight forward implementation of an edge search algorithm for obtaining the globally optimal solution for linear programs with an additional reverse convex constraint. The paper’s purpose is to provide a collection of problems, with known optimal solutions, and performance information for an edge search implementation so that researchers may have some benchmarks with which to compare new methods for reverse convex programs or concave minimization problems. There appears to be nothing in the literature that provides computational experience with a basic edge search procedure. The edge search implementation uses a depth first strategy. As such, this paper’s implementation of the edge search algorithm is a modification of Hillestad’s algorithm. A variety of test problems is generated by using a modification of the method of Sung and Rosen, as well as a new method that is presented in this paper.
Keywords:
global optimization; test problem generation; edge search algorithm; additional reverse convex constraintReferences:
| [1] | Avriel, M. and Williams, A.C. (1970), Complementary Geometric Programming, SIAM Journal of Applied Mathematics 19, 125-141. · Zbl 0319.90035 · doi:10.1137/0119011 |
| [2] | Avriel, M. and Williams, A.C. (1971). An Extension of Geometric Programming with Applications in Engineering Optimization, Journal of Engineering Mathematics 5, 187-194. · doi:10.1007/BF01535411 |
| [3] | Bansal, P.P. and Jacobsen, S.E. (1975), Characterization of Basic Solutions For a Class of Nonconvex Programs, Journal of Optimization Theory and Applications 15, 549-564. · Zbl 0281.90078 · doi:10.1007/BF00933745 |
| [4] | Bansal, P.P. and Jacobsen, S.E. (1975), An Algorithm for Optimizing Network Flow Capacity under Economies-of-Scale, Journal of Optimization Theory and Applications 15, 565-586. · Zbl 0281.90077 · doi:10.1007/BF00933746 |
| [5] | BenSaad, S. and Jacobsen, S.E. (1990), A Level Set Algorithm for a Class of Reverse Convex Programs, Annals of Operations Research 25, 19-42. · Zbl 0714.90078 · doi:10.1007/BF02283685 |
| [6] | Benson, H.P. and Sayin, S. (1994), A Finite Concave Minimization Algorithm Using Branch and Bound and Neighbor Generation, Journal of Global Optimization 5(1), 1-14. · Zbl 0819.90068 · doi:10.1007/BF01096999 |
| [7] | Floudas, C.A. and Pardalos, P.M. (1990), A Collection of Test Problems for Constrained Global Optimization Algorithms, Springer-Verlag, Lecture Notes in Computer Sciences 455. · Zbl 0718.90054 |
| [8] | Gurlitz, T.R. and Jacobsen, S.E. (1991), On the Use of Cuts in Reverse Convex Programs, Journal of Optimization Theory and Application 68 (2). · Zbl 0699.90085 |
| [9] | Hillestad, R.J. and Jacobsen, S.E. (1980), Linear Programs with an Additional Reverse-Convex Constraint, Journal of Applied Mathematics and Optimization 6, 257-269. · Zbl 0435.90065 · doi:10.1007/BF01442898 |
| [10] | Hillestad, R.J. and Jacobsen, S.E. (1980), Reverse-Convex Programming, Journal of Applied Mathematics and Optimization 6, 63-78. · Zbl 0448.90044 · doi:10.1007/BF01442883 |
| [11] | Hillestad, R.J. (1975), Optimization Problems Subject to a Budget Constraint with Economies of Scale, Operations Research, Journal of Applied Mathematics and Optimization 23 (6), 1091-1098. · Zbl 0335.90039 |
| [12] | Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin-New York. · Zbl 0704.90057 |
| [13] | Horst, R. and Thoai, N.V. (1989), Modification, Implementation and Comparison of Three Algorithms for Globally Solving Linearly Constrained Concave Minimization Problems, Computing 42, 271-289. · Zbl 0675.65063 · doi:10.1007/BF02239754 |
| [14] | Kalantari, B. and Rosen, J.B. (1986), Construction of Large-Scale Global Minimum Concave Quadratic Test Problems, Journal of Optimization Theory and Applications 48, 303-313. · Zbl 0559.90066 · doi:10.1007/BF00940675 |
| [15] | Moshirvaziri, K. (1994), A Generalization of the Construction of Test Problems for Nonconvex Optimization, Journal of Global Optimization 5(1), 21-34. · Zbl 0824.90114 · doi:10.1007/BF01097001 |
| [16] | Moshirvaziri, K. (1994), Construction of Test Problems for a Class of Reverse Convex Programs, Journal of Optimization Theory and Applications 81(2), 343-354. · Zbl 0819.90075 · doi:10.1007/BF02191668 |
| [17] | Pardalos, Panos M. (1987), Generation of Large-Scale Quadratic Programs for Use as Global Optimization Test Problems, ACM Transaction on Mathematical Software 13 (2), 143-147. · Zbl 0625.90080 · doi:10.1145/328512.328516 |
| [18] | Rosen, J.B. (1966), Iterative Solution of Non-linear Optimal Control Problems, SIAM Journal of Control 4, 223-244. · Zbl 0229.49025 · doi:10.1137/0304021 |
| [19] | Rosen, J.B. (1983), Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain, Mathematics of Operations Research 8, 215-230. · Zbl 0526.90072 · doi:10.1287/moor.8.2.215 |
| [20] | Sung, Y. and Rosen, J.B. (1982), Global Minimum Test Problem Construction, Mathematical Programming 24, 353-355. · Zbl 0509.90067 · doi:10.1007/BF01585116 |
| [21] | Thuong, Nguyen Van and Tuy, Hoang (1985), A Finite Algorithm for Solving Linear Programs with an Additional Reverse Convex Constraint, Springer-Verlag, Lecture Notes in Economics and Mathematical Systems 225, 291-302. · Zbl 0581.90071 |
| [22] | Tuy, Hoang (1987), Convex Programs with an Additional Reverse Convex Constraint, Journal of Optimization Theory and Applications 52(3), 463-485. · Zbl 0585.90071 · doi:10.1007/BF00938217 |
| [23] | Tuy, Hoang (1985), A General Deterministic Approach to Global Optimization via D.C. Programming, In: Hiriart-Urruty, J.B. (ed.), Fermat Days: Mathematics for Optimization, Elsevier, Amsterdam, 137-162. |
| [24] | Ueing, U. (1972), A Combinatorial Method to Compute a Global Solution of Certain Non-convex Optimization Problems, in Numerical Methods for Nonlinear Optimization, F.A. Lootsma (ed.), Academic Press, 223-230. · Zbl 0267.90088 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
