Given a graph $G=(V,E)$ where $|V|=n$ and $|E|=m$. Graph partitioning problems on $G$ are to find a partition of the vertices in $V$ into clusters satisfying several additional constraints in order to minimize or maximize the number (or the weight) of the edges whose endnodes do not belong to the same cluster. These problems are … Read more
Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not “under control” from a polyhedral point of view. The equivalence between optimization and separation suggests the existence of integer programming formulations for these problems whose associated polytopes admit elegant characterizations. In this work we … Read more
We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem … Read more
The limited predictability and high variability of renewable generations has brought significant challenges on the real-time operation of bulk power systems. This paper proposes the concept of real-time dispatchability (RTDA) of power systems with variable energy resources, which focuses on investigating the impact of operating constraints and the cost of corrective actions on the flexibility … Read more
We investigate structural properties of the completely positive semidefinite cone, consisting of all the nxn symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of … Read more
In this paper, we investigate the two-period subproblems proposed by Akartunal{\i} et al. (2014) for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds for these problems. In particular, we study the polyhedral structure of the mixed integer sets related to two relaxations of these subproblems for the special case of … Read more
In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two … Read more
Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more
In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner … Read more
We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more