A note on adapting methods for continuous global optimization to the discrete case. (English) Zbl 0723.90055
It is shown how branch and bound algorithms for solving continuous global optimization (GO) problems can be readily adapted to the discrete case. The modifications introduced take into account the discrete nature of the problems and consist of the use of rectangular partitions, which differ from the partitions used in nondiscrete GO, and special attention to the step-size of the algorithm when a rectangular element reduces to a singleton. Due to these modifications the algorithm is finite in the discrete case. In this way it is possible to obtain a variety of branch and bound algorithms for discrete concave optimization, optimization subject to reverse convex constraints, and Lipschitzian optimization).
As an illustration an algorithm for minimizing a concave function over the integers contained in a compact polyhedron is presented. Results of preliminary computational experience are reported for a FORTRAN code executing this algorithm (on an IBM 3090 400 mainframe computer using vector processing).
As an illustration an algorithm for minimizing a concave function over the integers contained in a compact polyhedron is presented. Results of preliminary computational experience are reported for a FORTRAN code executing this algorithm (on an IBM 3090 400 mainframe computer using vector processing).
Reviewer: O.A.Shcherbina (Simferopol)
MSC:
| 90C10 | Integer programming |
| 90C30 | Nonlinear programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Keywords:
branch and bound; global optimization; discrete concave optimization; reverse convex constraints; Lipschitzian optimizationReferences:
| [1] | H.P. Benson, Algorithms for parametric nonconvex programming, J. Optim. Theory Appl. 38 (1982) 319–340. · Zbl 0472.90051 · doi:10.1007/BF00935342 |
| [2] | H.P. Benson, A finite algorithm for concave minimization over a polyhedron, Naval Res. Logistics Quarterly 32 (1985) 165–177. · Zbl 0581.90080 · doi:10.1002/nav.3800320119 |
| [3] | H.P. Benson, Separable concave minimization via partial outer approximation and branch and bound, Oper. Res. Lett., to appear. · Zbl 0725.90084 |
| [4] | J.E. Falk and K.R. Hoffman, Concave minimization via collapsing polytopes, Oper. Res. 34 (1986) 919–929. · Zbl 0632.90057 · doi:10.1287/opre.34.6.919 |
| [5] | J.E. Falk and K.R. Hoffman, A successive underestimation method for concave minimization problems, Math. Oper. Res. 1 (1976) 251–259. · Zbl 0362.90082 · doi:10.1287/moor.1.3.251 |
| [6] | J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems. Management Sci. 15 (1969) 550–569. · Zbl 0172.43802 · doi:10.1287/mnsc.15.9.550 |
| [7] | K.R. Hoffman, A method for globally minimizing concave functions over convex sets, Math. Programming 20 (1981) 22–32. · Zbl 0441.90096 · doi:10.1007/BF01589330 |
| [8] | R. Horst An algorithm for nonconvex programming problems, Math. Programming 10 (1976) 312–321. · Zbl 0337.90062 · doi:10.1007/BF01580678 |
| [9] | R. Horst, Deterministic global optimization with partition sets whose feasibility is not known. Application to concave minimization, reverse convex constraints, d.c.-programming and Lipschitzian optimization, J. Optim. Theory Appl. 58 (1988) 11–37. · Zbl 0621.90064 · doi:10.1007/BF00939768 |
| [10] | R. Horst, Deterministic global optimization: recent advances and new fields of application, Naval Res. Logistics 37 (1990) 433–471. · Zbl 0709.90093 · doi:10.1002/1520-6750(199008)37:4<433::AID-NAV3220370403>3.0.CO;2-2 |
| [11] | R. Horst, A general class of branch and bound methods in global optimization with some new approaches for concave minimization, J. Optim. Theory Appl. 51 (1986) 271–291. · Zbl 0581.90073 · doi:10.1007/BF00939825 |
| [12] | R. Horst, N.V. Thoai and H.P. Benson, Concave minimization via conical partitions and polyhedral outer approximation, Math. Programming, to appear. · Zbl 0734.90092 |
| [13] | R. Horst and H. Tuy,Global Optimization: Deterministic Approaches (Springer, Berlin, 1990). · Zbl 0704.90057 |
| [14] | R. Horst and H. Tuy, On the convergence of global methods in multiextremal optimization, J. Optim. Theory Appl. 54 (1987) 253–271. · Zbl 0595.90079 · doi:10.1007/BF00939434 |
| [15] | H. Konno, Maximization of convex quadratic function subject to linear constraints, Math. Programming, 11 (1976) 117–127. · Zbl 0355.90052 · doi:10.1007/BF01580380 |
| [16] | P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications (Springer, Berlin, 1987). · Zbl 0638.90064 |
| [17] | C.D. Pegden and C.C. Petersen, An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions, Naval Res. Logistics Quarterly 26 (1979) 595–609. · Zbl 0496.90061 |
| [18] | H. Tuy and R. Horst, Convergence and restart in branch-and-bound algorithms for global optimization: application to concave minimization and d.c. optimization problems, Math. Programming 41 (1988) 161–183. · Zbl 0651.90063 · doi:10.1007/BF01580762 |
| [19] | H. Tuy, T.V. Thieu and N.Q. Thai, A conical algorithm for globally minimizing a concave function over a closed convex set, Math. Oper. Res. 10 (1985) 498–514. · Zbl 0579.90078 · doi:10.1287/moor.10.3.498 |
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.
