Solving Unary Constraint Satisfaction Problem other than branch and bound

Question

I am solving a problem of planning a meal, where I need to fulfill requests such as "create a two-dish meal that MUST have at most 2g of fat, the first dish MUST have 400kcal and SHOULD have at least 10g of protein, and the second dish MUST have 100kcal" by returning a list of dishes from a predefined list. In other words, it takes soft/hard constraints on a meal as a whole and sets of soft/hard constraint on each dish slot as an input, and outputs an assigment of dishes to dish slots.

I modelled it as a Constraint Satisfaction Problem with all dish constraints being unary constraints and meal constraints being used for accepting/rejecting a solution as well as ranking. I wrote Depth-First Branch and Bound roughly following [1] (shortly, it constructs depth-first a tree of all possible assignments and prunes branches with a dish violating its constraints) and it works pretty well.(*)

The problem is, I need another algorithm for solving that problem and - for reasons I can't change - it needs to be fully deterministic. Which is problematic, since:

• the whole meal planning research focuses on using various flavours of artificial intelligence,
• the few research papers that don't use AI, use onthologies and rule-based reasoning, but offer no details and constructing such is outside of my time budget and capabilites,
• all other algorithms I could find for solving Constraint Satisfaction Problem focus on the ones with binary constraints.

I have tried to find such algorithm for about two weeks, but found nothing. I feel like I'm missing an obvious solution, but I can't quite put my finger on it.

---

(*) Of course, I plan to improve it by appriopriately integrating meal constraints into the search.

---

[1] Sundmark, Niclas. "Design and implementation of a constraint satisfaction algorithm for meal planning." (2005).