Renata Sotirov We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more
The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more
In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more
This paper is an in-depth analysis of the generalized $\vartheta$-number of a graph. The generalized $\vartheta$-number, $\vartheta_k(G)$, serves as a bound for both the $k$-multichromatic number of a graph and the maximum $k$-colorable subgraph problem. We present various properties of $\vartheta_k(G)$, such as that the series $(\vartheta_k(G))_k$ is increasing and bounded above by the order … Read more
We study the Quadratic Cycle Cover Problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the … Read more
The maximum $k$-colorable subgraph (M$k$CS) problem is to find an induced $k$-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the M$k$CS problem that considers various semidefinite programming relaxations including their theoretical and numerical comparisons. To simplify these relaxations we exploit the symmetry arising from permuting the colors, … Read more
We consider both facial and symmetry reduction techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. The combination of facial and symmetry reduction leads to a significant improvement in both numerical stability and running time for both the ADMM and interior … Read more
The Bandwidth Problem asks for a simultaneous permutation of the rows and columns of the adjacency matrix of a graph such that all nonzero entries are as close as possible to the main diagonal. This work focuses on investigating novel approaches to obtain lower bounds for the bandwidth problem. In particular, we use vertex partitions … Read more
The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between incident arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various … Read more
Given an instance of the quadratic shortest path problem (QSPP) on a digraph $G$, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on $G$ such that the associated costs for both problems are equal for every $s$-$t$ path in $G$. We prove here that the … Read more