Back to search

University of Glasgow

Pseudo-Boolean proof logging for constraint propagation algorithms

Abstract

dc:description.abstract

Proof logging is a way to increase trust in the conclusion reached by an algorithm. Alongside any answer, a proof logging algorithm should automatically output a mathematical certificate of correctness in a machine-checkable format. This can be of critical importance in areas where the results of algorithms have safety implications; are of academic mathematical significance; or simply have tangible effects on people’s lives. This thesis introduces new proof logging techniques in the area of constraint programming (CP). CP is a powerful algorithmic paradigm for modelling and solving problems expressed in terms of variables; possible values for those variables; and constraints on allowed combinations of values. The field has matured over the past several decades to the point where general-purpose solvers are routinely used to tackle large real-world problem instances efficiently. However, certification has remained a challenge and currently very few CP solvers implement proof logging. Part of the reason for this is the difficulty of capturing in a proof system the expressive, high-level reasoning techniques used by specialised constraint propagation algorithms. Expressivity and convenience need to be carefully balanced against trustworthy and efficient checking. The main objective of this work is to investigate the extent to which pseudo Boolean (PB) reasoning can be used to develop feasible proof-logging versions of state-of-the art constraint propagation algorithms. We use the VeriPB proof checker and its associated PB proof system based on 0-1 linear inequalities and cutting planes derivations, augmented with convenience and strengthening rules. VeriPB has previously been used in certification for a number of combinatorial solving paradigms, including for some constraint propagation and search techniques. We refine and build on this foundation, developing new PB proof logging methods for a number of important constraint propagators, with a particular focus on smart table, regular language membership, Hamiltonian circuit, and ternary multiplication constraints. Many of the techniques we develop can be generalised. They establish that, in principle, a wide variety of CP propagators are amenable to PB certification. We also implement our methods within a proof-logging CP solver, and present empirical evaluation in terms of logging overhead and checking time. This work opens a clear avenue to a future where solvers are more trustworthy and auditable. It also gives us fresh insights into the applied capabilities of PB reasoning, adding new techniques to the PB justification repertoire.

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McIlree, Matthew John

Subjects

dc:subject × 2

Rights

Language dc:language
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

McIlree, Matthew John. Pseudo-Boolean proof logging for constraint propagation algorithms. PhD thesis, University of Glasgow, 2026. https://doi.org/10.5525/gla.thesis.86049