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
The question as to whether the Gomory-Chvatal closure of a non-rational polytope is a polytope has been a longstanding open problem in integer programming. In this paper, we answer this question in the affirmative, by combining ideas from polyhedral theory and the geometry of numbers. ArticleDownload View PDF
In this paper we consider a relaxation of the corner polyhedron introduced by Andersen et al., which we denote by RCP. We study the relative strength of the split and triangle cuts of RCP’s. Basu et al. showed examples where the split closure can be arbitrarily worse than the triangle closure under a `worst-cost’ type … 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
The cutting plane tree (CPT) algorithm provides a finite disjunctive programming procedure to obtain the solution of general mixed-integer linear programs (MILP) with bounded integer variables. In this paper, we present our computational experience with variants of the CPT algorithm. Because the CPT algorithm is based on discovering multi-term disjunctions, this paper is the first … Read more
We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined recently in another paper). We then extend this observation to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables provided that … Read more
We will analyze mixed 0/1 second order cone programs where the fractional and binary variables are solely coupled via the conic constraints. For this special type of mixed-integer second order cone programs we devise a cutting-plane framework based on the generalized Benders cut and an implicit Sherali-Adams reformulation. We show that the resulting cuts are … Read more
We provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables. Under a simple probabilistic model of the problem parameters, we show that a simple split cut, i.e. a Gomory cut, is more likely to be better than a type 1 triangle cut in … Read more
Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. … Read more
In this paper, we prove that the Chvatal-Gomory closure of a set obtained as an intersection of a strictly convex body and a rational polyhedron is a polyhedron. Thus, we generalize a result of Schrijver which shows that the Chvatal-Gomory closure of a rational polyhedron is a polyhedron. ArticleDownload View PDF