Search

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach. [ABSTRACT FROM AUTHOR]

In this paper we present a method for the regularized solution of nonlinear inverse problems, based on Ivanov regularization (also called method of quasi solutions or constrained least squares regularization). This leads to the minimization of a nonconvex cost function under a norm constraint, where nonconvexity is caused by nonlinearity of the inverse problem. Minimization is done by iterative approximation, using (nonconvex) quadratic Taylor expansions of the cost function. This leads to repeated solution of quadratic trust region subproblems with possibly indefinite Hessian. Thus, the key step of the method consists in application of an efficient method for solving such quadratic subproblems, developed by Rendl and Wolkowicz []. We here present a convergence analysis of the overall method as well as numerical experiments. [ABSTRACT FROM AUTHOR]

We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0–1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to n = 100, independent of the density. For some problems of special structure we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so. [ABSTRACT FROM AUTHOR]

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. [ABSTRACT FROM AUTHOR]

We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slater's condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function in the primal-dual space. This function shows similarities with the augmented Lagrangian function and is called "augmented primal-dual function" or "apd-function". The evaluation of the function and its derivative is cheap if the projection of a given point onto the cone can be computed cheaply, and if the projection of a given point onto the affine subspace defining the primal problem can be computed cheaply. For the special case of a semidefinite program, a certain regularization of the apd-function is analyzed. Numerical examples minimizing the apd-function with a conjugate gradient method illustrate the potential of the approach. [ABSTRACT FROM AUTHOR]

Abstract: The Lovász -function is a well-known polynomial lower bound on the chromatic number. Any near-optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented. These heuristics could be useful for coloring medium sized graphs as numerical results on DIMACS benchmark graphs indicate. [Copyright &y& Elsevier]

Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate their potential for branch and bound settings by looking also at the bounds in the first levels of the branching tree. [ABSTRACT FROM AUTHOR]

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ( G) or the clique number ω( G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ( G) or ω( G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. [ABSTRACT FROM AUTHOR]

We consider 3-partitioning the vertices of a graph into sets S1, S2, and S3 of specified cardinalities, such that the total weight of all edges joining S1 and S2 is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that this problem can be formulated as a linear program over the cone of completely positive matrices, leading in a natural way to semidefinite relaxations of the problem. We show in particular that the spectral relaxation introduced by Helmberg et al. (1995) can equivalently be formulated as a semidefinite program. Finally we propose a tightened version of this semidefinite program and show on some small instances that this new bound is a significant improvement over the spectral bound. [ABSTRACT FROM AUTHOR]

We investigate relaxations for the maximum stable set problem based on the Lovász number v(G) as an initial upper bound. We strengthen this relaxation by adding two classes of curling planes, odd circuit and triangle inequalities. We present computational results using this tighter model on many classes of graphs. [ABSTRACT FROM AUTHOR]

A bipartite graph G is known to be Pfaffian if and only if it does not contain an even subdivision H of K3,3 such that G−VH contains a 1-factor. However a general characterisation of Pfaffian graphs in terms of forbidden subgraphs is currently not known.The 2-ear theorem of Lova´sz and Plummer is likely to play a crucial roˆle in such a characterisation. The theorem asserts that every 1-extendible graph G has an ear decomposition K2=G0,G1,…,Gt=G such that the 1-extendible graph Gi is obtained from the 1-extendible graph Gi−1 by the adjunction of one or two ears. In this paper we first show that we can restrict the study of Pfaffian graphs to 1-extendible graphs which have an ear decomposition with a unique 2-ear adjunction. Motivated by that result we start a characterisation of Pfaffian graphs with an ear decomposition where the unique 2-ear adjunction is the final adjunction, i.e., Gt is obtained from Gt−1 by the adjunction of two ears. Such graphs are called ‘near bipartite’. [Copyright &y& Elsevier]

Presents on the exact solution method for the graph bisection problem. Description of a branch-and-bound algorithm; Method of Brunetta, Conforti, and Rinaldi, short BCR-library; Use of Primal-Dual Interior Point Approach.

We introduce a new class of algorithms for solving linear semidefinite programming (SDP) problems. Our approach is based on classical tools from convex optimization such as quadratic regularization and augmented Lagrangian techniques. We study the theoretical properties and we show that practical implementations behave very well on some instances of SDP having a large number of constraints. We also show that the "boundary point method" from Povh, Rendl, and Wiegele [Computing, 78 (2006), pp. 277-286] is an instance of this class. [ABSTRACT FROM AUTHOR]

We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods. [ABSTRACT FROM AUTHOR]

A preface for the 2011 issue of the journal "Mathematical Programming" is presented.