收稿日期: 2015-07-27
网络出版日期: 2017-04-30
An exponent deviation integral algorithm for mixed integer programming
Received date: 2015-07-27
Online published: 2017-04-30
研究了一种求解混合整数规划问题的指数变差积分算法. 利用积分型总极小值理论及指数变差积分对混合整数规划问题进行研究, 通过变差积分函数的分析性质及混合整数规划的最优性条件, 结合牛顿法设计了一种求解混合整数规划的指数变差积分新算法. 运用Monte-Carlo 模拟方法实现整个算法, 数值结果表明该算法是有效的.
关键词： Monte-Carlo 模拟; 指数变差积分; 最优性条件; 混合整数规划
于亚茹, 姚奕荣 . 求解混合整数规划问题的指数变差积分算法[J]. 上海大学学报(自然科学版), 2017 , 23(2) : 276 -289 . DOI: 10.3969/j.issn.1007-2861.2015.05.010
This paper studies an exponent deviation integral approach to the mixed integer programming problem. A deviation integral function with good properties is proposed, and the optimality condition for a mixed integer programming problem is examined. Then an exponent deviation integral algorithm is developed. Numerical calculation is performed using the Monte-Carlo technique to show effectiveness and feasibility of the algorithm.
[1] Bonami P, Gonçalves J P M. Heuristics for convex mixed integer nonlinear programs [J]. Computational Optimization and Applications, 2012, 51(2): 729-747.
[2] Berthold T. Primal heuristics for mixed integer programs [D]. Berlin: Technischen Universit¨at, 2006.
[3] Elhedhli S, Goffin J L. The integration of an interior-point cutting plane method within a branch-and-price algorithm [J]. Mathematical Programming, 2004, 100(2): 267-294.
[4] Joe N S. Interior point cutting plane methods in integer programming [J]. Computers and Operations Research, 2011, 38(9): 1335-1341.
[5] Zheng Q. Robust analysis and global optimization [J]. Annals of Operations Research, 1990, 24(1): 273-286.
[6] Zheng Q. Robust analysis and global minimization of a class of discontinuous functions(Ⅰ) [J]. Acta Mathematical Applicatae Sinica (English Series), 1990, 6(3): 205-223.
[7] Zheng Q. Robust analysis and global minimization of a class of discontinuous functions (Ⅱ) [J]. Acta Mathematical Applicatae Sinica (English Series), 1990, 6(4): 317-337.
[8] Zheng Q. Robust analysis and global optimization [J]. Computers and Mathematics with Applications, 1991, 21(6/7): 17-24.
[9] Bazaraa M S, Sherall H D, Shetty C M. Nonlinear programming: theory and algorithms [M]. 3rd ed. New York: John Wiley & Sons, 2006.
[10] Zheng Q. Optimality conditions of global optimization (Ⅰ)[J]. Acta Mathematicae Applicatae Sinica (English Series), 1985, 1(2): 66-78.
[11] Zheng Q. Optimality conditions of global optimization (Ⅱ)[J]. Acta Mathematicae Applicatae Sinica (English Series), 1985, 1(3): 118-132.
[12] 郑权, 蒋百川, 庄松林. 一个求总极值的方法[J]. 应用数学学报, 1978, 1(2): 161-174.
[13] Yao Y R, Chen L, Zheng Q. Optimality condition and algorithm with deviation integral for global optimization [J]. Journal of Mathematical Analysis and Applications, 2009, 357(2): 371-384.
[14] Han B S, Yao Y R. Existence and optimality of accessible and approximatable minimizers of quasi upper robust functions [J]. Computers and Mathematics with Applications, 2006, 52: 65-80.
[15] Tang J F, Zheng Q. Automatic design of optical thin-film system merit function and numerical optimization method [J]. Journal of Optical Society of America, 1982, 72(11): 1522-1528.
[16] Galperin E A, Zheng Q. Variation-free iterative method for global optimal control [J]. International Journal of Control, 1989, 50(5): 1731-1743.
[17] Galperin E A, Zheng Q. Integral global optimization method for nonlinear games [J]. Computers and Mathematics with Applications, 1991, 21(6/7): 145-159.
[18] Galperina E A, Pan Z X, Zheng Q. Application of global optimization to implicit solution of partial differential equations [J]. Computers and Mathematics with Applications, 1993, 25(10/11): 119-124.
[19] Zhuang S L, Zheng Q, Yu F T. Automatic generation of prototype lenses [J]. Optics Letters, 1982, 7(12): 581-583.
[20] Zheng Q, Zhuang D. Equi-robust set-valued mappings and the approximation of fixed points [C]// Proceedings of the Second International Conference on Fixed Point Theory and Applications. 1992: 346-361.
[21] Zheng Q, Yao Y R, Zhang M L. An integral global optimization algorithm for mixed programming problem [C]// Proceedings of the 2013 International Conference on Advanced Mechatronic Systems. 2013: 25-27.
[22] Shi S Z, Zheng Q, Zhuang D M. Discontinuous robust mapping are approximately [J]. Transactions of the American Mathematical Society, 1995, 347(12): 4943-4957.
/
| 〈 |
|
〉 |
