On the first Chvátal closure of the set covering polyhedron related to circulant matrices

We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chvátal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequalities previously reported in the literature. This family includes new facet-defining inequalities for the set covering polyhedron.     

Small Chvátal Rank

We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : A x ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.     

On the Chvátal–Gomory closure of a compact convex set

In this paper, we show that the Chvátal–Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver (Ann Discret Math 9:291–296, 1980) for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver in Ann Discret Math 9:291–296, 1980), rational ellipsoids (Dey and Vielma in IPCO XIV, Lecture Notes in Computer Science, vol 6080. Springer, Berlin, pp 327–340, 2010) and strictly convex bodies (Dadush et al. in Math Oper Res 36:227–239, 2011).     

The Chvátal closure of generalized stable sets in bidirected graphs

We consider the set of integral solutions of $Ax⩽b$, $x⩾0$, where A is the edge-vertex incidence matrix of a bidirected graph. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvátal closure in this case.     

A short proof for the polyhedrality of the Chvátal–Gomory closure of a compact convex set

Recently Schrijver’s open problem, whether the Chvátal–Gomory closure of an irrational polytope is polyhedral was answered independently in the seminal works of Dadush et al. (2011) and Dunkel and Schulz (2010); the former even applies to general compact convex sets. We present a very short, easily accessible proof.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube*

Gomorys and Chvátals cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvátal rank of the polyhedron is the number of rounds needed to obtain all valid inequalities. It is well known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is 2-dimensional, and if its integer hull is a 0/1-polytope.We show that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, we prove that the rank of every polytope contained in the n-dimensional 0/1-cube is at most n ² (1+log n). Moreover, we also demonstrate that the rank of any polytope in the 0/1-cube whose integer hull is defined by inequalities with constant coefficients is O(n).Finally, we provide a family of polytopes contained in the 0/1-cube whose Chvátal rank is at least (1 + ) n, for some > 0.* An extended abstract of this paper appeared in the Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization [20].     

Chvátal–Erdös Type Conditions for Hamiltonicity of Claw-Free Graphs

For a graph H, let \(\alpha (H)\) and \(\alpha ^{\prime }(H)\) denote the independence number and the matching number, respectively. Let \(k\ge 2\) and \(r>0\) be given integers. We prove that if H is a k-connected claw-free graph with \(\alpha (H)\le r\), then either H is Hamiltonian or the Ryjá c? ek’s closure \(cl(H)=L(G)\) where G can be contracted to a k-edge-connected \(K_3\)-free graph \(G_0^{\prime }\) with \(\alpha ^{\prime }(G_0^{\prime })\le r\) and \(|V(G_0^{\prime })|\le \max \{3r-5, 2r+1\}\) if \(k\ge 3\) or \(|V(G_0^{\prime })|\le \max \{4r-5, 2r+1\}\) if \(k=2\) and \(G_0^{\prime }\) does not have a dominating closed trail containing all the vertices that are obtained by contracting nontrivial subgraphs. As corollaries, we prove the following:

1. (a)
   A 2-connected claw-free graph H with \(\alpha (H)\le 3\) is either Hamiltonian or \(cl(H)=L(G)\) where G is obtained from \(K_{2,3}\) by adding at least one pendant edge on each degree 2 vertex;
    
2. (b)
   A 3-connected claw-free graph H with \(\alpha (H)\le 7\) is either Hamiltonian or \(cl(H)=L(G)\) where G is a graph with \(\alpha ^{\prime }(G)=7\) that is obtained from the Petersen graph P by adding some pendant edges or subdividing some edges of P.
    

Case (a) was first proved by Xu et al. [19]. Case (b) is an improvement of a result proved by Flandrin and Li [12]. For a given integer \(r>0\), the number of graphs of order at most \(\max \{4r-5, 2r+1\}\) is fixed. The main result implies that improvements to case (a) or (b) by increasing the value of r and by enlarging the collection of exceptional graphs can be obtained with the help of a computer. Similar results involved degree or neighborhood conditions are also discussed.

     

The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A classical theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs—a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.     

The Chvátal–Erdös Condition for Group Connectivity in Graphs

Let G be a graph and A an abelian group with the identity element 0 and ${|A| \geq 4}$ . Let D be an orientation of G. The boundary of a function ${f: E(G) \rightarrow A}$ is the function ${\partial f: V(G) \rightarrow A}$ given by ${\partial f(v) = \sum_{e \in E^+(v)}f(e) - \sum_{e \in E^-(v)}f(e)}$ , where ${v \in V(G), E^+(v)}$ is the set of edges with tail at v and ${E^-(v)}$ is the set of edges with head at v. A graph G is A-connected if for every b: V(G) → A with ${\sum_{v \in V(G)} b(v) = 0}$ , there is a function ${f: E(G) \mapsto A-\{0\}}$ such that ${\partial f = b}$ . A graph G is A-reduced to G′ if G′ can be obtained from G by contracting A-connected subgraphs until no such subgraph left. Denote by ${\kappa^{\prime}(G)}$ and α(G) the edge connectivity and the independent number of G, respectively. In this paper, we prove that for a 2-edge-connected simple graph G, if ${\kappa^{\prime}(G) \geq \alpha(G)-1}$ , then G is A-connected or G can be A-reduced to one of the five specified graphs or G is one of the 13 specified graphs.     

A lower bound on the Chvátal-rank of Antiwebs

In [Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of linear relaxations of the stable set polytope, International Transactions in Operational Research 17 (2010), pp. 827–849; Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of Antiwebs, Electronic Notes in Discrete Mathematics 36 (2010), pp. 183–190] we study the Chvátal-rank of the edge constraint and the clique constraint stable set polytopes related to antiwebs. We present schemes for obtaining both upper and lower bounds. Moreover, we provide an algorithm to compute the exact values of the Chvátal-rank for all antiwebs with up to 5,000 nodes. Here we prove a lower bound as a closed formula and discuss some cases when this bound is tight.     

Extensions and consequences of Chvátal-Erdős' theorem

A classical result of Chvátal and Erds states that a graph with independence number smaller or equal to its connectivity contains a Hamilton cycle. In this note we discuss some extensions of this theorem and show how they can be used to proof several other results in hamiltonian graph theory. Although several of the results are known, the proofs in this note are in general essentially shorter than the original proofs, and also give an indication of the relations between the results.Supported by a grant from the Natural Sciences and Engineering Research Council of Canada     

Pancyclism in Chvátal-Erdös's graphs

LetG = (X, E) be a simple graph of ordern, of stability numberα and of connectivityk withα ≤ k. The Chvátal-Erdös's theorem [3] proves thatG is hamiltonian. We have investigated under these conditions what can be said about the existence of cycles of lengthl. We have obtained several results:

1. IfG ≠ K _k,k andG ≠ C ₅,G has aC _n?1 .
2. IfG ≠ C ₅, the girth ofG is at most four.
3. Ifα = 2 and ifG ≠ C ₄ orC ₅,G is pancyclic.
4. Ifα = 3 and ifG ≠ K _3,3,G has cycles of any length between four andn.
5. IfG has noC ₃,G has aC _n?2 .

     

Generalized Chvátal-Gomory closures for integer programs with bounds on variables

Mathematical Programming - Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of...