Stochastic Level-Value Approximation for Quadratic Integer Convex Programming
-
摘要: 对凸二次整数极小化问题提出了一种随机水平值逼近算法,该算法应用了重点取样技术,并利用极小化相对熵的思想来更新取样密度.对算法的渐近收敛性进行了证明,给出了数值实验的结果.Abstract: A stochastic level value approximating method for quadratic integer convex minimizing problem was proposed. This method applies the importance sampling technique, and uses the main idea of the cross-entropy method to update the sample density functions. The asymptotic convergence of this algorithm was also proved, and some numerical results to illuminate its efficiency was reported.
-
[1] Wolsey Laurence A.Integer Programming[M].New York:John Wiley and Sons,Inc.1998. [2] Land A H,Doig A G.An automatic method for solving discrete problems[J].Econometrica,1960,28(3):497-520. doi: 10.2307/1910129 [3] Dakin R J.A tree search algorithm for mixed integer programming problems[J].Computer Journal,1965,8(3):250-255. doi: 10.1093/comjnl/8.3.250 [4] Dantzig G B,Fulkerson D R,Johnson S.Solution of a large scale traveling salesman problem[J].Operations Research,1954,2(4):393-410. doi: 10.1287/opre.2.4.393 [5] Gomory R E.An algorithm for the mixed integer problem[R]. RM-2597, The Rand Corporation, 1960. [6] Derpich I,Vera J R.Improving the efficiency of the Branch and Bound algorithm for integer programming based on “flatness” information[J].European Journal of Operational Research,2006,174(1):92-101. doi: 10.1016/j.ejor.2005.02.051 [7] HUA Zhong-sheng,HUANG Fei-hua.An effective genetic algorithm approach to large scale mixed integer programming problems[J].Applied Mathematics and Computation,2006,174(2):897-909. doi: 10.1016/j.amc.2005.05.017 [8] Bosio Sandro,Righini Giovanni.Computational approaches to a combinatorial optimization problem arising from text classification[J].Computers and Operations Research,2007,34(7):1910-1928. doi: 10.1016/j.cor.2005.07.021 [9] Arostegui Jr Marvin A,Kadipasaoglu Sukran N,Khumawala Basheer M.An empirical comparison of Tabu search, simulated annealing,and genetic algorithms for facilities location problems[J].International Journal of Production Economics,2006,103(2):742-754. doi: 10.1016/j.ijpe.2005.08.010 [10] Dino Ahr,Gerhard Reinelt.A Tabu search algorithm for the min-max k-Chinese postman problem[J].Computers and Operations Research,2006,33(12):3403-3422. doi: 10.1016/j.cor.2005.02.011 [11] Mokhtar S B,Hanif D S,Shetty C M.Nonlinear Programming, Theory and Algorithms[M].Hoboken,Canada: John Wiley and Sons,Inc.1993,199-233. [12] De Boer P-T,Kroese D P,Mannor S,et al.A tutorial on the cross-entropy method[J].Annals of Operations Research,2005,134(1):19-67. doi: 10.1007/s10479-005-5724-z [13] 邬冬华,俞武扬,田蔚文.一种求约束总极值的水平值估计方法[J].应用数学和力学,2006,27(7):874-882. [14] 彭拯,邬冬华,田蔚文.约束全局优化的水平值估计算法[J].计算数学,2007,29(3):293-304. [15] Rubinstein R Y.The cross-entropy method for combinatorial and continuous optimization[J].Methodology and Computing in Applied Probability,1999,1(2):127-190. doi: 10.1023/A:1010091220143 [16] Sheldon M Ross.Simulation[M].3rd Ed.Beijing,China:Posts and Telecom Press,2006:45-47 . [17] 万国成,田翔,任震.一类非线性整数规划问题的计算机求解[J].计算机工程与应用,2002,38(16):80-83. [18] 林锦,朱文兴.凸整数规划问题的混合蚁群算法[J].福州大学学报(自然科学版),1999,27(6):5-9.
点击查看大图
计量
- 文章访问数: 2970
- HTML全文浏览量: 135
- PDF下载量: 590
- 被引次数: 0