臺灣博碩士論文加值系統

Mixed-integer nonlinear programming (MINLP) problems have been intensively studied in the last decades due to its theoretical interest and its wide applicability. Several strategies and software for solving nonconvex MINLP problems have been proposed. Although many optimization approaches have been developed for MINLP problems, these methods can only find a local or approximate solution or use too many extra binary variables and constraints to reformulate the problem. Therefore, this study proposes a method for solving an MINLP problem in engineering optimization to obtain a global solution. The MINLP problem is transformed into a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the MINLP problem can then be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.

Mixed-integer nonlinear programming (MINLP) problems have been intensively studied in the last decades due to its theoretical interest and its wide applicability. Several strategies and software for solving nonconvex MINLP problems have been proposed. Although many optimization approaches have been developed for MINLP problems, these methods can only find a local or approximate solution or use too many extra binary variables and constraints to reformulate the problem. Therefore, this study proposes a method for solving an MINLP problem in engineering optimization to obtain a global solution. The MINLP problem is transformed into a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the MINLP problem can then be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.

ABSTRACT……………………..……………………………………………………………….i
ACKNOWLEDGEMENTS……..……………………..……………………………………….ii
Contents……………………..………………………………………………………………......iii
LIST OF FIGURES……………………..…………………………………………..……….iv
LIST OF TABLES……………………..…………………………………………..…………..v
Thesis organization……………………..…………………………………………………..…….vi
Chapter 1 Introduction……………………..…………………………………………………1
1-1. Background…………………….…..…………………………………………...……1
1-2. Motivations and objectives…………..………………..………………………….….1
Chapter 2 Literature Review……………………..……………………………………………3
2-1. Mixed integer nonlinear programming……………………..………………………3
2-2. Engineering optimization……………………..………………………………..…..4
2-3. Convexification strategies and piecewise linearization technique…………………5
Chapter 3 Methodology………………….…..………………………………………………..…6
3-1. Identification of convex terms and convex relaxation strategies…...………… 6
3-2. Piecewise linearization techniques...………………….…….…………...9
3-3. Solution Procedure…………………….……………………………………11
Chapter 4 Engineering Optimization examples……………..………………..…………13
4-1. A pressure vessel design.………………...………………………………….13
4-2. Tension/compression string design problem…………..………………………17
4-3. Heat exchanger design…….…………………………..………………..……...21
4-4. Speed Reducer………………..…………………………………………….24
Chapter 5 Discussions and Conclusions ………….……..…………………………………30
5-1. Future Direction………………..……………………………………30
REFERENCES………………………........................................................................................... …...32

Arora, J.S. Introduction to Optimum Design. McGraw-Hill,New York; 1989.

Belegundu, A.D. A study of mathematical programming methods for structural optimization. Department of Civil and Environmental Engineering, University of Iowa, Iowa City, Iowa; 1982.

Björk, K.M., Lindberg, P.O., Westerlund, T. Some convexifications in global optimization of problems containing signomial terms, Computers and Chemical Engineering2003;27:669-679, 2003.

Borchers, B., Mitchell, J.E. An improved branch and bound algorithm for mixed integer nonlinear programs, Computers and Operations Research 1994;21:4:359-367.

Bazara, M.S.,H.D. Sherali, C.M.Shetty. Nonlinear programming_theory and algorithums,2nd ed. John Wiley& Sons, New York; 1993.

Cardoso, M.F., Salcedo RL, Azevedo SF, Barbosa D. A simulated annealing approach to the solution of MINLP problems. Computers and Chemical Engineering 1997;21:1349–64.

Chen, TY.,Hsu Y S., A multiobjective optimization solver using rank-niche evolution strategy. Journal of science direct 2005; 684-699.

Cheung, BKS., Langevin A, Delmaire H. Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems. Computers and Mathematics with Applications 1997;32:13–23.

Coello, C.A.C. Use of a self-adaptive penalty approach for engineering optimization problems. Computers in Industry 41, 2000;113–127.

Coello, C.A.C. Theoretical and numerical constraint handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer Methods in Applied Mechanics and Engineering 191 (11/12), 2002; 1245–1287.
Coello, C.A.C., Montes, E.M. Constraint-handling in genetic algorithms through the use of dominance-based tournament selection. Advanced Engineering Informatics 16, 2002;193–203.

Costa L, Oliveria P. Evolutionary algorithms approach to the solution of mixed integer nonlinear programming problems. Computers and Chemical Engineering 2001;21:257–66.

Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Boston, MA;1989.

Deb K. An efficient constraint handling method for genetic algorithms. Computer Methods Apply Mechanical Engineering 2000;186:311–38.

Deep K, Singh KP, Kansal ML, Mohan C. A real coded genetic algorithm for solving integer and mixed integer optimization problems. Applied Mathematics and Computation 2009; 212:505–18.

Duran, M., Grossmann, I.E. An outer- approximation algorithm for a class of mixed integer nonlinear programs, Mathematical Programming 1986;36:307-339.

Exler O, Schittkowksi K. A trust region SQP algorithm for mixed-integer nonlinear programming. Optimization Letters 2007;1:269–80.

