  Fast domain propagation of linear constraints has become a crucial component
of today's best algorithms and solvers for mixed integer programming and
pseudo-boolean optimization to achieve peak solving performance. Irregularities
in the form of dynamic algorithmic behaviour, dependency structures, and
sparsity patterns in the input data make efficient implementations of domain
propagation on GPUs and, more generally, on parallel architectures challenging.
This is one of the main reasons why domain propagation in state-of-the-art
solvers is single thread only. In this paper, we present a new algorithm for
domain propagation which (a) avoids these problems and allows for an efficient
implementation on GPUs, and is (b) capable of running propagation rounds
entirely on the GPU, without any need for synchronization or communication with
the CPU. We present extensive computational results which demonstrate the
effectiveness of our approach and show that ample speedups are possible on
practically relevant problems: on state-of-the-art GPUs, our geometric mean
speed-up for reasonably-large instances is around 10x to 20x and can be as high
as 180x on favorably-large instances.
