I tried a couple of times long time ago to solve them with cp/integer programming.

The interviewers were clueless so after 10 minutes of trying to explain to them I quit and fell back to just writing the freaking algo they were expecting to see.