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.     

Optimizing over the first Chvátal closure

How difficult is, in practice, to optimize exactly over the first Chvátal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Can the first-closure optimization be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvátal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvátal closure for a set of ILP problems from MIPLIB 3.0 and 2003. We also report, for the first time, the optimal solution of a very hard instance from MIPLIB 2003, namely nsrand-ipx, obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.     

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.     

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).     

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.     

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.     

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–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 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.     

Sharp Bounds on the Aα-index of Graphs in Terms of the Independence Number

Acta Mathematicae Applicatae Sinica, English Series - Given a graph G, the adjacency matrix and degree diagonal matrix of G are denoted by A(G) and D(G), respectively. In 2017, Nikiforov[24]...     

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.     

Bounds on the value of information in uncertain decision problems II†

In most stochastic decision problems one has the opportunity to collect information that would partially or totally eliminate the inherent uncertainty. One wishes to compare the cost and value of such information in terms of the decision maker's preferences to determine an optimal information gathering plan. The calculation of the value of information generally involves oneor more stochastic recourse problems as well as one or more expected value distribution problems. The difficulty and costs of obtaining solutions to these problems has led to a focus on the development of upper and lower bounds on the various subproblems that yield bounds on the value of information. In this paper we discuss published and new bounds for static problems with linear and concave preference functions for partial and perfect information. We also provide numerical examples utilizing simple production and investment problems that illustrate the calculations involved in the computation of the various bounds and provide a setting for a comparison of the bounds that yields some tentative guidelines for their use. The bounds compared are the Jensen's Inequality bound,the Conditional Jensen's Inequality bound and the Generalized Jensen and Edmundson-Madansky bounds.     

The Turán-type inequality in the space L0 on the unit interval

Analysis Mathematica - Let P(x) be an arbitrary algebraic polynomial of degree n with all zeros in the unit interval ?1 ≤ x ≤ 1. We establish the Turán-type inequality...     

Estimates for the Upper Bounds of the First Eigenvalue on Submanifolds

ＥｓｔｉｍａｔｅｓｆｏｒｔｈｅＵｐｐｅｒＢｏｕｎｄｓｏｆｔｈｅＦｉｒｓｔＥｉｇｅｎｖａｌｕｅｏｎＳｕｂｍａｎｉｆｏｌｄｓ祁锋，于霖泉，雒秋明ＥｓｔｉｍａｔｅｓｆｏｒｔｈｅＵｐｐｅｒＢｏｕｎｄｓｏｆｔｈｅＦｉｒｓｔＥｉｇｅｎｖａｌｕｅｏｎＳｕｂｍａｎｉ...     

Note on the Cantor–Bendixson Rank of Limit Groups

We show that the Cantor–Bendixson rank of a limit group is finite as well as that of a limit group of a linear group.     

Sufficiency of Kalman’s Rank Condition for the Approximate Boundary Controllability on an Annular Domain*

In this paper the author establishes the sufficiency of Kalman’s rank condition on the approximate boundary controllability at a finite time for diagonalizable systems on an annular domain in higher dimensional case.