A note on the split rank of intersection cuts (Q647399): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the split rank of intersection cuts |
scientific article |
Statements
A note on the split rank of intersection cuts (English)
0 references
23 November 2011
0 references
The author analyzes mixed integer programs with \(m\) integer variables, \(n\) nonnegative continuous variables and a restriction vector \(f\) with at least one non-integer component. In a branch-and-cut framework split cuts -- introduced by Egon Balas more than 35 years ago by using disjunctions for integer-valued inequalities -- have shown to be of certain value; by adding all possible split cuts to the linear programming relaxation \(M\) one gets the first split closure \(M^1\), which was shown to be a polyhedron. Applying the split closure procedure to the resulting set iteratively again yields the second split closure \(M^2,\dots,M^t,\dots\) The split rank of a valid inequality for the convex hull of the mixed integer set of solutions is defined as the smallest integer \(t\) , such that the inequality is valid for \(M^t\) (or can be infinite shown by simple examples where the facet-defining inequality cannot be obtained using split cuts). This rank indicates how difficult it is to obtain an inequality using split cuts. The main result of the paper shows a lower bound on the split rank of the class of intersection cuts (a general class due to Balas too): after having constructed a polyhedral subset of the lattice-free convex set \(P\), which contains the vector \(f\) in its interior, one looks for a number \(k\) of integer points that lie on different faces of \(P\); then \(\log_2 (k)\) is a lower bound for the rank. This result can be specialized for \(n\)-row mixing inequalities yielding a lower bound of \(\log_2(n+1)\). The proofs are based mainly on geometric arguments.
0 references
mixed integer programming
0 references
intersection cuts
0 references
split rank
0 references
lower bound
0 references