We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … Read more
Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines … Read more
Given vectors $a,c\in Z^n$ and $b\in Z$, we consider the (unbounded) knapsack optimization problem $P:\,\min\{c’x\,\vert\, a’x=b;\,x\in N^n\}$. We compute the minimum value $p^*$ using techniques from complex analysis, namely Cauchy residue technique to integrate a function in $C^2$, the $Z$-transform of an appropriate function related to $P$. The computational complexity depends on $s:=\sum_{a_j} a_j$, not … Read more
Hierarchies of semidefinite relaxations for $0/1$ polytopes have been constructed by Lasserre (2001a) and by Lov\’asz and Schrijver (1991), permitting to find the cut polytope of a graph on $n$ nodes in $n$ steps. We show that $\left\lceil {n\over 2} \right\rceil$ iterations are needed for finding the cut polytope of the complete graph $K_n$. Citation … Read more
In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs … Read more
We provide two algorithms for computing the volume of the convex polytope $\Omega:=\{x\in \R^n_+ \,|\,Ax\leq b\}$, for $A\in\R^{m\times n}, b\in\R^n$. The computational complexity of both algorithms is essentially described by $n^m$, which makes them especially attractive for large $n$ and relatively small $m$, when the other methods with $O(m^n)$ complexity fail. The methodology which differs … Read more
The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most $k$ edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits. Article Download View Facets of The Cardinality Constrained Circuit … Read more
We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K. We present here a new formulation of the problem and derive facet results for different classes … Read more
In this article we introduce a theory of convexity for the lattices of integer points, which we call a theory of discrete convexity. In particular, we obtain generalizations of Edmonds’ polymatroid intersection theorem and the Hoffman-Kruskal theorem as consequences of our constructions. Citation Advances in Mathematics (to appear) Article Download View Discrete convexity and unimodularity. … Read more
We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications … Read more