完整圖k着​​色求解器

Question

我正在尋找一個完整的CSP求解器，這意味着它總是會找到一個解決方案，如果它存在並會告訴你，如果沒有解決方案存在。針對圖形着色優化的求解器是優選的，但不是必需的。有很多迭代算法/求解器，但我需要完整性（？）來完成我的工作。

我已經使用弱承諾搜索算法實現了自己的求解器，但是我確定有很多優化和基於線程的特性可以提高求解器的速度，並允許我增加變量的數量在我的模擬中使用。我意識到這是一個指數級的難題，但每一點點都會有所幫助！

Answer 1

有人有implementedMehrotra and Trick的分行價格法。我沒有使用這個代碼，但我相信這種方法是精確着色的最新技術。