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

Question

我想首先实现一个自定义分支规则(对于树顶的几个节点)，然后使用Scip实现香草完全强分支规则(或者其他一些规则，如伪成本规则)。这可以使用/通过扩展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)回调中决定返回一个dict。

{'result': pyscipopt.SCIP_RESULT.DIDNOTRUN}

这应该会通知SCIP，您的规则没有执行，应该跳过，在这种情况下，"relpscost“规则应该接管(请参阅这里)。

编辑:我不太清楚您的实例是什么样子，所以我在这里猜测:我认为您认为节点2处的多个调用是由于强分支造成的，这是正确的。您可以通过切换到另一个备份策略来进行检查，例如"mostinf“。

此外，在优化完成后，通过调用model.printStatistics()来检查统计数据确实很有帮助。我在cod105基准测试的“MIPlIB”实例上尝试了您的代码，并类似地找到了一组“未分支”输出。关于分支规则的(缩写)统计数据如下：

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

因此，回退规则实际上被多次调用。显然，“完全强”规则在内部调用"CustomRand“，尽管这没有反映在实际的统计数据中.