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
In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip … Read more