An Auditable Constraint Programming Solver

We describe the design and implementation of a new constraint programming solver that can produce an auditable record of what problem was solved and how the solution was reached. As well as a solution, this solver provides an independently verifiable proof log demonstrating that the solution is correct. This proof log uses the VeriPB proof system, which is based upon cutting planes reasoning with extension variables. We explain how this system can support global constraints, variables with large domains, and reformulation, despite not natively understanding any of these concepts. 2012 ACM Subject Classification Theory of computation → Logic and verification; Theory of computation → Discrete optimization Supplementary Material Source code for the solver described in this paper can be found here: (Source Funding Stephan Gocht : Supported by the Swedish Research Council grant 2016-00782. Ciaran McCreesh : Supported by a Royal Academy of Engineering research fellowship. Jakob Nordström : Supported by the Swedish Research Council grant 2016-00782 and the Independent Research Fund Denmark grant 9040-00389B.

我们描述了一种新的约束规划求解器的设计与实现，该求解器能够生成关于所解决问题以及如何得到解决方案的可审计记录。除了解决方案之外，此求解器还提供了一个可独立验证的证明日志，用以证明该解决方案是正确的。这个证明日志使用了VeriPB证明系统，该系统基于带有扩展变量的切割平面推理。我们解释了尽管该系统本身并不理解全局约束、大定义域变量以及重新公式化这些概念，但它如何能够支持它们。 2012 ACM学科分类 计算理论→逻辑与验证；计算理论→离散优化 补充材料 本文所述求解器的源代码可在此处找到：（来源 资金来源 斯蒂芬·戈赫特：由瑞典研究委员会2016 - 00782号资助支持。 西亚兰·麦克里什：由英国皇家工程院研究奖学金支持。 雅各布·诺德斯特伦：由瑞典研究委员会2016 - 00782号资助以及丹麦独立研究基金9040 - 00389B号资助支持。