Generalised 2-circulant inequalities for the max-cut problem

The max-cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results.     

Facets for the cut cone I

We study facets of the cut coneC _n , i.e., the cone of dimension 1/2n(n – 1) generated by the cuts of the complete graph onn vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a lifting procedure for constructing facets ofC _n+1 from given facets of the lower dimensional coneC _n . After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.     

Connections between semidefinite relaxations of the max-cut and stable set problems

We describe links between a recently introduced semidefinite relaxation for the max-cut problem and the well known semidefinite relaxation for the stable set problem underlying the Lovász’s theta function. It turns out that the connection between the convex bodies defining the semidefinite relaxations mimics the connection existing between the corresponding polyhedra. We also show how the semidefinite relaxations can be combined with the classical linear relaxations in order to obtain tighter relaxations. This work was done while the author visited CWI, Amsterdam, The Netherlands. Svata Poljak untimely deceased in April 1995. We shall both miss Svata very much. Svata was an excellent colleague, from whom we learned a lot of mathematics and with whom working was always a very enjoyable experience; above all, Svata was a very nice person and a close friend of us. The research was partly done while the author visited CWI, Amsterdam, in October 1994 with a grant fom the Stieltjes Institute, whose support is gratefully acknowledged. Partially supported also by GACR 0519. Research support by Christian Doppler Laboratorium für Diskrete Optimierung.     

Optimization and optimality test for the Max-Cut Problem

We show that the following two problems are polynomially equivalent:

Laplacian eigenvalues and the maximum cut problem

We introduce and study an eigenvalue upper bound(G) on the maximum cut mc (G) of a weighted graph. The function(G) has several interesting properties that resemble the behaviour of mc (G). The following results are presented.We show that is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that(G) is never worse that 1.131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of(G), and show that(G) is computable in polynomial time with an arbitrary precision.The research has been partially done when the second author visited LRI in September 1989.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems.     

最大割问题的二次规划方法

本文给出了最大割问题的二次规划算法。这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界，然后用分支定界法得到了最大割问题的解。数值结果表明这种算法是非常有效的。