A HEURISTIC-BASED BRANCH-AND-BOUND ALGORITHM FOR UNCONSTRAINED QUADRATIC ZERO-ONE PROGRAMMING

作     者：PALUBECKIS, G 

作者机构：Department of Practical Informatics Kaunas University of Technology Studentu St. 50 3028 Kaunas Lithuania 

出 版 物：《COMPUTING》 (Computing)

年 卷 期：1995年第54卷第4期

页      面：283-301页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：INTEGER QUADRATIC PROGRAMMING BRANCH AND BOUND GRAPHS 

摘      要：In this paper we describe a branch and bound algorithm for solving the unconstrained quadratic 0-1 programming problem. The salient features of it are the use of quadratic programming heuristics in the transformation of subproblems and exploiting some classes of facets of the polytope related to the quadratic problem in deriving upper bounds on the objective function. We develop facet selection procedures that form a basis of the bound computation algorithm. We present computational experience on four series of randomly generated problems and 14 real instances of a quadratic problem arising in design automation. We remark that the same ideas can also be applied to some other combinatorial optimization problems.