线性约束0-1二次规划的一个定界技术

A BOUNDING TECHNIQUE FOR LINEARLY CONSTRAINED 0-1 QUADRATIC PROGRAMMING

本文给出确定线性约束0－1二次规划问题最优值下界的方法，该方法结合McBride和Yormark的思想和总体优化中定下界的方法，证明了所定的界较McBride和Yormark的要好．求解线性约束0－1二次规划问题的分支定界算法可以利用本文的定界技术．

Taking into account the idea of McBride and Yormark (1980) and a lower bounding method in global optimization, a lower bounding technique is presented in this paper for linearly constrained 0-1 quadratic programming problems, which could in turn be incorporated into the Branch-and-Bound scheme. The lower bound provided is proved to be better than that of McBride and Yormark (1980).