Asymptotic best-variable branching conjecture for MVB
Asymptotic best-variable branching conjecture for MVB
Let an MVB instance have variables indexed by , and let be the ratio associated with variable ; write
Asymptotic best-variable branching conjecture. For each instance of MVB, there exists a gap such that, for all gaps greater than , variable is always branched on at the root node.
The conjecture asserts eventual stabilization of the root branching choice at the variable with the smallest asymptotic growth ratio. The surrounding result identifies the MVB growth ratio with the best single-variable branching ratio, but the eventual root-choice assertion is left as a conjecture.
Sources & referencesView supporting material
Primary source
Pierre Le Bodic and George L. Nemhauser, “An Abstract Model for Branching and its Application to Mixed Integer Programming”, arXiv:1511.01818 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.