Unconstrained quadratic bivalent programming problem (Q792219)

The problem of minimising an unconstrained quadratic function of 0-1 variables is considered in this paper. A local minimising point is defined; and necessary and sufficient conditions for such a point are identified. A branching and pruning algorithm, which essentially generates all the local minimising points, is proposed to solve the problem. Computational experience with the algorithm, which is encouraging, is reported. This experience indicates that problems up to 120 variables are solved efficiently by the algorithm. Another computational study, incorporating some efficient bounding strategies, has also been conducted (to be published in Opsearch). This study is aimed to identify the relatively difficult problems and has also been used to propose efficient heuristic algorithms to solve these difficult problems.