1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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". $\endgroup$
    – j_random_hacker
    Commented May 20, 2017 at 20:18
  • $\begingroup$ @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. $\endgroup$
    – Dragomok
    Commented May 21, 2017 at 6:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'll give this a try now, thank you. And, just in case: I follow the usual custom of "wait a week or two before accepting even if there are no other answers". $\endgroup$
    – Dragomok
    Commented May 21, 2017 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.