Answers are grounded in this paper and cite their sources.
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 F of k-sparsity, and a given k-sparse split set S, let F(S) be the minimum number of split sets from the list F, whose union contains S ∩ [0, \ 1]ⁿ. Let the covering number of F be the maximum value of 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 k/2 for k ≥ 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 ≤ 4.
No takes yet. Share an insight, caveat, or question.
Dey et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: