Solving Unary Constraint Satisfaction Problem other than branch and bound
A pragmatic approach will be to formulate this as an instance of integer linear programming, and feed the system to an off-the-shelf ILP solver.  The details of exactly how to do that will depend on the specific kinds of constraints you have.  There are many tutorials on integer linear programming, so you might start there.

If you need the solution to be deterministic (so solving the same problem multiple times is guaranteed to give the answer), and if you're not sure whether your ILP solver is deterministic, you can define an ordering on solutions (e.g., lexicographic search) and then use binary search to find the "first" valid solution out of all optimal solutions.