切平面在混合整数非线性规划中的应用
|
摘要
混合整数非线性规划(Mixed Integer Nonlinear Programming,MINLP)是一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的一个重要分支,近几十年来MINLP的应用有了快速的发展,其应用领域包括流程工业、金融、工程、管理科学和运筹学等各个领域。MINLP问题的求解算法包括确定型算法和启发式算法,确定型算法是将难于求解的MINLP问题分解为相对容易求解的混合整数线性规划问题(Mixed Integer Linear Programming,MILP),其中一类分解方法是通过投影及对偶等方法将MINLP问题分解为MILP问题,另外一类是利用迭代构造切平面的方法将原问题分解为简单问题。
本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究,明确切平面在确定型算法中的重要作用,利用切平面的构造方法对已知算法进行改进,并争取构造出新的算法。
本文首先给出了切平面在确定型算法中的作用,给出了切平面构造的位置和方法与各种算法收敛速度的关系,得出结论:切平面的构造影响算法的收敛速度,一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度,非线性可行域边界上构造的切平面称为支撑超平面;又MINLP问题的性质要求最优解为整数点,因此如果可以给出在整数点处快速生成支撑超平面的方法,就得到了一个简洁且收敛速度快的确定型算法。
基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式,并证明了其收敛性,同时提出了三个具体支撑超平面算法,分别为平行下降支撑超平面算法,基于内点的支撑超平面算法和不基于内点的支撑超平面算法。
外逼近(Outer Approximation,OA)算法是求解MINLP问题的一个重要算法,有着很广泛的应用,该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算法的思想引入到OA算法中,给出改进的OA算法,我们称新的算法为EOA(Extended Outer Approximation,EOA)算法。在EOA算法中,当第一个非线性规划问题无解时,利用Vinott's SHP算法生成一个支撑超平面,替换OA算法中通过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边界整数点生成切平面的优势,同时减少了NLP问题的求解次数。
启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法,确定型算法在求解MINLP问题时可以保证解的全局最优性,但对大规模问题的求解需要很长的计算时间,启发式方法不能保证解的全局最优,但求解问题时具有快速、简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法,新的算法继承了切平面方法全局收敛和启发式算法效率高的特点,并保证了算法的收敛速度和全局最优性,我们称这种算法为启发式切平面算法。
Mixed Integer Nonlinear Programming (MINLP) refers to mathematical programming with continuous and integer variables. MINLP which is an important class of Integer Programming (IP) has experience tremendous progress in recent years. MINLP have been used in various applications, including process industry, financial, engineering, management science and operations research sectors. Algorithms which are proposed for solving MINLP include deterministic methods and heuristic methods. The deterministic methods target the formulation of sub-problems that are easier to solve than the original. One main decomposition idea involves projection and duality, and another decomposition idea is based on the generating of cutting planes.
According to the study of the deterministic algorithms, we found that the cutting plane act an important role in the construction of the deterministic algorithms. Aim of present paper is to study function of cutting plane, and using cutting plane to improve or construct new algorithms. Function of cutting plane in deterministic algorithms is present first, relations of deterministic algorithms and position and method of generating cutting plane are shown following.
According to the study of cutting plane, we found that the construction of cutting plane influence convergence speed of the different method. Generally, when the cutting planes are generated at boundary of nonlinear feasible region, the algorithms has fast convergence speed. It is called supporting hyperplane, when the cutting planes are generated at boundary of nonlinear feasible region. If the supporting hyperplane can be generate easily and quickly, the algorithms are constructed with fast convergence speed. Based on the theory discussed above, three kind of supporting hyperplane algorithm are presented. Outer Approximation (OA) method is an important algorithm and widely used for solving MINLP problems. Based on the study of OA, we improved OA method and a Extended OA (EOA) is presented, the EOA method can reduce complexity of OA method.
Heuristic algorithm and deterministic algorithm are two broad classes method for solving MINLP problems. When given enough time and provide the problem satisfies certain conditions such as convexity, the deterministic algorithm can terminate with a guaranteed solution or an indication that the problem has no integer solution. If MINLP problems needed to be solved has large scale, that it becomes prohibitive to us a deterministic approach, then one has to resort to heuristic algorithm, which do not provide a guarantee that on termination the incumbent is a minimize. But heuristic algorithms, wildly applied in practical problems, are usually faster and more convenient than deterministic algorithms. At last, a kind of cutting plane method of transform the heuristic algorithms to deterministic algorithms is presented, and the new proposed method utilized the character of fast convergence speed of heuristic algorithms and the character of guaranteed solution of deterministic algorithms. The new proposed method is called heuristic cutting plane method.
本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究,明确切平面在确定型算法中的重要作用,利用切平面的构造方法对已知算法进行改进,并争取构造出新的算法。
本文首先给出了切平面在确定型算法中的作用,给出了切平面构造的位置和方法与各种算法收敛速度的关系,得出结论:切平面的构造影响算法的收敛速度,一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度,非线性可行域边界上构造的切平面称为支撑超平面;又MINLP问题的性质要求最优解为整数点,因此如果可以给出在整数点处快速生成支撑超平面的方法,就得到了一个简洁且收敛速度快的确定型算法。
基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式,并证明了其收敛性,同时提出了三个具体支撑超平面算法,分别为平行下降支撑超平面算法,基于内点的支撑超平面算法和不基于内点的支撑超平面算法。
外逼近(Outer Approximation,OA)算法是求解MINLP问题的一个重要算法,有着很广泛的应用,该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算法的思想引入到OA算法中,给出改进的OA算法,我们称新的算法为EOA(Extended Outer Approximation,EOA)算法。在EOA算法中,当第一个非线性规划问题无解时,利用Vinott's SHP算法生成一个支撑超平面,替换OA算法中通过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边界整数点生成切平面的优势,同时减少了NLP问题的求解次数。
启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法,确定型算法在求解MINLP问题时可以保证解的全局最优性,但对大规模问题的求解需要很长的计算时间,启发式方法不能保证解的全局最优,但求解问题时具有快速、简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法,新的算法继承了切平面方法全局收敛和启发式算法效率高的特点,并保证了算法的收敛速度和全局最优性,我们称这种算法为启发式切平面算法。
Mixed Integer Nonlinear Programming (MINLP) refers to mathematical programming with continuous and integer variables. MINLP which is an important class of Integer Programming (IP) has experience tremendous progress in recent years. MINLP have been used in various applications, including process industry, financial, engineering, management science and operations research sectors. Algorithms which are proposed for solving MINLP include deterministic methods and heuristic methods. The deterministic methods target the formulation of sub-problems that are easier to solve than the original. One main decomposition idea involves projection and duality, and another decomposition idea is based on the generating of cutting planes.
According to the study of the deterministic algorithms, we found that the cutting plane act an important role in the construction of the deterministic algorithms. Aim of present paper is to study function of cutting plane, and using cutting plane to improve or construct new algorithms. Function of cutting plane in deterministic algorithms is present first, relations of deterministic algorithms and position and method of generating cutting plane are shown following.
According to the study of cutting plane, we found that the construction of cutting plane influence convergence speed of the different method. Generally, when the cutting planes are generated at boundary of nonlinear feasible region, the algorithms has fast convergence speed. It is called supporting hyperplane, when the cutting planes are generated at boundary of nonlinear feasible region. If the supporting hyperplane can be generate easily and quickly, the algorithms are constructed with fast convergence speed. Based on the theory discussed above, three kind of supporting hyperplane algorithm are presented. Outer Approximation (OA) method is an important algorithm and widely used for solving MINLP problems. Based on the study of OA, we improved OA method and a Extended OA (EOA) is presented, the EOA method can reduce complexity of OA method.
Heuristic algorithm and deterministic algorithm are two broad classes method for solving MINLP problems. When given enough time and provide the problem satisfies certain conditions such as convexity, the deterministic algorithm can terminate with a guaranteed solution or an indication that the problem has no integer solution. If MINLP problems needed to be solved has large scale, that it becomes prohibitive to us a deterministic approach, then one has to resort to heuristic algorithm, which do not provide a guarantee that on termination the incumbent is a minimize. But heuristic algorithms, wildly applied in practical problems, are usually faster and more convenient than deterministic algorithms. At last, a kind of cutting plane method of transform the heuristic algorithms to deterministic algorithms is presented, and the new proposed method utilized the character of fast convergence speed of heuristic algorithms and the character of guaranteed solution of deterministic algorithms. The new proposed method is called heuristic cutting plane method.
引文
[1]Garey,M.R.,Johnson,D.S.,Computers and Intractability:A guide to the Theory of NP-completeness[z].San Francisco:W.H.Freeman and Co,1979.
[2]Karp R.M.Miller R.E.and Thatcher J.W.(editors).Reducibility Among Combinatorial Problems,in:Complexity of Computer Computations.New York:(1972) Plenum,85-103.
[3]R.Gomory,Outline of an Algorithm for Integer Solutions to Linear Programs,Bulletin of the American Mathematical Society 64(1958),275.
[4]E.Balas,S.Ceria,G.Cornu(?)jols,and N.Natraj,Gomory Cuts Revisited,Operations Research Letters 19(1996),1.
[5]R.Dakin,A Tree-Search Algorithm for Mixed Integer Programming Problems,The Computer Journal 8(1964),250
[6]E.Balas,S.Ceria,and G.Cornu(?)jols,A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs,Mathematical Programming 58(1993),295.
[7]E.Balas,S.Ceria,and G.Cornu(?)jols,Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework,Management Science 42(1996),1229.
[8]C.Barnhart,E.Johnson,G.Nemhauser,M.Savelsbergh,and P.Vance,Branch-and-Price:Column Generation for Solving Huge Integer Programs,Operations Research 46(1998),316.
[9]M.Savelsbergh,A Branch-and-Price Algorithm for the Generalized Assignment Problem,Operations Research 45(1997),831.
[10]Optimization Software for Operations Research Applications,http://www.aimms.com.
[11]A Modeling Language for Mathematical Programming,http://www.ampl.com.
[12]The World's Mathematical Programming Optimizers,www.ilog.com/products/cplex/.
[13]General Algebraic Modeling System,www.gams.com.
[14]The Language of Technical Computing,www.tomopt.com
[15]G.L.Nemhauser,L.A.Wolsey,Integer and Combinatorial Optimization,Wiley-Interscience:New York,1988.
[16]L.E.Johnson,L.George Nemhauser,Martin W.P.Savelsbergh:Progress in Linear Programming-Based Algorithms for Integer Programming:An Exposition.INFORMS Journal on Computing 12(1):2-23(2000)
[17]A.Schrijver,Theory of Linear and Integer Programming,(John Wiley,Chichester,1986)
[18]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社,2000.
[19]施光燕,董加礼.最优化方法.北京:高等教育出版社,1999.
[20]马仲番.线性整数规划的数字基础.北京:科学出版社,1998.
[21]M.Yuceer,I.Atasoy,R.Berber,A semi heuristic MINLP algorithm for production scheduling.Computer Aided Chemical Engineering,vol.14,pp.335-340,2003.
[22]M.Yuceer,R.Berber,A heuristic approach for solution of MINLP problem for production scheduling in preemptive mode.Chemical Engineering and Processing,vol.44,pp.933-940,2005.
[23]P.Bonami,and M.Lejeune,An Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints,IBM Research Report RC24215,02/2007.
[24]S.S.Syam,A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals.European Journal of Operational of Operational Research,vol.108,pp.196-207,1998.
[25]J.S.Pang,A new and efficient algorithm for a class of portfolio selection problems.Operations Research,vol.28,pp.754-767,1989.
[26]Z.Novak Pintari(?),P.Glavi(?),Integration of Flue Gas into the Process Flowsheet by Combined Pinch-MINLP Approach.Chemical Engineering Research and Design,vol.80,pp.606-614,2002.
[27]T.Farkas,E.Rev,Z.Lelkes,Process flowsheet superstructures:Structural multiplicity and redundancy:Part Ⅰ:Ideal and binarily minimal MINLP representations.Computers &Chemical Engineering,vol.29,pp.2180-2197,2005.
[28]T.Farkas,E.Rev,Z.Lelkes,Process flowsheet superstructures:Structural multiplicity and redundancy:Part Ⅱ:Ideal and binarily minimal MINLP representations.Computers &Chemical Engineering,vol.29,pp.2198-2214,2005.
[29]李荷华,钱宇,郑世清,程华农,化工过程系统综合问题新的模块化求解策略和算法.化工学报,vol.54(7),pp.972-977,2003.
[30]闫志国,钱宇,李秀喜,化工过程综合问题MINLP算法中整型变量的连续化.高校化学工程学报,2005,vol.19(5),pp.670-674,.
[31]I.E.Grossmann,M.M.Daichendt,New Trends in Optimization-based Approaches for Process Synthesis,Computers and Chemical Engineering,vol.20,pp.665-683,1996.
[32]I.E.Grossmann,J.A.Caballero and H.Yeomans,Advances in Mathematical Programming for Automated Design,Integration and Operation of Chemical Processes,Proceedings of the International Conference on Process Integration(PI'99),Copenhagen,Denmark,1999.
[33]I.E.Grossmann,Mixed-Integer Optimization Techniques for Algorithmic Process Synthesis, Advances in Chemical Engineering, Vol. 23, Process Synthesis, pp.171-246 1996.
[34]I.E. Grossmann, J. Quesada, R. Raman and V. Voudouris, Mixed Integer Optimization Techniques for the Design and Scheduling of Batch Processes, Batch Processing Systems Engineering (Eds. G.V. Reklaitis, A.K. Sunol, D.W.T. Rippin, O. Hortacsu), pp. 451-494, Springer-Verlag, Berlin, 1996.
[35]J. Pinto, and I.E. Grossmann, Assignment and Sequencing Models for the Scheduling of Chemical Processes, Annals of Operations Research, vol. 81, pp.433-466, 1998.
[36]N. Shah, Single and Multisite Planning and Scheduling: Current Status and Future Challenges, FOCAPO Proceedings, 1998.
[37]J. Kallrath, Mixed integer optimization in the chemical process industry: Experience, potential and future", Trans. I. Chem E. vol. 78, part A, pp. 809-822, 2000.
[38] Amir, H.M., Hasegawa, T. Nonlinear Mixed-Discrete Structural Optimization, Journal of Structural Engineering, vol. 115, pp. 626-646, 1989.
[39]Sandgren, E. Nonlinear Integer and Discrete Programming in Mechanical Design Optimization, Transactions of the ASME, Journal of Mechanical Design, vol. 112, pp. 223-229, 1990.
[40]Emet, S. and Westerlund,T., Comparisons of solving a chromatographic separation problem using MINLP methods ,Computers & Chemical Engineering Vol.28, pp. 673-682,2004.
[41]Thomasa, I. and Kr(?)nera, A., Mixed-integer optimization of distillation column tray positions in industrial practice, Computer Aided Chemical Engineering, Vol.21, Part 1, pp. 1015-1020, 2006.
[42] E.M.L. Beale, Integer Programming, in The State of the Art in Numerical Analysis, (Eds D.A.H. Jacobs), Academic Press, London, 1978.
[43]M. Benichou, J.M. Gauthier, P. Girodet, G. Hentges, G. Ribiere, O. Vincent, Experiments in Mixed-Integer Linear Programming, Mathematical Programming, vol. 1, pp. 76-94, 1971.
[44]R. Breu and C. A. Burdet, Branch-and-bound experiments in 0-1 programming, Mathematical Programming Study, vol. 2, pp. 1-50, 1974.
[45]R.J. Dakin, A tree search algorithm for mixed integer programming problems, Computer Journal, vol. 8, pp. 250-255, 1965.
[46]R. Fletcher, Practical Methods of Optimization, 2nd edition (Eds. John Wiley), Chichester, 1987.
[47]R.S. Garfinkel, G.L. Nemhauser, Integer Programming, (Eds. John Wiley), New York, 1972.
[48]H.Greenberg,Integer Programming,Academic Press,New York,1971.
[49]O.K.Gupta A.Ravindran,Nonlinear Integer Programming and Discrete Optimization,Transactions of the ASME,Journal of Mechanisms,Transmissions and Automation in Design vol.105,pp.160-164,1983.
[50]O.K.Gupta,A.Ravindran,Branch and bound experiments in convex nonlinear integer programming,Management Science,vol.31,pp.1533-1546,1985.
[51]F.K(?)orner,A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems,BIT,vol.28,pp.701-708,1988.
[52]A.H.Land,A.G Doig,An automatic method for solving discrete programming problems,Econometrica,vol.28,pp.497-520,1960.
[53]J.D.C.Little,K.C.Murty,D.M.Sweeney and C.Karel,An algorithm for the travelling salesman problem,Operations Research,vol.11,pp.972-989,1963.
[54]G.L.Nemhauser,L.A.Wolsey,Integer and Combinatorial Optimization,(Eds.John Wiley),New York,1988.
[55]E.Sandgren,Nonlinear Integer and Discrete Programming for Topological Decision Making in Engineering Design,Transactions of the ASME,Journal of Mechanical Design,vol.112,pp.118-122.1990.
[56]E.Sandgren,Nonlinear Integer and Discrete Programming in Mechanical Design Optimization,Transactions of the ASME,Journal of Mechanical Design,vol.112,pp.223-229,1990.
[57]H.A.Taha,Integer Programming Theory,Applications and Computations,Academic Press,London,1975.
[58]O.V.Volkovich,V.A.Roshchin,I.V.Sergienko,Models and methods of solution of quadratic integer programming problems,Cybernetics,vol.23,pp.289-305,1987.
[59]王粉兰,非线性整数规划问题的若干新算法,博士论文,运筹学与控制论,上海大学,2005.
[60]R.A.Stubbs,S.Mehrotra,A Branch and Cut Method for 0-1 Mixed Convex Programming,presented at INFORMS Meeting,Washington,1999.
[61]S.Leyffer,Integrating SQP and Branch and Bound for Mixed Integer Nonlinear Programming,Computers and Chemical Engineering,vol.18,pp.295-309,2001.
[62]J.F.Benders,Partitioning procedures for solving mixed-variable programming problems,Numerische Mathematik,vol.4,pp.238-252,1962.
[63]O.E.Flippo,A.H.G.Rinnoy Kan,G.van der Hoek,Duality and decomposition in general mathematical programming,Econometric Institute,Report 8747/B,Erasmus University Rotterdam, 1987.
[64]O.E. Flippo and A.H.G. Rinnoy Kan, A note on Benders Decomposition in mixed-integer quadratic programming, Operations Research Letters, vol. 9, pp. 81-83, 1990.
[65]O.E. Flippo and A.H.G. Rinnoy Kan, Decomposition in general mathematical programming, Mathematical Programming, vol.60, pp. 361-382, 1993.
[66]A.M. Geoffrion, Generalized Benders Decomposition, Journal of Optimization Theory and Applications, vol. 10, pp. 237-260, 1972.
[67]R. Lazimy, Mixed-integer quadratic programming, Mathematical Programming, vol. 22, pp. 332-349, 1982.
[68]R. Lazimy, Improved Algorithm for Mixed-Integer Quadratic Programs and a Computational Study, Mathematical Programming, vol. 32, pp. 100-113, 1985.
[69]N.V. Sahinidis, I.E. Grossmann, Convergence properties of generalized Benders Decomposition, Computers and chemical Engineering, vol. 15, pp. 481-491,1991.
[70]O.V. Volkovich, V.A. Roshchin, I.V. Sergienko, Models and methods of solution of quadratic integer programming problems, Cybernetics, vol. 23, pp. 289-305, 1987.
[71] M. Duran, I.E. Grossmann, An outer-approximation algorithm for a class of Mixed Integer Nonlinear Programs, Mathematical Programming, vol. 36, pp.307-339, 1986.
[72]M. Duran and I.E. Grossmann, A mixed-integer programming algorithm for process systems synthesis, American Institute of Chemical Engineers Journal, vol. 32, pp. 592-606, 1986.
[73]G. R. Kocis and I.E. Grossmann, Global Optimization of Nonconvex Mixed Integer Nonlinear Programming (MINLP) problems in Process Synthesis, Industrial Engineering Chemistry Research, vol. 27 pp. 1407-1421, 1988.
[74] G. R. Kocis I.E. Grossmann, Computational experience with DICOPT solving MINLP problems in process systems engineering, Computers and Chemical Engineering, vol. 13, NO. 3,pp.307-315, 1989.
[75]I. Quesada, I.GGrossmann, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Dept. of Chemical Engineering, Carnegie Mellon University 1992.
[76]J. Viswanathan, I.E. Grossmann, A combined penalty function and outer-approximation method for MINLP optimization, Computers and chemical Engineering, vol. 14, pp. 769-782, 1990.
[77] X. Yuan, S. Zhang L. Pibouleau and S. Domenech, Une m'ethode d'optimization non lin'eaire en variables mixtes pour la conception de precedes, Operations Research vol. 22, pp.331-346,1988.
[78]J.E.Kelley,the Cutting Plane Method for Solving Convex Programs.Journal of SIAM,vol.8,NO.4,pp.703-712,1960.
[79]T.Westerlund,F.Pettersson,an Extended Cutting Plane Method for Solving Convex MINLP Problems,Computers chem.Eng,vol.19,pp.131-136,1995.
[80]Still C.and Westerlund T.(1997).A Modified α-ECP Algorithm for Solving Quasi-Convex NLP Problems.Report 97-156-A,Process Design Laboratory,(?)bo Akademi University,ISSN 952-12-0123-1,ISBN 0783-215X.
[81]T.Westerlund,H.Skrifvars,I.Harjunkoski,R.P(o|¨)rn,An Extended Cutting Plane Method for a Class of Non-Convex MINLP Problems,Computers chem.Eng,vol.22,pp.357-365,1998.
[82]R.P(o|¨)rn,T.Westerlund,Mixed Integer Non-Linear Programming Using Cutting Plane Techniques,European Symposium on Computer Aided Process Engineering ESCAPE-10,(Eds.S.Pierucci ),Elsevier Science,vol.8,pp.1-6.2000
[83]R.P(o|¨)rn,T.Westerlund,A Cutting Plane Method for Minimizing Pseudo-Convex functions in the Mixed Integer Case,Computers chem.Eng,vol.24,pp.2655-2665,2000.
[84]P.Michelon and N.Maculan,Lagrangean decomposition for integer nlnlinear programming wirh linear constraints,Mathematical Programming 52(1991) 303-313.
[85]J.Z.Cha and R.W.Mayne,,Optimization with Discrete Variables via Recursive Quadratic Programming:Part Ⅰ,Concepts and De8nitions,"ASME,Journal of Mech.,Trans.& Auto.In Design,vol.111,pp.124-130,1989.
[86]J.Z.Cha and R.W Mayne,.(1989b),Optimization with Discrete Variables Via Recursive Quadratic Programming:Part Ⅱ,Algorithm and Results,ASME,Journal of Mech.,Trans.&Auto.In Design,vol.111,pp.130-136,1989.
[87]E.Oliver,S.Klaus,A trust region SQP algorithm for mixed-integer nonlinear programming,Optimization Letters,vol.1,pp.269-280,2007.
[88]G.R.Olsen,G.N.Vanderplaats,Method for nonlinear Optimization with discrete design variables,AIAA Journal,vol.27,pp.1584-1589,1989.
[89]S.K.Banerjee,K.Rajamani,Optimization of System Relibility Using a Parametric Approach,IEEE,Trans.Reliability,vol.22,pp.35-39,1973.
[90]M.Pappas,A.Allentuch,Mathematical Programming Procedures for Mixed Discrete Continuous Design Problems,ASME J.of Engineering for Industry,pp.201-209,1974.
[91]陈国华,廖小莲,0-1非线性混合整数规划的罚函数解法,应用数学与计算数字学报.Vol.21,No.1,pp.111-115,2007.
[92]E.G.Davydov,I.K.Sigal,Application of the Penalty Function Method in Integer Programming Problems,Engineering Cyberuetics,vol.10,pp.21-24,1972.
[93]H.L.Li,An Approximate Method for Local Optima for Nonlinear Mixed Integer Programming Problems,Computers and Operations Research,vol.19,pp.435-444,1992.
[94]R.L.Salcedo,Solving nonconvex nlnlinear programming and mixed-integer nonlinear programming problems with adaptive random search,Industrial Enginneering Chemistry Research 31(1992) 262-273
[95]丰建荣,刘正和,刘志河,王成寿,MINLP问题全局优化算法的研究,系统仿真学报,vol.17,pp.1859-1863,2005.
[96]刘芳,李人厚,基于种族优生的进化规划用于混合非线性整数规划,系统仿真学报,vol.15,pp.1076-1078,2003.
[97]刘钊,康立山,蒋良孝,杨林权,用粒子群优化改进算法求解混合整数非线性规划问题,小型微型计算机系统,vol.26,No.6,pp.991-994,2005.
[98]P.Bonami,L.Biegler,A.Conn,G.Cornuejols,I.Grossmann,C.Laird,J.Lee,A.Lodi,F.Margot,S.Nicolas,A.Waechter.An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs,Discrete Optimization,5:186-204,2008.
[99]O.Exler,K.Schittkowski,"A Computational Study of a Trust Region SOP Algorithm for Mixed-Integer Nonlinear Programming",Web:www.klaus-schittkowski.de.2006.
[100]S.Leyffer,Deterministic Methods for Mixed Integer Nonlinear Programming,Dr.Dissertation,Department of Mathematics and Computer Science,University of Dundee,Dundee,1993.
[101]C.S.Adjiman,C.A.Schweiger and C.A.Foludas,Mixed-lnteger Nonlinear Optimization in Process Sythesis(Eds.D.Z.Du,P.M.Pardalos),1998.
[102]V.Piccialli,Methods for solving Mixed Variable Programming problems,Dr.Dissertation,Department of Computer and Systems Science,University of Rome "La Sapienza",Italy,2004.
[103]D.Li,X.L.Sun,Nonlinear Integer Programming,Springer,New York,2005.
[104]M.Tawarmalani,N.V.Sahinidis,Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming:Theory,Algorithms,Software,and Applications.Kluwer,Academic Publishers,Dordrecht,2002.
[105]http://www.gamsworld.org/minlp/
[106]http://www.coin-or.org/
[107]达林,查建中,一种求解混合非线性整数规划的支撑超平面算法,系统工程理论与实践,vol.28(9),pp.82-86,2008.
[108]Dalin, J.Z.Cha, Non Interior-point Supporting Hyperplane method for solving MINLP, submit to Computers & Chemical Engineering.
[109] Jr.A.F. Veinott, (1967), The Supporting Hyperplane Method For unimodal Programming, Operations Research, vol. 15(1), pp. 147-152.
[110]I. E. Grossmann, Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and Engineering, vol.3, pp.227-252, 2002.
[111]J.Z. Cha, Mixed discrete constrained nonlinear programming via recursive quadratic programming, Dr. Dissertation, University of New York at Buffalo, 1987.
[2]Karp R.M.Miller R.E.and Thatcher J.W.(editors).Reducibility Among Combinatorial Problems,in:Complexity of Computer Computations.New York:(1972) Plenum,85-103.
[3]R.Gomory,Outline of an Algorithm for Integer Solutions to Linear Programs,Bulletin of the American Mathematical Society 64(1958),275.
[4]E.Balas,S.Ceria,G.Cornu(?)jols,and N.Natraj,Gomory Cuts Revisited,Operations Research Letters 19(1996),1.
[5]R.Dakin,A Tree-Search Algorithm for Mixed Integer Programming Problems,The Computer Journal 8(1964),250
[6]E.Balas,S.Ceria,and G.Cornu(?)jols,A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs,Mathematical Programming 58(1993),295.
[7]E.Balas,S.Ceria,and G.Cornu(?)jols,Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework,Management Science 42(1996),1229.
[8]C.Barnhart,E.Johnson,G.Nemhauser,M.Savelsbergh,and P.Vance,Branch-and-Price:Column Generation for Solving Huge Integer Programs,Operations Research 46(1998),316.
[9]M.Savelsbergh,A Branch-and-Price Algorithm for the Generalized Assignment Problem,Operations Research 45(1997),831.
[10]Optimization Software for Operations Research Applications,http://www.aimms.com.
[11]A Modeling Language for Mathematical Programming,http://www.ampl.com.
[12]The World's Mathematical Programming Optimizers,www.ilog.com/products/cplex/.
[13]General Algebraic Modeling System,www.gams.com.
[14]The Language of Technical Computing,www.tomopt.com
[15]G.L.Nemhauser,L.A.Wolsey,Integer and Combinatorial Optimization,Wiley-Interscience:New York,1988.
[16]L.E.Johnson,L.George Nemhauser,Martin W.P.Savelsbergh:Progress in Linear Programming-Based Algorithms for Integer Programming:An Exposition.INFORMS Journal on Computing 12(1):2-23(2000)
[17]A.Schrijver,Theory of Linear and Integer Programming,(John Wiley,Chichester,1986)
[18]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社,2000.
[19]施光燕,董加礼.最优化方法.北京:高等教育出版社,1999.
[20]马仲番.线性整数规划的数字基础.北京:科学出版社,1998.
[21]M.Yuceer,I.Atasoy,R.Berber,A semi heuristic MINLP algorithm for production scheduling.Computer Aided Chemical Engineering,vol.14,pp.335-340,2003.
[22]M.Yuceer,R.Berber,A heuristic approach for solution of MINLP problem for production scheduling in preemptive mode.Chemical Engineering and Processing,vol.44,pp.933-940,2005.
[23]P.Bonami,and M.Lejeune,An Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints,IBM Research Report RC24215,02/2007.
[24]S.S.Syam,A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals.European Journal of Operational of Operational Research,vol.108,pp.196-207,1998.
[25]J.S.Pang,A new and efficient algorithm for a class of portfolio selection problems.Operations Research,vol.28,pp.754-767,1989.
[26]Z.Novak Pintari(?),P.Glavi(?),Integration of Flue Gas into the Process Flowsheet by Combined Pinch-MINLP Approach.Chemical Engineering Research and Design,vol.80,pp.606-614,2002.
[27]T.Farkas,E.Rev,Z.Lelkes,Process flowsheet superstructures:Structural multiplicity and redundancy:Part Ⅰ:Ideal and binarily minimal MINLP representations.Computers &Chemical Engineering,vol.29,pp.2180-2197,2005.
[28]T.Farkas,E.Rev,Z.Lelkes,Process flowsheet superstructures:Structural multiplicity and redundancy:Part Ⅱ:Ideal and binarily minimal MINLP representations.Computers &Chemical Engineering,vol.29,pp.2198-2214,2005.
[29]李荷华,钱宇,郑世清,程华农,化工过程系统综合问题新的模块化求解策略和算法.化工学报,vol.54(7),pp.972-977,2003.
[30]闫志国,钱宇,李秀喜,化工过程综合问题MINLP算法中整型变量的连续化.高校化学工程学报,2005,vol.19(5),pp.670-674,.
[31]I.E.Grossmann,M.M.Daichendt,New Trends in Optimization-based Approaches for Process Synthesis,Computers and Chemical Engineering,vol.20,pp.665-683,1996.
[32]I.E.Grossmann,J.A.Caballero and H.Yeomans,Advances in Mathematical Programming for Automated Design,Integration and Operation of Chemical Processes,Proceedings of the International Conference on Process Integration(PI'99),Copenhagen,Denmark,1999.
[33]I.E.Grossmann,Mixed-Integer Optimization Techniques for Algorithmic Process Synthesis, Advances in Chemical Engineering, Vol. 23, Process Synthesis, pp.171-246 1996.
[34]I.E. Grossmann, J. Quesada, R. Raman and V. Voudouris, Mixed Integer Optimization Techniques for the Design and Scheduling of Batch Processes, Batch Processing Systems Engineering (Eds. G.V. Reklaitis, A.K. Sunol, D.W.T. Rippin, O. Hortacsu), pp. 451-494, Springer-Verlag, Berlin, 1996.
[35]J. Pinto, and I.E. Grossmann, Assignment and Sequencing Models for the Scheduling of Chemical Processes, Annals of Operations Research, vol. 81, pp.433-466, 1998.
[36]N. Shah, Single and Multisite Planning and Scheduling: Current Status and Future Challenges, FOCAPO Proceedings, 1998.
[37]J. Kallrath, Mixed integer optimization in the chemical process industry: Experience, potential and future", Trans. I. Chem E. vol. 78, part A, pp. 809-822, 2000.
[38] Amir, H.M., Hasegawa, T. Nonlinear Mixed-Discrete Structural Optimization, Journal of Structural Engineering, vol. 115, pp. 626-646, 1989.
[39]Sandgren, E. Nonlinear Integer and Discrete Programming in Mechanical Design Optimization, Transactions of the ASME, Journal of Mechanical Design, vol. 112, pp. 223-229, 1990.
[40]Emet, S. and Westerlund,T., Comparisons of solving a chromatographic separation problem using MINLP methods ,Computers & Chemical Engineering Vol.28, pp. 673-682,2004.
[41]Thomasa, I. and Kr(?)nera, A., Mixed-integer optimization of distillation column tray positions in industrial practice, Computer Aided Chemical Engineering, Vol.21, Part 1, pp. 1015-1020, 2006.
[42] E.M.L. Beale, Integer Programming, in The State of the Art in Numerical Analysis, (Eds D.A.H. Jacobs), Academic Press, London, 1978.
[43]M. Benichou, J.M. Gauthier, P. Girodet, G. Hentges, G. Ribiere, O. Vincent, Experiments in Mixed-Integer Linear Programming, Mathematical Programming, vol. 1, pp. 76-94, 1971.
[44]R. Breu and C. A. Burdet, Branch-and-bound experiments in 0-1 programming, Mathematical Programming Study, vol. 2, pp. 1-50, 1974.
[45]R.J. Dakin, A tree search algorithm for mixed integer programming problems, Computer Journal, vol. 8, pp. 250-255, 1965.
[46]R. Fletcher, Practical Methods of Optimization, 2nd edition (Eds. John Wiley), Chichester, 1987.
[47]R.S. Garfinkel, G.L. Nemhauser, Integer Programming, (Eds. John Wiley), New York, 1972.
[48]H.Greenberg,Integer Programming,Academic Press,New York,1971.
[49]O.K.Gupta A.Ravindran,Nonlinear Integer Programming and Discrete Optimization,Transactions of the ASME,Journal of Mechanisms,Transmissions and Automation in Design vol.105,pp.160-164,1983.
[50]O.K.Gupta,A.Ravindran,Branch and bound experiments in convex nonlinear integer programming,Management Science,vol.31,pp.1533-1546,1985.
[51]F.K(?)orner,A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems,BIT,vol.28,pp.701-708,1988.
[52]A.H.Land,A.G Doig,An automatic method for solving discrete programming problems,Econometrica,vol.28,pp.497-520,1960.
[53]J.D.C.Little,K.C.Murty,D.M.Sweeney and C.Karel,An algorithm for the travelling salesman problem,Operations Research,vol.11,pp.972-989,1963.
[54]G.L.Nemhauser,L.A.Wolsey,Integer and Combinatorial Optimization,(Eds.John Wiley),New York,1988.
[55]E.Sandgren,Nonlinear Integer and Discrete Programming for Topological Decision Making in Engineering Design,Transactions of the ASME,Journal of Mechanical Design,vol.112,pp.118-122.1990.
[56]E.Sandgren,Nonlinear Integer and Discrete Programming in Mechanical Design Optimization,Transactions of the ASME,Journal of Mechanical Design,vol.112,pp.223-229,1990.
[57]H.A.Taha,Integer Programming Theory,Applications and Computations,Academic Press,London,1975.
[58]O.V.Volkovich,V.A.Roshchin,I.V.Sergienko,Models and methods of solution of quadratic integer programming problems,Cybernetics,vol.23,pp.289-305,1987.
[59]王粉兰,非线性整数规划问题的若干新算法,博士论文,运筹学与控制论,上海大学,2005.
[60]R.A.Stubbs,S.Mehrotra,A Branch and Cut Method for 0-1 Mixed Convex Programming,presented at INFORMS Meeting,Washington,1999.
[61]S.Leyffer,Integrating SQP and Branch and Bound for Mixed Integer Nonlinear Programming,Computers and Chemical Engineering,vol.18,pp.295-309,2001.
[62]J.F.Benders,Partitioning procedures for solving mixed-variable programming problems,Numerische Mathematik,vol.4,pp.238-252,1962.
[63]O.E.Flippo,A.H.G.Rinnoy Kan,G.van der Hoek,Duality and decomposition in general mathematical programming,Econometric Institute,Report 8747/B,Erasmus University Rotterdam, 1987.
[64]O.E. Flippo and A.H.G. Rinnoy Kan, A note on Benders Decomposition in mixed-integer quadratic programming, Operations Research Letters, vol. 9, pp. 81-83, 1990.
[65]O.E. Flippo and A.H.G. Rinnoy Kan, Decomposition in general mathematical programming, Mathematical Programming, vol.60, pp. 361-382, 1993.
[66]A.M. Geoffrion, Generalized Benders Decomposition, Journal of Optimization Theory and Applications, vol. 10, pp. 237-260, 1972.
[67]R. Lazimy, Mixed-integer quadratic programming, Mathematical Programming, vol. 22, pp. 332-349, 1982.
[68]R. Lazimy, Improved Algorithm for Mixed-Integer Quadratic Programs and a Computational Study, Mathematical Programming, vol. 32, pp. 100-113, 1985.
[69]N.V. Sahinidis, I.E. Grossmann, Convergence properties of generalized Benders Decomposition, Computers and chemical Engineering, vol. 15, pp. 481-491,1991.
[70]O.V. Volkovich, V.A. Roshchin, I.V. Sergienko, Models and methods of solution of quadratic integer programming problems, Cybernetics, vol. 23, pp. 289-305, 1987.
[71] M. Duran, I.E. Grossmann, An outer-approximation algorithm for a class of Mixed Integer Nonlinear Programs, Mathematical Programming, vol. 36, pp.307-339, 1986.
[72]M. Duran and I.E. Grossmann, A mixed-integer programming algorithm for process systems synthesis, American Institute of Chemical Engineers Journal, vol. 32, pp. 592-606, 1986.
[73]G. R. Kocis and I.E. Grossmann, Global Optimization of Nonconvex Mixed Integer Nonlinear Programming (MINLP) problems in Process Synthesis, Industrial Engineering Chemistry Research, vol. 27 pp. 1407-1421, 1988.
[74] G. R. Kocis I.E. Grossmann, Computational experience with DICOPT solving MINLP problems in process systems engineering, Computers and Chemical Engineering, vol. 13, NO. 3,pp.307-315, 1989.
[75]I. Quesada, I.GGrossmann, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Dept. of Chemical Engineering, Carnegie Mellon University 1992.
[76]J. Viswanathan, I.E. Grossmann, A combined penalty function and outer-approximation method for MINLP optimization, Computers and chemical Engineering, vol. 14, pp. 769-782, 1990.
[77] X. Yuan, S. Zhang L. Pibouleau and S. Domenech, Une m'ethode d'optimization non lin'eaire en variables mixtes pour la conception de precedes, Operations Research vol. 22, pp.331-346,1988.
[78]J.E.Kelley,the Cutting Plane Method for Solving Convex Programs.Journal of SIAM,vol.8,NO.4,pp.703-712,1960.
[79]T.Westerlund,F.Pettersson,an Extended Cutting Plane Method for Solving Convex MINLP Problems,Computers chem.Eng,vol.19,pp.131-136,1995.
[80]Still C.and Westerlund T.(1997).A Modified α-ECP Algorithm for Solving Quasi-Convex NLP Problems.Report 97-156-A,Process Design Laboratory,(?)bo Akademi University,ISSN 952-12-0123-1,ISBN 0783-215X.
[81]T.Westerlund,H.Skrifvars,I.Harjunkoski,R.P(o|¨)rn,An Extended Cutting Plane Method for a Class of Non-Convex MINLP Problems,Computers chem.Eng,vol.22,pp.357-365,1998.
[82]R.P(o|¨)rn,T.Westerlund,Mixed Integer Non-Linear Programming Using Cutting Plane Techniques,European Symposium on Computer Aided Process Engineering ESCAPE-10,(Eds.S.Pierucci ),Elsevier Science,vol.8,pp.1-6.2000
[83]R.P(o|¨)rn,T.Westerlund,A Cutting Plane Method for Minimizing Pseudo-Convex functions in the Mixed Integer Case,Computers chem.Eng,vol.24,pp.2655-2665,2000.
[84]P.Michelon and N.Maculan,Lagrangean decomposition for integer nlnlinear programming wirh linear constraints,Mathematical Programming 52(1991) 303-313.
[85]J.Z.Cha and R.W.Mayne,,Optimization with Discrete Variables via Recursive Quadratic Programming:Part Ⅰ,Concepts and De8nitions,"ASME,Journal of Mech.,Trans.& Auto.In Design,vol.111,pp.124-130,1989.
[86]J.Z.Cha and R.W Mayne,.(1989b),Optimization with Discrete Variables Via Recursive Quadratic Programming:Part Ⅱ,Algorithm and Results,ASME,Journal of Mech.,Trans.&Auto.In Design,vol.111,pp.130-136,1989.
[87]E.Oliver,S.Klaus,A trust region SQP algorithm for mixed-integer nonlinear programming,Optimization Letters,vol.1,pp.269-280,2007.
[88]G.R.Olsen,G.N.Vanderplaats,Method for nonlinear Optimization with discrete design variables,AIAA Journal,vol.27,pp.1584-1589,1989.
[89]S.K.Banerjee,K.Rajamani,Optimization of System Relibility Using a Parametric Approach,IEEE,Trans.Reliability,vol.22,pp.35-39,1973.
[90]M.Pappas,A.Allentuch,Mathematical Programming Procedures for Mixed Discrete Continuous Design Problems,ASME J.of Engineering for Industry,pp.201-209,1974.
[91]陈国华,廖小莲,0-1非线性混合整数规划的罚函数解法,应用数学与计算数字学报.Vol.21,No.1,pp.111-115,2007.
[92]E.G.Davydov,I.K.Sigal,Application of the Penalty Function Method in Integer Programming Problems,Engineering Cyberuetics,vol.10,pp.21-24,1972.
[93]H.L.Li,An Approximate Method for Local Optima for Nonlinear Mixed Integer Programming Problems,Computers and Operations Research,vol.19,pp.435-444,1992.
[94]R.L.Salcedo,Solving nonconvex nlnlinear programming and mixed-integer nonlinear programming problems with adaptive random search,Industrial Enginneering Chemistry Research 31(1992) 262-273
[95]丰建荣,刘正和,刘志河,王成寿,MINLP问题全局优化算法的研究,系统仿真学报,vol.17,pp.1859-1863,2005.
[96]刘芳,李人厚,基于种族优生的进化规划用于混合非线性整数规划,系统仿真学报,vol.15,pp.1076-1078,2003.
[97]刘钊,康立山,蒋良孝,杨林权,用粒子群优化改进算法求解混合整数非线性规划问题,小型微型计算机系统,vol.26,No.6,pp.991-994,2005.
[98]P.Bonami,L.Biegler,A.Conn,G.Cornuejols,I.Grossmann,C.Laird,J.Lee,A.Lodi,F.Margot,S.Nicolas,A.Waechter.An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs,Discrete Optimization,5:186-204,2008.
[99]O.Exler,K.Schittkowski,"A Computational Study of a Trust Region SOP Algorithm for Mixed-Integer Nonlinear Programming",Web:www.klaus-schittkowski.de.2006.
[100]S.Leyffer,Deterministic Methods for Mixed Integer Nonlinear Programming,Dr.Dissertation,Department of Mathematics and Computer Science,University of Dundee,Dundee,1993.
[101]C.S.Adjiman,C.A.Schweiger and C.A.Foludas,Mixed-lnteger Nonlinear Optimization in Process Sythesis(Eds.D.Z.Du,P.M.Pardalos),1998.
[102]V.Piccialli,Methods for solving Mixed Variable Programming problems,Dr.Dissertation,Department of Computer and Systems Science,University of Rome "La Sapienza",Italy,2004.
[103]D.Li,X.L.Sun,Nonlinear Integer Programming,Springer,New York,2005.
[104]M.Tawarmalani,N.V.Sahinidis,Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming:Theory,Algorithms,Software,and Applications.Kluwer,Academic Publishers,Dordrecht,2002.
[105]http://www.gamsworld.org/minlp/
[106]http://www.coin-or.org/
[107]达林,查建中,一种求解混合非线性整数规划的支撑超平面算法,系统工程理论与实践,vol.28(9),pp.82-86,2008.
[108]Dalin, J.Z.Cha, Non Interior-point Supporting Hyperplane method for solving MINLP, submit to Computers & Chemical Engineering.
[109] Jr.A.F. Veinott, (1967), The Supporting Hyperplane Method For unimodal Programming, Operations Research, vol. 15(1), pp. 147-152.
[110]I. E. Grossmann, Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and Engineering, vol.3, pp.227-252, 2002.
[111]J.Z. Cha, Mixed discrete constrained nonlinear programming via recursive quadratic programming, Dr. Dissertation, University of New York at Buffalo, 1987.