An Unconstrained Quadratic Program with Binary Variables is the problem of maximizing a quadratic form x'Qx + d'x, where x is a vector of n whose components can assume only the values 0 or 1, while the matrix Q and the vector d have arbitrary rational entries. Max-Cut is the problem of finding a (possibly empty) cut of maximal weight in a given weighted graph. These two classical combinatorial optimization problems have attracted a great deal of interest also for their numerous links with other fields of discrete mathematics and for the variety of interesting “real world” applications. By applying a simple map, it is easy to see that they are equivalent, thus we can refer only to one of them, say, the second.
Max-Cut falls into the class of NP-hard problems, thus it is very unlikely that an algorithm exists that finds a solution for an arbitrary instance in a number of steps bounded by a polynomial in the size of the graph. We survey some classes of instances with a special structure for which such an algorithm exists. These classes are well characterized either in terms of the structure of the graph or in terms of the structure of the objective function coefficients.
However, as most of the interesting instances do not fall into those nice classes, the real challenge, from a computational standpoint, remains the one of finding the optimal solution, in a reasonable amount of time, for arbitrary instances of significant sizes. Some promising progress in this direction has been made in the last few years, mainly due to the study of two relaxations. The first one is the semidefinite relaxation, supported by the fact that today’s interior point methods are able to solve semidefinite programs efficiently. Incidentally, based on this relaxation, one of the most important results on approximative algorithms for NP-hard problems has been produced right for Max-Cut. The second one is the linear relaxation, supported by the fact that today’s simplex or interior point algorithms are able to solve large linear programs efficiently. This relaxation relies on the (partial) knowledge of the linear system describing the Cut Polytope, the convex hull of the characteristic vectors of all cuts of the graph. Some of the numerous results produced on the Cut Polytope can be turned into powerful algorithmic tools by means of suitable projecting and lifting operations.
By covering all these topics, which are specific for Max-Cut, we have also the opportunity to survey some of the main components of a typical state-of-the art algorithm for the exact optimization of NP-hard combinatorial problems.