A polytope P ⊆ [ 0 , 1 ] n is said to have the persistency property if for every vector c ∈ R n and every c -optimal point x ∈ P , there exists a c -optimal integer point y ∈ P ∩ { 0 , 1 } n such that x i = y i for each i ∈ { 1 , … , n } with x i ∈ { 0 , 1 } . In this paper, we consider a relaxation of the persistency property called 1-persistency . We study the family Q of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as Q - persistent graphs. We provide sufficient conditions for a graph to be Q -persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of ( k , U ) -umbrella graphs, and study which of them belong to Q . The property of being Q -persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family Q , i.e., minimally not Q -persistent (mn Q ) graphs. In this line, we identify some mn Q ( k , U ) -umbrella graphs and also other forbidden minimal structures for Q -persistency outside this family (named as whale graphs).

Given a graph G = (V,E) , a set of consecutive colors, and a demand vector d ∈ ℤ + |V| , the interval coloring problem asks for an assignment of d i consecutive colors to each vertex i ϵ V , in such a way that no two adjacent vertices are assigned the same color. Inspired by a situation arising in the allocation of ships to berths, in this work we propose to consider the split-interval coloring problem , which asks to assign at most two disjoint color intervals to each vertex in such a way that each vertex i ϵ V receives a total of d i colors. We explore a natural integer programming formulation for this NP-hard problem and its associated polytope. We state some relations to the interval coloring polytope, including lemmas allowing to translate valid inequalities between these two polytopes. We also present several valid inequalities and study conditions ensuring that these inequalities induce facets of the associated polytope.

The power dominating set problem (PDS) is a graph optimization problem with applications related to the control and monitoring of electric power systems using devices called phasor measurement units (PMUs). The objective of PDS is to find a minimum set of vertices on which to install PMUs that allow monitoring all remaining vertices by recursively applying two observation rules. In particular, the domination rule assumes that a vertex with a PMU can monitor all its neighbors. In real-world applications, PMUs have a predefined number of channels that limit the number of neighbors that they can monitor. This work proposes a novel integer linear programming formulation for the PDS variant that considers PMUs with channel limitation. The formulation is based on a set of constraints to forbid circular precedences that might arise in the application of the observation rules. As the number of constraints grows exponentially, an algorithm is developed to handle them dynamically (as lazy constraints) with an efficient separation routine. Computational experiments are performed on benchmark instances with up to 13.659 vertices to compare the performance of the new formulation with others adapted from the PDS literature. An interesting behavior is observed, where the best-performing formulation strongly depends on the number of limited channels. In particular, the new formulation is effective in instances with moderate channel limitation.

Given a vector $y \in \mathbb{R}^n$ and a matrix $H \in \mathbb{R}^{n\times m}$, the sparse approximation problem $\mathcal P_{0/p}$ asks for a point $x$ such that $\|y - Hx\|_p \leq \alpha$, for a given scalar $\alpha$, minimizing the size of the support $\|x\|_0 := \#\{j \ |\ x_j \neq 0 \}$. Existing convex mixed-integer programming formulations for $\mathcal P_{0/p}$ are of a kind referred to as “big-$M$”, meaning that they involve the use of a bound $M$ on the values of $x$. When a proper value for $M$ is not known beforehand, these formulations are not exact, in the sense that they may fail to recover the wanted global minimizer. In this work, we study the polytopes arising from these formulations and derive valid inequalities for them. We first use these inequalities to design a branch-and-cut algorithm for these models. Additionally, we prove that these inequalities are sufficient to describe the set of feasible supports for $\mathcal P_{0/p}$. Based on this result, we introduce a new (and the first to our knowledge) $M$-independent integer linear programming formulation for $\mathcal P_{0/p}$, which guarantees the recovery of the global minimizer. We propose a practical approach to tackle this formulation, which has exponentially many constraints. The proposed methods are then compared in computational experimentation to test their potential practical contribution.