# Can the “goat cabbage wolf” problem be solved using integer programming?

Question:

Can you solve the "goat cabbage wolf" problem using integer programming.

If so could I get an outline of the solution or a reference to one?

OK, I'll bite.

I could implement this using the concept of 'inventory'. After each trip we have: $$inv_{trip,side,item} = inv_{trip-1,side,item} + delivered_{trip,side,item} - takenaway_{trip,side,item}$$ We also have initial inventory and required final inventory. The equations look like:

The equations to forbid certain configurations are similar to what I suggested here.

The main decisions looks like:

----     64 VARIABLE pax.L  items taken on each trip

wolf        goat     cabbage

trip1.L2R                       1
trip2.L2R           1
trip2.R2L                       1
trip3.L2R                                   1
trip4.L2R                       1