0

我想最初实现一个自定义分支规则（对于树顶部的几个节点），然后使用 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
4

1 回答 1

0

我相信你可以达到这个效果。SCIP 有几个分支规则，并根据它们的优先级一一执行，直到其中一个产生结果。

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

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

{'result': pyscipopt.SCIP_RESULT.DIDNOTRUN}

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

编辑：对我来说，您的实例的外观不是很明显，所以我在这里猜测一下：我认为您假设节点 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”，尽管这并未反映在实际统计数据中......

于 2022-02-26T19:55:30.413 回答