A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
针对带线性约束的零一二次规划问题，提出一种新的线性化方法，能比现有方法得到更紧的线性规划松弛，并设计了结合拉格朗日松弛、Benders割平面和局部搜索的隐枚举算法，通过计算实验验证了其有效性。
This paper is concerned with the solution of linearly constrained zero-one quadratic programming problems. Problems of this kind arise in numerous economic, location decision, and strategic planning situations, including capital budgeting, facility location, quadratic assignment, media selection, and dynamic set covering. A new linearization technique is presented for this problem which is demonstrated to yield a tighter continuous or linear programming relaxation than is available through other methods. An implicit enumeration algorithm which uses Lagrangian relaxation, Benders' cutting planes, and local explorations is designed to exploit the strength of this linearization. Computational experience is provided to demonstrate the usefulness of the proposed linearization and algorithm.