Stochastic Level-Value Approximation for Quadratic Integer Convex Programming

PENG Zheng; WU Dong-hua

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2008 > 29(6): 726-734

PENG Zheng, WU Dong-hua. Stochastic Level-Value Approximation for Quadratic Integer Convex Programming[J]. Applied Mathematics and Mechanics, 2008, 29(6): 726-734.

Citation:

PENG Zheng, WU Dong-hua. Stochastic Level-Value Approximation for Quadratic Integer Convex Programming[J]. Applied Mathematics and Mechanics, 2008, 29(6): 726-734.

Citation:

PENG Zheng, WU Dong-hua. Stochastic Level-Value Approximation for Quadratic Integer Convex Programming[J]. Applied Mathematics and Mechanics, 2008, 29(6): 726-734.

PDF( 377 KB)

Stochastic Level-Value Approximation for Quadratic Integer Convex Programming

PENG Zheng^1,2,
WU Dong-hua¹

1.
Department of Mathematics, Shanghai University, Shanghai 200444, P. R. China;

Received Date: 2007-07-09
Rev Recd Date: 2008-04-30
Publish Date: 2008-06-15

Abstract

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.
- quadratic integer convex programming,
- stochastic level value approximation,
- cross-entropy method,
- asymptotic convergence

FullText(HTML)

References(18)

References

[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.