Experiments in quadratic 0-1 programming (Q1123806)

The paper is concerned with the unconstrained quadratic 0-1 programming problem. An approach proposed by the authors consists in reducing this problem to a max-cut problem in a graph and then using a partial description of the cut polytope to attack the problem with a cutting plane algorithm based on the simplex method. This approach, however, does not guarantee finding an optimum solution. To obtain it the authors use a branch-and-bound method. They report on extensive computational experience and note that in the vast majority of examples considered the problem is solved without branching.