在 PySCIPOpt 的同一分支定界树中实现多个分支规则

Question

我想首先实现一个自定义分支规则（针对树顶部的几个节点），然后使用 Scip 实现的香草完全强分支规则（或一些其他规则，如 pseudocost）。这有可能做 using/by 扩展吗 PySCIPOpt?

import pyscipopt as scip
import random

class oddevenbranch(scip.Branchrule):

def branchexeclp(self, allowaddcons):
    '''
    This rule uses the branching rule I have defined if the node number is odd, 
    and should use strong branching otherwise.
    '''
    node_ = self.model.getCurrentNode()
    num = node_.getNumber()
    if num % 2 == 1:
        candidate_vars, *_ = self.model.getLPBranchCands()
        branch_var_idx = random.randint(0,len(candidate_vars)-1)
        branch_var = candidate_vars[branch_var_idx]
        self.model.branchVar(branch_var)
        result = scip.SCIP_RESULT.BRANCHED
        return {"result": result}

    else:
        print(num, ': Did not branch')
        result = scip.SCIP_RESULT.DIDNOTRUN
        return {"result": result}

if __name__ == "__main__":

    m1 = scip.Model()
    m1.readProblem('xyz.mps') # Used to read the instance
    m1.setIntParam('branching/fullstrong/priority', 11000)

    branchrule = oddevenbranch()
    m1.includeBranchrule(branchrule=branchrule,
                        name="CustomRand", # name of the branching rule
                        desc="",           # description of the branching rule
                        priority=100000,   # priority: set to this to make it default
                        maxdepth=-1,       # maximum depth up to which it will be used, or -1 for no restriction
                        maxbounddist=1)    # maximal relative distance from current node's dual bound to primal 

    m1.optimize()

我想知道是什么导致了这种行为。是否需要多次调用分支才能进行强分支？

2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch
2 : Did not branch

Answer 1

我相信你能达到这个效果。 SCIP有多个分支规则，按照优先级一条一条执行，直到其中一条产生结果。

默认规则“relpscost”的优先级为 10000，因此您应该创建一个具有更高优先级的自定义规则。

如果你不想在一个节点（树的更深处）使用你自己的规则，你可以在你的规则的branchexeclp(allowedcons)回调中决定return一个字典

{'result': pyscipopt.SCIP_RESULT.DIDNOTRUN}

这应该通知 SCIP 您的规则没有执行并且应该被跳过，在这种情况下，“relpscost”规则应该接管（参见 here）。

编辑：我不太清楚你的实例是什么样子的，所以我在这里猜测了一下：我认为你假设节点 2 的多次调用是由于强分支是正确的。您可以通过切换到另一个备份策略来检查，例如“mostinf”。

此外，在优化完成后通过调用 model.printStatistics() 查看统计信息非常有帮助。我在 MIPlIB 基准测试的“cod105”实例上尝试了您的代码，同样发现了一组“未分支”输出。有关分支规则的（缩写）统计数据如下：

Branching Rules    :   ExecTime  SetupTime   BranchLP  BranchExt   BranchPS    Cutoffs    DomReds       Cuts      Conss   Children
  CustomRand       :       0.00       0.00          1          0          0          0          0          0          0          2
  fullstrong       :       5.32       0.00          7          0          0          0          7          0          3          0

所以回退规则实际上被调用了好几次。显然，“fullstrong”规则在内部调用了“CustomRand”，尽管这并未反映在实际统计数据中...

在 PySCIPOpt 的同一分支定界树中实现多个分支规则

Implementing multiple branching rules in the same branch and bound tree in PySCIPOpt

python

scip

pyscipopt