Email: shipping puzzle - alternative model

% Data

legs = 6;

dow = [M, T, T, W, R, F];

next_candidate = [{0,3},{0},{0,4},{0,5},{0,6},{0}];

% Types

enum DAY = {M, T, W, R, F};

int: legs;

set of int: LEG = 1..legs;

set of int: LEG0 = 0..legs;

array[LEG] of DAY: dow;

array[LEG] of set of int: next_candidate;

% next leg or 0 if end of route

array[LEG] of var LEG0: next;

constraint forall(l in LEG)

    (next[l] in next_candidate[l]);

% each leg is used at most once

include "alldifferent_except_0.mzn";

constraint alldifferent_except_0(next);

var LEG: num_routes = sum(l in LEG)(next[l] = 0);

solve

minimize num_routes;

output ["num_routes = ", show(num_routes), ";\n"];% ++ ["next = ", show(next), ";\n" ];

solve :: seq_search([

                int_search(next, first_fail, indomain_max, complete),

            ])

minimize num_routes;

Cheers,

Magnus

int: legs;

int: decisions;

set of int: DECISION = 1..decisions;

set of int: LEG = 1..legs;

array[LEG] of set of DECISION: outgoing;

array[LEG] of set of DECISION: incoming;

set of DECISION: to_sink;

array[DECISION] of var 0..1: flow;

% the outgoing flow of each vertex (leg) is exactly one (to another leg or to the sink)

constraint forall(l in LEG)

    (sum(e in outgoing[l])(flow[e]) = 1);

% the incoming flow of each normal vertex (leg) is 0 or 1

constraint forall(l in LEG)

    (sum(e in incoming[l])(flow[e]) <= 1);

% the objective is the incoming flow to the sink

var LEG: num_routes = sum(e in to_sink)(flow[e]); 

solve

minimize num_routes;

output ["num_routes = ", show(num_routes), ";\n"];

Attached are a couple of instances (as well as an instance generator). With the OSICBC solver the 1000-puzzle is solved within a second, the 10000-puzzle in ~100 seconds.

Can we do even better? Some things to investigate would be:

- symmetry breaking - some routes are equal - on option would be to merged them and adjust the flow capacity of the connecting edge.
- some edges can be removed, we know there must be a flow on them (e.g. those leading from Friday routes to the sink)

Further improvement could be to use a commercial back-end (like CPLEX).

Feel feel to use any material you find useful in your blog! (I don't have a blog or twitter account).

Hope you will enjoy playing with the MIP-model!

Cheers,
Magnus

int: vertices;

int: edges;

set of int: E = 1..edges;

set of int: V = 1..vertices;

array[V] of set of E: outgoing;

array[V] of set of E: incoming;

array[V] of int: capacity;

set of E: to_sink;

array[E] of var 0..max(capacity): flow;

% constraints on the outgoing flow from the vertices

constraint forall(v in V)

    (sum(e in outgoing[v])(flow[e]) = capacity[v]);

% constraints on the incoming flow to the vertices

constraint forall(v in V)

    (sum(e in incoming[v])(flow[e]) <= capacity[v]);

% the objective is the incoming flow to the sink

var int: num_routes = sum(e in to_sink)(flow[e]); 

solve

minimize num_routes;

output ["num_routes = ", show(num_routes), ";\n"];

Cheers,

Magnus