Minizinc, Gecode, how to get an identical solutions across distributed servers, with multi-solution model?

218 views Asked by At

I am using minizinc and gecode to solve a minimization problem in a distributed fashion. I have multiple distributed servers that solve the same model with identical input and I want all the servers to get the same solution.

The problem is that model has multiple solutions, which periodically causes servers to come up with different solutions independently. It is not significant which solution will be chosen, as long as it is identical among all servers. I am also using "-p" arguments with gecode to use multiple threads (if it is relevant).

Is there a way that I could address this issue?

For example, I was thinking about outputting all the solutions and then sort them alphanumerically on each server.

Thanks!

1

There are 1 answers

2
Dekker1 On BEST ANSWER

If the search strategy in the model does not contain randomisation, then, assuming all versioning is the same, a single thread executing of Gecode should always return the same answer for the same model and instance data. It does not matter if it's on a different node. Using single threaded execution is the easiest way of ensuring that the same solution is found on all nodes.

If you are however want to use multiple threads, no such guarantee can be made. Due to the concurrency of the program, the execution path can be different every run and a different solution might be found each time.

Your suggestion of sorting the solution is possible, but will come at a price. There are two ways of doing this. You can either find all solutions, using the -a flag, and sort them afterwards or you can change your model to force the solution to be the first solution if you would sort them. This second option can be achieved by changing the search strategy. Both these solutions can be very costly and might (more than) exponentially increase the runtime.

If you are concerned about runtime at all, then I suggest you take Patrick Trentin's advice and run the model on a master node and distribute the solution. This will be the most efficient in computational time and most likely as efficient in runtime.