Solving Unary Constraint Satisfaction Problem other than branch and bound

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).

• Unless these "SHOULD"s have weights attached to them, I don't see how you have enough information for an objective function here -- that is, to decide which of two meals is "better". May 20, 2017 at 20:18
• @j_random_hacker Thanks for advice, but I'm aware of that. At the moment, I am using a lump sum of degrees of violation of soft constraints (and "hard flexible" or rather "hard arbitrarily graded") for scoring. 0 for total satisfaction, 1 for total violation and an (arbitrarily assigned, but tied to constraint satisfaction function) number between 0 and 1 for partial violation. It's primitive, silly, wouldn't make sense for a real-life application, and I'd need to add a bit to my data structures just to compute Pareto front, but it's sufficient for now. May 21, 2017 at 6:18