An outer-approximation algorithm for a class of mixed-integer nonlinear programs.(English)Zbl 0619.90052
The authors present an outer-approximation algorithm for solving mixed- integer nonlinear programming problems of a particular class. Linearity of the integer variables, and convexity of the nonlinear functions involving continuous variables are the main features in the underlying mathematical structure. Based on principles of decomposition, outer- approximation and relaxation, the proposed algorithm effectively exploits the structure of the problems, and consists of an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program. Convergence and optimality properties of the algorithm are presented, as well as a general discussion on its implementaion. Numerical results are reported for several example problems to illustrate the potential of the proposed algorithm for problems in the class addressed in this paper. Finally, a theoretical comparison with generalized Benders decomposition is presented on the lower bounds predicted by the relaxed master programs.
Reviewer: M.Savelsbergh
MSC:
| 90C11 | Mixed integer programming |
| 90C30 | Nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
computer-aided design;outer-approximation;mixed-integer nonlinear programming;decomposition;relaxation;Convergence;optimality propertiesCite
Full Text:DOI
References:
| [1] | S. Albers and K. Brockhoff, ”A procedure for new product positioning in an attribute space”,European Journal of Operational Research 1 (1977) 230–238. ·Zbl 0366.90038 ·doi:10.1016/0377-2217(77)90092-3 |
| [2] | E. Balas, ”A duality theorem and an algorithm for (mixed-) integer nonlinear programming”,Linear Algebra and its Applications 4 (1971) 341–352. ·Zbl 0225.90032 ·doi:10.1016/0024-3795(71)90005-X |
| [3] | E. Balas, ”Disjunctive programming”, in: P.L. Hammer, E.L. Johnson and B.H. Korte, eds.,Annals of Discrete Mathematics 5: Discrete Optimization II (North-Holland, Amsterdam, 1979) pp. 3–51. ·Zbl 0409.90061 |
| [4] | E. Balas and R. Jeroslow, ”Canonical Cuts on the Unit Hypercube”,SIAM Journal of Applied Mathematics 23 (1972) 61–79. ·Zbl 0237.52004 ·doi:10.1137/0123007 |
| [5] | J. F. Benders, ”Partitioning procedures for solving mixed-variables programming problems”,Numerische Mathematik 4 (1962) 238–252. ·Zbl 0109.38302 ·doi:10.1007/BF01386316 |
| [6] | D.P. Bertsekas, G.S. Lauer, N.R. Sandell, Jr., and T.A. Posbergh, ”Optimal short-term scheduling of large-scale power systems”,IEEE Transactions on Automatic Control AC-28 (1983) 1–11. ·Zbl 0522.90054 ·doi:10.1109/TAC.1983.1103136 |
| [7] | J.A. Bloom, ”Mathematical generation planning models using decomposition and probabilistic simulation”, Special Report No. EA-2566-SR, Electric Power Research Institute, Palo Alto, California (August 1982). |
| [8] | J.A. Bloom, ”Solving an electricity generating capacity expansion planning problem by generalized Benders’ decomposition”,Operations Research 31 (1983) 84–100. ·Zbl 0495.90049 ·doi:10.1287/opre.31.1.84 |
| [9] | A.L. Brearley, G. Mitra and H.P. Williams, ”Analysis of mathematical programming problems prior to applying the simplex algorithm”,Mathematical Programming 8 (1975) 54–83. ·Zbl 0317.90037 ·doi:10.1007/BF01580428 |
| [10] | H. Crowder, E.L. Johnson and M.W. Padberg, ”Solving large-scale zero-one linear programming problems”,Operations Research 31 (1983) 803–834. ·Zbl 0576.90065 ·doi:10.1287/opre.31.5.803 |
| [11] | M.A. Duran, ”A mixed-integer nonlinear programming approach for the systematic synthesis of engineering systems”, Ph.D. Thesis, Department of Chemical Engineering, Carnegie-Mellon University (Pittsburgh, PA, December 1984). |
| [12] | M.A. Duran and I.E. Grossmann, ”An outer-approximation algorithm for a class of mixed-integer nonlinear programs. The relation with generalized Benders decomposition”, Technical Report DRC-06-68-84, Design Research Center, Carnegie-Mellon University, (Pittsburgh, PA, December 1984). |
| [13] | M. A. Duran and J. E. Grossmann, ”A mixed-integer nonlinear programming algorithm for process systems synthesis”,American Institute of Chemical Engineers Journal, 32 (1986) 592–606. |
| [14] | B.C. Eaves and W.I. Zangwill, ”Generalized cutting plane algorithms”,SIAM Journal on Control 9 (1971) 529–542. ·doi:10.1137/0309037 |
| [15] | J. Elzinga and T.G. Moore, ”A central cutting plane algorithm for the convex programming problem”,Mathematical Programming 8 (1975) 134–145. ·Zbl 0318.90048 ·doi:10.1007/BF01580439 |
| [16] | J.F. Faccenda and S. Debashish, ”Computational experiments with a nonlinear 0–1 powerhouse optimization model”, paper presented at the ORSA/TIMS Joint National Meeting, Orlando, FL (November 1983). |
| [17] | R.S. Garfinkel and G.L. Nemhauser,Integer Programming (John Wiley & Sons, New York, 1972). |
| [18] | B. Gavish, D. Horsky and K. Srikanth, ”An approach to the optimal positioning of a new product”,Management Science 29 (1983) 1277–1297. ·Zbl 0526.90056 ·doi:10.1287/mnsc.29.11.1277 |
| [19] | A.M. Geoffrion, ”Elements of large-scale mathematical programming, Parts I and II”,Management Science 16 (1970), 652–691. ·Zbl 0209.22801 ·doi:10.1287/mnsc.16.11.652 |
| [20] | A.M. Geoffrion, ”Generalized Benders decomposition”,Journal of Optimization Theory and Applications 10 (1972) 237–260. ·Zbl 0229.90024 ·doi:10.1007/BF00934810 |
| [21] | F. Glover, ”Surrogate constraints”,Operations Research 16 (1968), 741–749. ·Zbl 0165.22602 ·doi:10.1287/opre.16.4.741 |
| [22] | R.E. Gomory, ”Some polyhedra related to combinatorial problems”,Linear Algebra and its Applications 2 (1969) 451–558. ·Zbl 0184.23103 ·doi:10.1016/0024-3795(69)90017-2 |
| [23] | C. Gonzaga and E. Polak, ”On constraint dropping schemes and optimality functions for a class of outer approximations algorithms”,SIAM Journal of Control and Optimization 17 (1979) 477–493. ·Zbl 0412.90059 ·doi:10.1137/0317034 |
| [24] | G.W. Graves, ”Water pollution control”, in: A.V. Balakrishnan, ed.,Techniques of Optimization (Academic Press, New York, 1972) pp. 499–509. |
| [25] | I.E. Grossman, ”Mixed-integer programming approach for the synthesis of integrated process flow-sheets”,Computers and Chemical Engineering 9 (1985) 463–482. ·doi:10.1016/0098-1354(85)80023-5 |
| [26] | G. Gunawardane, S. Hoff and L. Schrage, ”Identification of special structure constraints in linear programs”,Mathematical Programming 21 (1981) 90–97. ·Zbl 0467.90045 ·doi:10.1007/BF01584231 |
| [27] | O.K. Gupta, ”Branch and bound experiments in nonlinear integer programming”, Ph.D. Thesis, School of Industrial Engineering, Purdue University (West Lafayette, IN, December 1980). |
| [28] | O.K. Gupta and A. Ravindran, ”Nonlinear mixed integer programming and discrete optimization”, in: R.W. Wayne and K.M. Ragsdell, eds.,Progress in Engineering Optimization (ASME, New York, 1981) pp. 27–32. |
| [29] | H.H. Hoang, ”Topological optimization of networks: A nonlinear mixed integer model employing generalized Benders decomposition”,IEEE Transactions on Automatic Control AC-27 (1982) 164–169. ·Zbl 0472.90068 ·doi:10.1109/TAC.1982.1102873 |
| [30] | W.W. Hogan, ”Optimization and convergence for extremal value functions arising from structured nonlinear programs”, Working Paper No. 180. Western Management Science Institute, University of California, Los Angeles (September 1971). |
| [31] | J.E. Kelley, Jr.: ”The cutting-plane method for solving convex programs”,Journal of the Society for Industrial and Applied Mathematics 8 (1960) 703–712. ·Zbl 0098.12104 ·doi:10.1137/0108053 |
| [32] | G.S. Lauer, D.P. Bertsekas, N.R. Sandell Jr., and T.A. Posbergh, ”Solution of large-scale optimal unit commitment problems”,IEEE Transactions on Power Apparatus and Systems, PAS-101 (1982) 79–86. ·doi:10.1109/TPAS.1982.317243 |
| [33] | L.J. Leblanc, ”An algorithm for the discrete network design problems”,Transportation Science 9 (1975) 183–199. ·doi:10.1287/trsc.9.3.183 |
| [34] | J.H. May, A.D. Shocker and D. Sudharshan, ”A simulation comparison of methods for new product location”, Working paper No. 82-126, Graduate School of Business, University of Pittsburgh, Pittsburgh (October 1983). |
| [35] | D.Q. Mayne, E. Polak and R. Trahan, ”An outer approximations algorithm for computer-aided design problems”,Journal of Optimization Theory and Applications 28 (1979) 331–352. ·Zbl 0387.90094 ·doi:10.1007/BF00933378 |
| [36] | B.A. Murtagh and M.A. Saunders, ”A projected lagrangian algorithm and its implementation for sparse nonlinear constraints, and MINOS/AUGMENTED User’s Manual”, Technical Reports SOL 80-1 R and SOL 80-14, Systems Optimization Laboratory, Department of Operations Research, Stanford University, California (February 1981, June 1980). |
| [37] | R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). ·Zbl 0193.18401 |
| [38] | N.R. Sandell, Jr., D.P. Bertsekas, J.J. Shaw, S.W. Gully and R. Gendron, ”Optimal scheduling of large scale hydrothermal power systems”, in:Proceedings of the 1982 IEEE International Large Scale Systems Symposium (Virginia Beach, Virginia, October 1982) pp. 141–147. |
| [39] | L. Schrage,LP Models with LINDO (Linear Interactive Discrete Optimizer) (The Scientific Press, Palo Alto, CA, 1981). |
| [40] | J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions I (Springer-Verlag, New York, 1970). ·Zbl 0203.52203 |
| [41] | J.A. Tomlin, ”Large scale mathematical programming systems”,Computers and Chemical Engineering 7 (1983) 575–582. ·doi:10.1016/0098-1354(83)80003-9 |
| [42] | D.M. Topkis, ”Cutting-plane methods without nested constraint sets,”Operations Research 18 (1970) 404–413. ·Zbl 0205.21903 ·doi:10.1287/opre.18.3.404 |
| [43] | D.M. Topkis, ”A note on cutting-plane methods without nested constraint sets,”Operations Research 18 (1970) 1216–1220. ·Zbl 0229.90043 ·doi:10.1287/opre.18.6.1216 |
| [44] | D.M. Topkis, ”A cutting-plane algorithm with linear and geometric rates of convergence,”Journal of Optimization Theory and Applications 36 (1982) 1–22. ·doi:10.1007/BF00934337 |
| [45] | T.J. Van Roy and L.A. Wolsey, ”Valid inequalities for mixed 0–1 programs,” CORE Discussion Paper 8316 (March 1983). |
| [46] | J.A. Vaselenak, I.E. Grossmann and A.W. Westerberg, ”Optimal retrofit design of multi-product batch plants,” paper 50d presented at the American Institute of Chemical Engineers 1986 National Meeting, Houston, TX (April 1986). |
| [47] | F.S. Zufryden, ”ZIPMAP–A zero-one integer programming model for market segmentation and product positioning,”Journal of the Operational Research Society 30 (1979) 63–70. ·Zbl 0397.90050 |
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.
