Branching with a pre-specified finite list of $k$-sparse split sets for binary MILPs

Abstract

When branching for binary mixed integer linear programs with disjunctions of sparsity level $2$, we observe that there exists a finite list of $2$-sparse disjunctions, such that any other $2$-sparse disjunction is dominated by one disjunction in this finite list. For sparsity level greater than $2$, we show that a finite list of disjunctions with this property cannot exist. This leads to the definition of covering number for a list of splits disjunctions. Given a finite list of split sets $\mathcal{F}$ of $k$-sparsity, and a given $k$-sparse split set $S$, let $\mathcal{F}(S)$ be the minimum number of split sets from the list $\mathcal{F}$, whose union contains $S\cap [0,1{]}^n$. Let the covering number of $\mathcal{F}$ be the maximum value of $\mathcal{F}(S)$ over all $k$-sparse split sets $S$. We show that the covering number for any finite list of $k$-sparse split sets is at least $\lfloor k/2\rfloor$ for $k\ge 4$. We also show that the covering number of the family of $k$-sparse split sets with coefficients in $\{-1,0,1\}$ is upper bounded by $k-1$ for $k\le 4$.