摘要
考虑如下的整数线性规划问题: (P)min Cx, s.tAx≥b, x≥0,且为整数向量,其中c,b是具有适当维数的行向量或列向量,A是已知的矩阵,c的分量均为正数,且假定(P)是可行的,x是n维变量。 用V(·)表示优化问题(·)的最优值。如果对x放弃整数限制要求,问题(P)
Methods for solving Lagrangean dual in integer programs have been highly developed toprovide good bounds in branch and bound procedures. While surrogate dual has been theore-tically shown to provide stronger bounds, the complexity of solving surrogate dual has dis-couraged their employment in integer programs. This paper presents a new method for solvingsurrogate duality in integer programs. The theoretical analysis and computational examplesshow that the method proposed is efficient.
出处
《计算数学》
CSCD
北大核心
1993年第2期156-164,共9页
Mathematica Numerica Sinica
