# Email: shipping puzzle - alternative model

← Back to Kevin's homepagePublished: 2018 December 31Magnus saw my MiniZinc shipping puzzle and got as absorbed in the problem as I did! He wrote in with a series of increasingly efficient solutions and has kindly agreed to share them.

Hi Kevin,

I saw your implementation of the shipping puzzle using MiniZinc, below is an alternative model of this vehicle routing problem. In this implementation each leg has a next leg, which has to be on the following day in the week, additionally start/end locations must match. In the case these constraints cannot be satisfied a special value of '0' is used. The objective is then to minimize the number of '0' in the next array. In the model below the routes have not been pretty-printed.

Best regards,

Magnus

`%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%`%

`% Data`

`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 ];`

`% Types`

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;

int: legs = card(leg_id);

`% next leg or 0 if new route`

array[leg_id] of var 0..legs: next;

`% either following day or new route`

`constraint`

(forall(l in 1..legs)

` (dow[next[l]] = dow[l] + 1 \/ next[l] = 0));`

` `

`% either matching start/end or new route`

`constraint`

(forall(l in 1..legs)

` (start[next[l]] = end[l] \/ next[l] = 0));`

var 1..legs: num_routes = sum(l in 1..legs)(next[l] = 0);

`% each leg is used exactly once`

include "alldifferent_except_0.mzn";

constraint alldifferent_except_0(next);

solve minimize num_routes;

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

Hi Magnus,

Thanks for writing!

I wouldn't have thought to model the problem this way, and it does turn out to be much faster --- I can solve routes with 100 legs in just a few seconds.

I'll explore this approach a bit more and see if I can scale it up to the 10,000 leg case.

Thanks,

Kevin

Hi Kevin,

I´m glad you found the model useful. Scaling it to cover the 10,000-leg case is not a trivial task.

Below my improved model. A few explanations:

- for each leg the set of possible next legs have been pre-calculated - this is the "next_candidate" parameter

- the parameters start, end and the enum CITY are not used anylonger (except in the pre-calculation step outside of MiniZinc)

- please find the 10,000 legs instance attached

`% 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" ];

This is still not performing well on the 10,000-leg instance. What you could do to improve further is to step into the world of search annotations. Replace the solve statement with the following:

annotation relax_and_reconstruct(array[int ] of var int,int);

solve :: seq_search([

int_search(next, dom_w_deg, indomain_random, complete),

` ])`

:: relax_and_reconstruct(next, 97)

:: restart_luby(100)

minimize num_routes;

- using restarts to avoid ending up in a bad part of the search space

- using LNS where 97% of the variables are fixed (this requires the Gecode back-end)

With this approach a minimal routes value of 2414 was achieved - what took ~30 min on my hardware.

Best regards

Magnus Ahlander

Hi Kevin,

Found a simpler search annotation that performs much better! 2414 routes on the 10,000-leg instance in less than four minutes. Here it is:

solve :: seq_search([

int_search(next, first_fail, indomain_max, complete),

` ])`

minimize num_routes;

`Cheers,`

`Magnus`

Hi Magnus,

Uh oh, looks like this puzzle is distracting you as much as it has distracted me =P

Thanks for sending this over --- would it be okay if I mentioned some of this code on my blog post about the problem?

Would also love to give you credit; is there a website or twitter handle you want me to link to with your name?

More broadly: I'm surprised that this puzzle seems so difficult for MiniZinc to handle --- you seem to be an expert and know much about implementation details like search strategy annotations, but even then we're a few orders of magnitude away from the Clojure and Rust solutions.

Do you think this problem is not something that MiniZinc is designed to handle?

Is there another optimization system you think might work better?

(Or a way to make this problem "harder" so that MiniZinc would be a more effective tool than a general purpose language?)

Best,

Kevin

Hi Kevin,

Yes, I think there is a better way to model this problem - if in the MiniZinc IDE you select the OSICBC solver, you will notice that it performs well and finds the optimum on smaller instances (~ 1000 routes) within a few seconds. Since OSICBC is a MIP-solver, this indicates that a linearisation could be effective (the best exact solutions on vehicle routing class of problem are often achieved using MIP solvers).

So let's try to express the constraints and the objective using linear equations. To understand the approach it is useful to illustrate the problem with a graph with the following characteristics:

- each leg forms a vertex in the graph

- between all compatible vertices edges with a flow capacity of 0 or 1 are added

- an extra vertex - the sink - is added to the graph

- between each vertex (apart from the sink itself) and the sink an edge with a flow capacity of 0 to 1 is added

the constraints will then be:

- the total outgoing flow from each vertex (apart from the sink) is 1

- the total incoming flow to each vertex (apart from the sink) is less than one (0 or 1)

the objective is:

- minimize the total incoming flow to the sink

Here the MiniZinc-model:

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

Hi Kevin,

Couldn't stay away from trying the symmetry breaking myself. The effect is stunning, the 10,000-leg instance is solved within 200 ms using OSICBC.

Here the updated model (instance generator and instances attached):

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

Hi Magnus,

This is super interesting, thanks for sending it over!

I don't know anything about MIP solvers, but I'll definitely take a look now.

Pretty busy at work the next few weeks, but I'll add these updates to my blog post --- if you don't have a website/twitter, is it okay if I just credit you as "Magnus Åhlander"? Or would you prefer just "Magnus" (or to remain entirely anonymous?)

Best,

Kevin

Hi Kevin,

I made some minor improvements to the models and cleaned up a bit - all is attached. Also included is a larger instance with 20,000 routes between 50 cities.

Here some results:

CP Gecode 1000 - 0,2s

CP OSICBC 1000 - 4s (proves optimality)

CP Gecode 10000 - 70s

MIP OSICBC 10000 - 45s (proves optimality)

MIP OSICBC 20000 - 90s (proves optimality)

MIP-merged OSICBC 10000 - 0,2s (proves optimality)

MIP-merged OSICBC 20000 - 20s (proves optimality)

On the non-merged models I tried some symmetry breaking between the legs, but unfortunately without success. A little bit frustrating - maybe there are efficient symmetry breakings which I fail to find?

One issue is that transforming data within a MiniZinc model is inherently painful, on the other hand when doing the data pre-processing outside of MiniZinc the MIP-model data files become very large, what could have a negative impact on the performance, using the OSICBC solver it is unclear what part of the run-time is spent parsing and compiling.

When comparing the different models one important question would be: how easy would it be to handle further constraints? Some ideas of further features:

- each leg has a duration

- a route can contain more legs on a single day

- each route (=plane) can travel max. e.g. 18 hours a day - between any two legs there must be a gap of >= 2 hours

- each route must end where it begins (or a penalty cost is applied)

- there are a maximum of N planes available

- each route has a value (=earning)

-...

How easy or difficult would it be to extend the various models with such constraints or others? How easy would it be to write up an algorithm in something like Clojure or Scala?

Feel free to use anything you find useful in your blog, you can refer to me by my full name.

Cheers,

Magnus

Hi Magnus,

Your email is one of several that I know people will find valuable, but that I can't dedicate the time to capturing in a full blog post.

Do you mind if I simply publish our email exchange directly to my website?

Hope you have a happy new year!

Best,

Kevin

Hi Kevin,

Yes, of course you can publish our exchange, please edit the contents as it suits you the best. Your blog is great, covering a very broad area of topics!

In reality, this shipping puzzle doesn´t really make MiniZinc shine. Using something like MiniZinc is probably over-kill when there are algorithms with polynomial run-time. However, playing with additional constraints may soon become painful with a dedicated algorithm, whereas it is doable with MiniZinc.

Comparing the three models I suggested - CP, MIP and MIP-merged, I believe that the MIP-merged model also would not scale above the simple shipping puzzle. Each of the CP- and MIP-models has different advantages. The MIP-model seems to be the most performant, but linearizing additional constraints may be cumbersome and time-consuming. The CP-model is probably the easiest to extend. Working with really large instances, often meta-heuristics would prove the most successful. Either within MiniZinc using LNS or by implementing your own local search algorithm in a standard programming language.

Happy New Year from Vienna, Austria!

Cheers,

Magnus