2
$\begingroup$

I have heard of a famous problem called the "Wolf, Goat, and Cabbage Riddle" :(https://en.wikipedia.org/wiki/Wolf,_goat_and_cabbage_problem):

enter image description here

"Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage. The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?"

I have informally heard that this riddle can be seen as an optimization problem as it can be interpreted as a discrete optimization problem with integer constraints (i.e. certain combinations of items can not be left together). I have also heard that this riddle can appear in real life when there are thousands of objects and thousands of constraints (but I am not sure about this). It would be interesting to hear comments about this.

enter image description here

My Question: Does this "Wolf, Goat and Cabbage Riddle" have any relation to "Monge's Optimal Transport Problem"?

I am still trying to understand "Monge's Optimal Transport Problem" but in a general sense, it seems like this is related to the "Assignment Problem" seeking the "cheapest and fastest" way to transport items from one location to another location.

enter image description here

Is there any relationship between the "Wolf, Goat and Cabbage Riddle" and "Monge's Optimal Transport Problem"? Does (a more complex version of) the "Wolf, Goat and Cabbage Riddle" ever come up in real world Optimization Problems (e.g. scheduling and transportation)?

Improve this question
$\endgroup$
2
  • $\begingroup$ What is missing in my answer of your question? $\endgroup$
    – worldsmithhelper
    Mar 10, 2022 at 0:12
  • $\begingroup$ @ worldsmithhelpher: Hello! Nothing is missing from your answer - I was just interested in hearing more about how the "Wolf, Goat, Cabbage" Problem can be interpreted as an Optimization Problem. $\endgroup$
    – stats_noob
    Mar 10, 2022 at 0:50

2 Answers 2

Reset to default
3
$\begingroup$

According to my understanding Transportation theory which covers Monge's Optimal Transport Problem is not concerned with constraints temporary storage of incompatible goods. Furthermore most formulations have an time invariant transport map, meaning those formulation could not represent the time varieying differently directed flow of goods. Yes it would be possible to extend Optimal Transport problem to cover the "Wolf, Goat and Cabbage Riddle" case however calling that a relation is a bit strenous.

I am not aware of "these items can not be stored together contraints" in logisitics. Such constraints might occour in cryptography however in this case not a specific problem solved but a generic protocol would be used.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Just for clarity, there are constraints in logistics and transportations of the type "these items cannot be stored (or shipped) together". For example, in shipping items to stores, I doubt anyone ships strawberries, coffee beans, and chicken in the same trailer (I know this was an exaggeration, but such constraints exist) $\endgroup$
    – EhsanK ♦
    Feb 28, 2022 at 3:57
  • $\begingroup$ This is still not stored together but transported together which would have a different encoding. $\endgroup$
    – worldsmithhelper
    Mar 10, 2022 at 0:12
1
$\begingroup$

A fundamental difference between the riddle and either Monge's problem and the more common (in my experience) Hitchcock transportation problem is that the riddle is inherently a multiperiod problem (where we can think of a time period as the duration of one trip across the river). So you would need to extend either of those models by adding a time dimension and inventory variables for the number (0 or 1) of wolves, goats and cabbages on each side of the river.

A second fundamental difference is that flows are inherently discrete. If you attempt to formulate the problem as a multiperiod Hitchcock problem using exclusively continuous variables (so as to be a linear program), you will end up with fractional solutions where the farmer, for instance, leaves half a goat and half a head of cabbage untended at one point. (Arguably this might be okay, since the goat would presumably be dead and thus incapable of eating the cabbage.)

It is possible to formulate this as a multiperiod integer linear program, although that seems overkill for the original riddle.

Improve this answer
$\endgroup$

Your Answer

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

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