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).
Solving Unary Constraint Satisfaction Problem other than branch and bound
algorithms;branch and bound;planning
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.