离散p-扩散问题的连续化算法
An Efficient Lagrangian Smoothing Heuristic for the p-Dispersion-Sum Problem

作者: 龚玉君 , 邹慧敏 :北京航空航天大学,数学与系统科学学院,北京;

关键词: 二次规划问题拉格朗日光滑算法启发式连续算法Quadratic Program Lagrangian Smoothing Frank-Wolfe Algorithm Heuristic

摘要:
p-扩散问题主要研究在事先定义的n个位置中如何选取p个位置,使得这p个位置之间的距离之和最大,具有很实际的应用价值。本文提出了解决p-扩散问题的一种连续化方法,采用连续的算法解决离散问题策略,通过控制一个参数使得从拉格朗日函数向罚函数过渡迭代求解。这种算法的子问题采用了截断的Frank-Wolfe算法来避免收敛过慢,相比较离散算法,不受结点数量的制约,更具有广泛性。本文建立了有效的迭代终止准则,并且证明了这种算法最终会收敛在一个KKT点。最后,针对这种连续化算法,我们做了大量数值实验,验证了算法的可行性与有效性。

Abstract:
In this article, we propose a Lagrangian smoothing algorithm for the p-dispersion-sum problem (PDSP), a problem to locate p facilities at some of n predefined locations by maximizing the distance sum between the p established facilities, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We make the iteration from Lagrangian function to penalty function by controlling a parameter. We establish practical stopping criteria and prove that our algorithm finitely terminates at a KKT point. Compared to the discrete algorithm, the smoothing algorithm is free from the constraints of the number of nodes and more extensive. Numerical results indicate that our approach outperforms good and rapid for solving randomly generated problems in dimensional n ≥ 100.

文章引用: 龚玉君 , 邹慧敏 (2014) 离散p-扩散问题的连续化算法。 运筹与模糊学, 4, 7-14. doi: 10.12677/ORF.2014.41002

参考文献

[1] Horst, R. and Pardalos, P. M. (1975) Handbook of globa1 optimization. Kluwer Academic Publishers, Boston.

[2] Pardalos, P.M. and Rosen, J.B. (1987) Constrained global optimization: Algorithm and applications. Springer-Verlag, Berlin.

[3] Adams, W.P. and Sherali, H.D. (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Management Science, 10, 1274-1290

[4] Krarup, J., Pisinger, D. and Plastria, F. (2002) Discrete location problems with push-pull objectives. Discrete Applied Mathematics, 123, 363-378.

[5] Kortsarz, G. and Peleg, D. (1993) On choosing a dense subgraph. Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, 3-5 November 1993, 692-701.

[6] Asahiro, Y., Iwama, K., Tamaki, H. and Tokuyama, T. (1996) Greedily finding a dense subgraph. Proceedings of the 5th Scandinavian Workshop on Algorithm Theory. Lectures notes in Computer Science, 1097, 136-148.

[7] Hassin, R., Rubinstein, S. and Tamir, A. (1997) Approximation algorithms for maximum dispersion. Operations Research Letters, 21, 133-137.

[8] Srivastav, A. and Wolf, K. (1998) Finding dense subgraph with semidefiinite programming. In: K. Jansen and J. Rolim, Eds., Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, 181-191.

[9] Kincaid, R.K. (1992) Good solutions to discrete noxious location problems via metaheuristics. Annals of Operations Research, 40, 265-281.

[10] Krarup, J., Pisinger, D. and Plastria, F. (2002) Discrete location problems with push-pull objectives. Discrete Applied Mathematics, 123, 363-378.

[11] Billionnet, A. and Soutif, E. (2004) An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem. European Journal of Operational Research, 157, 565-575.

[12] Xia Yong and Guo, Z.F. (2011) Quadratic-type efficient upper bounds for the p-dispersion-sum problem.

[13] Xia Yong and Guo, Z.F. (2010) An efficient lagrangian smoothing heuristic for MAX-CUT. Indian Journal of Pure & Applied Mathematics, 41, 683-700

[14] Pisinger, D. (2006) Upper bounds and exact algorithms for p-dispersion problems. Computers & Operations Research, 33, 1380-1398.

[15] Erkut, E. (1990) The discrete p-dispersion problem. European Journal of Operational Research, 46, 48-60.

分享
Top