Ryan-Foster Branchingとは

 0/1　Branchingだと、1側が重いのに比べて0側は、軽い、と言うかあまり効かないことが多いです。こうした偏りを是正する方法として、Ryan-Foster　Branchingと言う方法があります。

例えば、

休休　A

勤勤　B

休勤　C

勤休　D

A/B とC/DでBranchingします。比較として、通常ブランチ

休

～休み

を考えてみます。休＝１でブランチとすると、これはかなり強い限定になります。しかし、～休=0のブランチは、休み以外を選択するわけで、弱い限定になります。この傾向はシフト数が多くれば多いほど、強まります。１が強い限定を生み、0が弱い限定しか生まない、ということは、Tree構築においてバランスが悪い結果となります。1ブランチの枝は短いのに対して0枝は、長い枝になります。なので、なるべく同じ確率となるようにしたい訳です。これが、Ryan-Foster　Branchの背景になります。

複雑な割には、効果が少ないと判断して、スケジュールナースでは採用していませんが、SCIPでは、割に使っているようです。

SCIP Doxygen Documentation: Ryan/Foster branching