shipping puzzle in minizinc

1-readme.md

First pass at shipping puzzle in MiniZinc. See https://kevinlynagh.com/notes/shipping-puzzle/

Runs in 2.5 seconds on my 2013 macbook air. Anything more than 7 routes takes more than a few minutes (and I stopped waiting).

I tried to improve perf by breaking symmetry in the rows of routes by ordering the routes according to the first leg. (i.e., the first non-zero value in a row of routes should be less than the first non-zero value of the next row of routes) But I couldn't figure out how to do that neatly.

shipping.dzn

CITY = {FORT_WORTH,AUSTIN,COLUMBUS,EL_PASO,LOS_ANGELES,HOUSTON,SAN_DIEGO,INDIANAPOLIS};
leg_id = {1,2,3,4,5,6,7};
start = [FORT_WORTH,AUSTIN,COLUMBUS,EL_PASO,LOS_ANGELES,HOUSTON,SAN_DIEGO];
end = [COLUMBUS,EL_PASO,AUSTIN,HOUSTON,INDIANAPOLIS,SAN_DIEGO,LOS_ANGELES];
dow = [T,W,T,W,W,W,M];

shipping.mzn

include "globals.mzn";


enum DAY = {M, T, W, R, F};
enum CITY;
set of int: leg_id;
array[leg_id] of CITY: start;
array[leg_id] of CITY: end;
array[leg_id] of DAY: dow;

set of int: route_id;
array[route_id, DAY] of var 0..card(leg_id): routes;
% CITY = {PDX, SFO, SEA, DEN, JFK};
% leg_id = {1  , 2  , 3  , 4  , 5  , 6  };
% start  = [PDX, PDX, SEA, DEN, PDX, DEN];
% end    = [SEA, SFO, DEN, PDX, DEN, JFK];
% dow    = [M  , T  , T  , W  , R  , F  ];


route_id = 1..card(leg_id);

% Each leg is used exactly once
constraint forall(l in leg_id)
                 (1 = sum(rid in route_id, d in DAY)
                         (l = routes[rid, d]));

% Legs are assigned on the right day
constraint forall(rid in route_id, d in DAY where routes[rid, d] != 0)
                 (d = dow[routes[rid, d]]);

% Legs must be consecutive and match locations
constraint forall(rid in route_id, d in DAY diff {F})
                 (let { var int: l1 = routes[rid, d];
                        var int: l2 = routes[rid, enum_next(DAY, d)]}
                   in (l1 = 0 \/ l2 = 0 \/ end[l1] = start[l2])
                 );

% planes cannot stay idle (no empty legs within a route)
constraint forall(rid in route_id, d in DAY)
                 (routes[rid, d] = 0 -> (   forall(d2 in DAY where d2 > d)(routes[rid, d2] = 0)
                                         \/ forall(d2 in DAY where d2 < d)(routes[rid, d2] = 0)));

%%%%%%%%%%%%%%%%%%%%%
% objective
var int: num_routes;
constraint num_routes = sum(rid in route_id)
                           (0 != sum(d in DAY)(routes[rid, d]));

solve minimize num_routes;
output ["num_routes = \(num_routes)\n"];
output ["\(d) \(routes[rid, d])\n" | rid in route_id, d in DAY];