Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves … Read more
Given an undirected graph and a positive integer k, the maximum k-colorable subgraph problem consists of selecting a k-colorable induced subgraph of maximum cardinality. The natural integer programming formulation for this problem exhibits two kinds of symmetry: arbitrarily permuting the color classes and/or applying a non-trivial graph automorphism gives equivalent solutions. It is well known … Read more
We provide a complete characterization of all polytopes P ⊆ [0,1]^n with empty integer hull whose Gomory-Chvátal rank is n (and, therefore, maximal). In particular, we show that the first Gomory- Chvátal closure of all these polytopes is identical. Article Download View Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank
We show that half-integral polytopes obtained as the convex hull of a random set of half-integral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability — even if the size of the set relative to the total number of half-integral points of the cube tends to 0. The high rank … Read more
In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation … Read more
Although well studied, important questions on the rank of the Chvátal-Gomory operator when restricting to polytopes contained in the n-dimensional 0/1 cube have not been answered yet. In particular, the question on the maximal rank of the Chvátal-Gomory procedure for this class of polytopes is still open. So far, the best-known upper bound is O(n^2 … Read more
We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more
Ryser’s conjecture postulates that, for $r$-partite hypergraphs, $\tau \leq (r-1) \nu$ where $\tau$ is the covering number of the hypergraph and $\nu$ is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where $r \leq 5$. In this paper, we … Read more
We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes. Citation L. Galli & A.N. … Read more
Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover … Read more