在 PySCIPOpt 的同一分支定界树中实现多个分支规则
Implementing multiple branching rules in the same branch and bound tree in PySCIPOpt
我想首先实现一个自定义分支规则(针对树顶部的几个节点),然后使用 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
我相信你能达到这个效果。 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”,尽管这并未反映在实际统计数据中...
我想首先实现一个自定义分支规则(针对树顶部的几个节点),然后使用 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
我相信你能达到这个效果。 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”,尽管这并未反映在实际统计数据中...