Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more
One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more
We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more
Modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. However, some authors pointed out drawbacks of the modularity, the main issue of which is resolution limit. Resolution limit refers to the sensitivity of the modularity to the … Read more
In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding … Read more
We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more
We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact … Read more
The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic … Read more
We present a coordinate ascent method for a class of semidefinite programming problems that arise in non-convex quadratic integer optimization. These semidefinite programs are characterized by a small total number of active constraints and by low-rank constraint matrices. We exploit this special structure by solving the dual problem, using a barrier method in combination with … Read more
The purpose of this paper is to solve the 0-1 k-item quadratic knapsack problem (kQKP), a problem of maximizing a quadratic function subject to two linear constraints.We propose an exact method based on semide nite optimization. The semide nite relaxation used in our approach includes simple rank one constraints, which can be handled efficiently by interior point … Read more