How are these recent approaches different from OPIUM[1] from 2007? 0install is based around this algorithm. Also as far as I know Debian and FreeBSD both offer options to resolve dependencies using SAT solvers.
Also there is zypper, the package manager of OpenSUSE and SLES. That's where I first heard about this usage of SAT, around 10 years ago.
https://en.wikipedia.org/wiki/ZYpp
Eclipse's P2 has also been using a SAT solver for quite some time [0].