2
$\begingroup$

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple packages of each of these ingredients in various sizes.

I'll need at least 5kg of food to get me through the weekend, but I'm willing to carry up to 10kg of weight if it means I can achieve a more perfect balance of chocolate, marshmallow, and graham cracker. (My camping companions like s'mores, too.)

I really don't care about the weight, as long as it's in the range of 5-10kg. But the farther away from a 20/50/30 split, the sadder I'll be. :-(

I'm willing to devote some computational resources to this problem, but not too much; the weekend will be here before you know it. Can Computer Science help me?

$\endgroup$
1
$\begingroup$

This could be formulated as an ILP instance that searches for a feasible solution under your ratio constraints. However, you want to maintain the ratio as best as possible and not necessarily require it; therefore, we attempt to minimize the distance from this ratio by employing a Lagrangian relaxation of the constraints.

In this formulation $x_c$ is the 0-1 variable over each chocolate (similarly for marshmellow and graham cracker). $x_t$ is the integer variable that holds the number of selected items.

$$\min \lambda_c (\sum_c w_c x_c - .2 x_t) + \lambda_m (\sum_m w_m x_m - .5 x_t) + \lambda_g (\sum_g w_g x_g - .3 x_t)$$ $$s.t. \sum w_c x_c + \sum w_m x_m + \sum w_g x_g \leq x_t$$ $$\sum w_c x_c + \sum w_m x_m + \sum w_g x_g \leq 10$$ $$\sum w_c x_c + \sum w_m x_m + \sum w_g x_g \geq 5$$ $$ x_c \in \{0,1\}, x_g \in \{0,1\}, x_m \in \{0,1\}$$ $$x_t \geq 0$$

$\endgroup$
  • $\begingroup$ Unless you have 10s of 1000s of items in your pantry most off-the-shelf ILP solvers will blast through this in a few seconds. $\endgroup$ – Nicholas Mancuso Jan 12 '15 at 18:49
  • $\begingroup$ Very helpful, and thanks for the detailed expansion. The Lagrangian relaxation was not familiar to me, but it looks like just the ticket. $\endgroup$ – GSnyder Jan 13 '15 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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