Asymptotic best-variable branching conjecture for MVB

Let an MVB instance have variables indexed by i=1,,ni=1,\dots,n, and let φi\varphi_i be the ratio associated with variable ii; write

i=arg,minjφj.i=\operatorname*{\arg\\,\min}_j \varphi_j.

Asymptotic best-variable branching conjecture. For each instance of MVB, there exists a gap HH such that, for all gaps greater than HH, variable ii 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.