一类特殊0-1二次规划问题解的必要条件和算法

The Necessary Conditions and the Algorithm for a Special Class of 0-1 Quadratic Programming Problem

研究一类特殊的0-1二次规划问题,其目标函数的系数矩阵为对称矩阵,所有元素均为0或1并且对角线元素相同,决策变量的和为给定的正整数.首先,给出一个最优解的必要条件.然后,设计了一个高效的算法,可用于求解大规模的此类问题.

In this paper,we consider a special class of 0-1 quadratic programming problem.The coefficient matrix of its objective function is a 0-1 symmetric matrix with the same element in the diagonal,and the sum of decision variable is a given positive integer.We present a necessary condition for the optimal solution,and design an efficient algorithm that can be used to solve large-scale problem.