Contribution of copositive formulations to the graph partitioning problem

This article provides analysis of several copositive formulations of the graph partitioning problem and semidefinite relaxations based on them. We prove that the copositive formulations based on results from Burer [S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479–495] and the author of the paper [J. Povh, Semidefinite approximations for quadratic programs over orthogonal matrices. J. Global Optim. 48 (2010), pp. 447–463] are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath–Hoffman eigenvalue lower bound [W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 17 (1973), pp. 420–425] and the projected semidefinite lower bound from Wolkowicz and Zhao [H. Wolkowicz and Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97 (1999), pp. 461–479].     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

Facets of the Graph Coloring Polytope

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.     

On stable set polyhedra for K1,3-free graphs

We give several classes of facets for the convex hull of incidence vectors of stable sets in a K_1,3-free graph, including facets with (a, a + 1)-valued coefficients, where a = 1, 2, 3,…. These provide counterexamples to three recent conjectures concerning such facets. We also give a necessary and sufficient condition for a minimal imperfect graph to be an odd hole or an odd antihole and indicate that minimal imperfect K_1,3-free graphs satisfy the condition.     

Lower and upper bounds for the spanning tree with minimum branch vertices

We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.     

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.     

How tight is the corner relaxation? Insights gained from the stable set problem

The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations for the edge formulation of the maximum stable set problem in a graph.     

Composition of stable set polyhedra

Barahona and Mahjoub found a defining system of the stable set polytope for a graph with a cut-set of cardinality 2. We extend this result to cut-sets composed of a complete graph minus an edge and use the new theorem to derive a class of facets.     

Critical Facets of the Stable Set Polytope

Dedicated to the memory of Paul Erdős A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an -critical graph. We extend several results from the theory of -critical graphs to facets. The defect of a nontrivial, full-dimensional facet of the stable set polytope of a graph G is defined by . We prove the upper bound for the degree of any node u in a critical facet-graph, and show that can occur only when . We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewell [11]. As an application of these techniques we sharpen a result of Surányi [13] by showing that if an -critical graph has defect and contains nodes of degree , then the graph is an odd subdivision of . Received October 23, 1998     

Cutting planes for semidefinite relaxations based on triangle-free subgraphs

We show how to separate a doubly nonnegative matrix, which is not completely positive and has a triangle-free graph, from the completely positive cone. This method can be used to compute cutting planes for semidefinite relaxations of combinatorial problems. We illustrate our approach by numerical tests on the stable set problem.     

On the stable set polytope of a series-parallel graph

We give a short proof of Chvátal's conjecture that the nontrivial facets of the stable set polytope of a series-parallel graph all come from edges and odd holes.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and by CP Rail.     

An axiomatic duality framework for the theta body and related convex corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of “Schur Lifting” of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010.     

On the facial structure of set packing polyhedra

In this paper we address ourselves to identifying facets of the set packing polyhedron, i.e., of the convex hull of integer solutions to the set covering problem with equality constraints and/or constraints of the form . This is done by using the equivalent node-packing problem derived from the intersection graph associated with the problem under consideration. First, we show that the cliques of the intersection graph provide a first set of facets for the polyhedron in question. Second, it is shown that the cycles without chords of odd length of the intersection graph give rise to a further set of facets. A rather strong geometric property of this set of facets is exhibited.     

A comparison of two dual-based procedures for solving the p-median problem

We compare two dual-based procedures for solving the p-median problem. They rely upon alternative Lagrangean relaxations of the problem. We describe the algorithms and report on our computational experiments.     

Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

Bad news for chordal partitions

Reed and Seymour [1998] asked whether every graph has a partition into induced connected nonempty bipartite subgraphs such that the quotient graph is chordal. If true, this would have significant ramifications for Hadwiger's Conjecture. We prove that the answer is “no.” In fact, we show that the answer is still “no” for several relaxations of the question.     

First facets of the octahedron

A procedure is given for identifying the facets of the octahedron that are first intersected upon extending the edge of a polyhedral cone. The information generated by this procedure can be exploited to advantage by cut-search procedures for zero-one integer programming. Results are given which make it possible to determine the first two facets (or sets of “tied facets”) following the innermost facet with less effort than required to determine the innermost facet itself. Depending on the orientation of the extended edge relative to the octahedron, a number of successive additional facets may be determined with comparable ease.     

Facets for the cut cone II: Clique-web inequalities

We study new classes of facets for the cut coneC _n generated by the cuts of the complete graph onn vertices. This cone can also be interpreted as the cone of all semi-metrics onn points that are isometricallyl ₁-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets ofC _n . These new facets belong to the class of clique-web inequalities which generalize the hypermetric and cycle inequalities as well as the bicycle odd wheel inequalities.