整数规划的渐进强对偶方法

摘要/Abstract

摘要：

虽然整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。该文提出一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索。

关键词: 整数规划;Lagrange松弛;对偶间隙;拟对偶公式

Abstract:

Although the Lagrangian method is a powerful dual search method in integer programming, it often fails to identify the optimal solution of the prim a l problem. In this paper, a quasi dual formulation is proposed for bounded integ er programming. This formulation possesses an asymptotic strong duality property and guarantees a success for identifying an optimum solution. Its another f eatu re is that no actual dual search is needed when the parameters of the method are set to be suitable.

Key words: Integer programming;Lagrangian relaxation;Duality gap;Quasi dual formulation

中图分类号:

90C10

王薇, 徐以凡. 整数规划的渐进强对偶方法[J]. 数学物理学报, 2004, 24(3): 285-292.

WANG Wei, XU Yi-Fan. An Asymptotic Strong Duality |Method for Integer Programming[J]. Acta mathematica scientia,Series A, 2004, 24(3): 285-292.

参考文献

[1]Bell D E,Shapiro J F. A convergent duality theory for integer programming.Operations Research,1977,25: 419-443

[2]Fisher M L.The Lagrangian relaxation method for solving integer programming p roblems. Management Science,1981,27:1-18

[3]Geoffirion A M.Lagrangian relaxation for integer programming.Math Programming Stud,1974,2:82-114

[4]Goh C J, Yang X Q.A sufficient and necessary condition for nonconvex constrained optimization.Appl Math Lett,1997,10: 9-12

[5]Guignard M, Kim S.Lagrangian decomposition: a model yielding stronger Lagrangian relaxation bounds.Mathematical Programming, 1993, 33: 262-273

[6]Li D. Zero duality gap for a class of nonconvex optimization problem.J Opti Theory Appl, 1995, 85: 309-324

[7]Li D. Zero duality gap in integer programming:p norm surrogate constrain t method. Operations Research Letter,1999, 25: 89-96

[8]Llewellyn D C, Ryan J. A primal dual integer programming algorithm. Disc rete Appl Math, 1993, 45: 262-273

[9]Michelon P N,Maculan N. Lagrangian decomposition for integer nonlinear progra mming with linear constrains.Mathematical Programming,1991, 52: 303-313

[10]Shapiro J F.A survey of Lagrangian techniques for discrete optimization. Annal s of Discrete Mathematics, 1979, 5: 113-138

[11]Sun X L,Li D. Valueestimation function method for constrained global optimiz ation. J Opti Theory Appl,1999,102: 385-409

[12]White D J.Weighting factor extensions for finite multiple objective vector min imization problems.European Journal of Operations Research,1988,36: 256-265

[13]Williams H P.Duality in mathematics and linear and integer programming.J Opti Theory Appl, 1996,90:257-278

[14]Xu Z K. Local saddle points and convexification for nonconvex optimizatin problems.J Opti Theory Appl, 1997,100: 257-278