# Alcuin's River Crossing

TomSym implementation of GAMS Example (CROSS,SEQ=191)

A farmer carrying a bushel of corn and accompanied by a goose and a wolf came to a river. He found a boat capable of transporting himself plus one of his possessions - corn, goose, or wolf - but no more. Now, he couldn't leave the corn alone with the goose, nor the goose alone with the wolf, else one would consume the other. Nevertheless, he succeeded in getting himself and his goods across the river safely.

Borndoerfer, R, Groetschel, M, and Loebel, A, Alcuin's Transportation Problem and Integer Programming. Konrad Zuse Zentrum for Informationstechnik, Berlin, 1995.

Contributed by Soren Nielsen, Institute for Mathematical Sciences University of Copenhagen

i: items (goose, wolf, corn)

t: time (t1-t10);

% Crossing - near to far is +1 - far to near -1 dirt = (-1).^((1:10)'-1); % 1 if the item is on the far side at time t toms 3x10 integer y % binary % crossing the river cross = tom('cross',3,10); %toms 3x10 cross toms 10x1 done % all items on far side toms nocross % number of non crossing periods cbnd = {0 <= y <= 1 % y is binary, rest positive cross >= 0 done >= 0 nocross >= 0}; % Cross definition eq1 = {}; for i=1:3 for t=1:9 eq1 = {eq1; y(i,t+1) == y(i,t) + dirt(t)*cross(i,t)}; end end % Everything on far side eq2 = {}; for i=1:3 for t=1:10 eq2 = {eq2; done(t) <= y(i,t)}; end end % Limit cross eq3 = {}; for t=1:9 eq3 = {eq3; sum(cross(:,t)) <= 1}; end % Eat none 1 eq4 = {}; for t=1:10 eq4 = {eq4; dirt(t)*(y(1,t) + y(2,t) - 1) <= done(t)}; end % Eat none 2 eq5 = {}; for t=1:10 eq5 = {eq5; dirt(t)*(y(1,t) + y(3,t) - 1) <= done(t)}; end % Objective nocross = sum(done); cbndinit = {y(:,1) == 0}; con1 = {cbnd; eq1; eq2; eq3; eq4; eq5; cbndinit}; solution = ezsolve(-nocross,con1);

Problem type appears to be: mip ===== * * * =================================================================== * * * TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05 ===================================================================================== Problem: --- 1: f_k -3.000000000000000000 sum(|constr|) 0.000000000000003542 f(x_k) + sum(|constr|) -2.999999999999996400 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 55