Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams
Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams
复制标题
使用零抑制二元决策图解决图着色的分支价格算法中的定价问题
DOI：
--
复制
发表时间：
2014
影响因子：
2.1
通讯作者：
S. Jacobson
中科院分区：
文献类型：
--
作者：
D. Morrison;E. Sewell;S. Jacobson
分支与价格算法将分支定界搜索与必须通过列生成解决的指数大小的 LP 公式相结合。不幸的是，整数编程的分支定界中使用的标准分支规则会干扰列生成例程的结构；因此，大多数此类算法采用替代分支规则来规避这一困难。本文展示了如何使用零抑制二元决策图 (ZDD) 来解决图着色问题的分支价格算法中的定价问题，即使存在分支决策施加的约束。这种方法有利于更直接的求解方法，并且可以提高列生成子例程的收敛性。
Branch-and-price algorithms combine a branch-and-bound search with an exponentially-sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch-and-bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram (ZDD) can be used to solve the pricing problem in a branch-and-price algorithm for the graph coloring problem, even in the presence of constraints imposed by branching decisions. This approach facilitates a much more direct solution method, and can improve convergence of the column generation subroutine.