The max-cut problem and quadratic 0–1 optimization; polyhedral aspects,relaxations and bounds

Given a graphG, themaximum cut problem consists of finding the subsetS of vertices such that the number of edges having exactly one endpoint inS is as large as possible. In the weighted version of this problem there are given real weights on the edges ofG, and the objective is to maximize the sum of the weights of the edges having exactly one endpoint in the subsetS. In this paper, we consider the maximum cut problem and some related problems, likemaximum-2-satisfiability, weighted signed graph balancing. We describe the relation of these problems to the unconstrained quadratic 0–1 programming problem, and we survey the known methods for lower and upper bounds to this optimization problem. We also give the relation between the related polyhedra, and we describe some of the known and some new classes of facets for them.