Fletcher, R., Leyffer, S, “Solving mixed integer nonlinear programs by outer approximation”, Mathematical Programming 1994;66: 327-349.

Geem ZW, Kim JH, Loganathan GV. A new heuristic optimization algorithm: harmony search. Simulation 2001;76(2):60–8.
Geoffrion, A.M. Generalized Benders decomposition. Journal of Optimization Theory and Applications 1972:10, 237–260.

Glover, F. Heuristic for integer programming using surrogate constraints, Decision Sciences. 1977;8 (1):156–166.
Hua Z, Huang F. An efficient genetic algorithm approach to large scale mixed integer programming problems. Applied Mathematics and Computation 2006;174:897–907.

Hillier F, Lieberman G.J. Introduction to operations research. Sixth edition, McGraw-Hill: New York;1995.

Himmelblau, DM. Applied nonlinear programming. New York: McGraw-Hill; 1972.

Joines J, Houck C. On the use of non-stationary penalty functions to solve nonlinear constrained optimization functions with GA’s. In: Proceedings of the evolutionary computation conference, poster sessions, IEEE world congress on computational intelligence, Orlando; 1994;5:79–84.

Jaberipour M., Khorram E. Two improved harmony search algorithms for solving engineering optimization problems.Communications in Nonlinear Science and Numerical Simulation 2010; 3316-31.

Holland, J.H. Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI;1975.

Jie, J., Zeng J., Han C. An extended mind evolutionary computation model for optimizations. Journal of Applied Mathematics and Computation 185:2007;1038–1049.

Kennedy J., Eberhart R. Particle swarm optimization, in: Proceedings - IEEE International Conference on Neural Networks, Perth, Australia 1995;4: 1942–1948.

Lee KS, Geem ZW. A new meta-heuristic algorithm for continues engineering optimization: harmony search theory and practice. Computer Methods Apply Mechanical Engineering 2004;194:3902–33.

Leyffer, S. Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Computational Optimization and Applications 18, 2001;295–309.

Li HL, Papalambros P. A production system for use of global optimization knowledge. ASME J Mechanical Transmissions Automatics 1985;107:277–84.

Lucidi S, Piccialli V, Sciandrone M. An algorithm model for mixed variable programming. SIAM Journal on Optimization 2005;15:1057–84.

Luo Y.Q., Yuan X.G., Liu Y.G. An improved PSO algorithm for solving non-convex NLP/MINLP problems with equality constraints. Computers and Chemical Engineering 2007;31:153–62.

Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems. Apply Mathematics Computer 2007;188:1567–79.

Michalewicz Z. Genetic algorithms, numerical optimization, and constraints. In: Eshelman L, editors. Proceedings of the sixth international conference on genetic algorithms. San Mateo: Morgan Kaufmann 1995;151–8.

Quesada, I., Grossmann, I.E.. An LP/NLP based branch and bound algorithm for convex minlp optimization problems. Computer and Chemical Engineering 16,1992; 937–947.

Sandgren E. Nonlinear integer and discrete programming in mechanical design optimization. J Mech Des ASME 1990;112(43):223–9.

Kirkpatrick S., Gelatt C., Vecchi M. Optimization by simulated annealing, Science 1983;220: 4598:671–680.

Stubbs, R.A., Mehrotra, S. A branch-and-cut method for 0–1 mixed convex programming. Mathematical Programming 86, 1999; 515–532.

Sun X.L., McKinnon, K.I.M., Li, D. A convexification method for a class of global optimization problems with applications to reliability optimization, Journal of Global Optimization 2001;21:185-199.

Taha, HH. Operations Reserch. Seventh edition, Macmillan: New York;2003.

Tsai, J.F. Global optimization for nonconvex programming problems and applications. NSC project technique report (2009).

Tsai, J.F., Li, H.L., Hu, N.Z., :Global optimization for signomial discrete programming problems in engineering design, Engineering Optimization 2002;4:613-622.

Tsai, J.F.:Global optimization for nonlinear fractional programming problems in Engineering design. Engineering optimization 37(4),2005;399-409.

Ugray Z., Lasdon L., Plummer J., Glover F., Kelly J., Marti R. A multistart scatter search heuristic for smooth NLP and MINLP problems /http://www.utexas.edu/courses/lasdon/papers.htmS; 2002.

Wah B.W. , Chen Y.X., Wang T. Simulated annealing with asymptotic convergence for nonlinear constrained optimization. Journal of Global Optimization 2007;39:1–37.

Westerlund T., Pettersson F. An extended cutting plane method for solving convex MINLP problems. Computer and Chemical Engineering 19,1995;S131–S136.

Westerlund T., Po¨rn, R. Solving pseudo-convex mixed integer optimization problems by cutting plane techniques. Optimization and Engineering 3, 2002;235–280.

Wu S.J., Chow P.T.. Genetic algorithms for nonlinear mixed discrete-integer optimization problems via meta-genetic parameter optimization. Engineering Optimization 1995;24:137–59.

Wu Z.Y., Bai, F.s.,Zhang, L.S. Convexification and concavification for a general class of global optimization problems. Journal of Global optimization 31,2005;45-60.

Yang J, Zhuang Y. An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem. Journal of Applied Soft Computing 2009;653-660.