2

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!

kirbo
  • 1,707
  • 5
  • 26
  • 32
  • Out of curiosity, why do you need solutions to be the same? – Patrick Trentin Aug 29 '17 at 08:14
  • Solutions is the form of coordination among distributed nodes. If global state is synchronized then all nodes will make identical decisions based on the deterministic model. – kirbo Aug 29 '17 at 09:11
  • 1
    Wouldn't it be more efficient to solve once and distribute the unique solution, instead of the all-sat approach you suggested? – Patrick Trentin Aug 29 '17 at 09:18
  • 1
    If you are solving `.fzn` files, perchance you might try using [OptiMathSAT](http://optimathsat.disi.unitn.it/pages/fznreference.html), it has experimental support for (a subset of) *FlatZinc*. It allows for *lexicographically optimising* multiple objectives in the same `.fzn` model. Take all variables of interest and optimise them lexicographically, that should reliably yield you a unique and identical solution on all machines. I am not sure how it compares performance-wise with an all-sat approach based on gecode, though. – Patrick Trentin Aug 29 '17 at 09:35
  • Thank you for the reference to the OptiMathSAT, I didn't know about it. I agree that solving model once and distributing solution among all nodes is a good approach. In my case the design choice was motivated by (1) simplified & failure robust design i.e., no need to elect a leader and (2) mostly uniform solution space where small deviations among solutions would not cause problems. However, recently I found that point (2) does not always hold and "identical" solutions in terms of optimization target might be quite different. – kirbo Aug 29 '17 at 12:47
  • actually, OptiMathSAT should always print the same solution across multiple computers even without using a lexicographic optimisation approach. That idea was only meant to ensure from a "theoretical point of view", and not only from an "implementation point of view", that it would. Having said this, I think that running gecode without multi-threading (which I believe is causing the issue you experience, as noted by Dekker) should be the simplest and fastest solution. – Patrick Trentin Sep 01 '17 at 07:50

1 Answers1

5

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.

Dekker1
  • 5,565
  • 25
  • 33