Promoting solution diversity?

[braingineer]

Hello!

I am just wondering if there is a way to promote diversity among the bindings. For example, I have a CSP with a lot of binary variables. I would like to find solutions with minimal overlap. I imagine this could be done if one could set a depth threshold for the search so that when it backtracks to find a new solution, it can't choose a new branch that is further than this depth.

Thanks, Brian

[ehebrard]

I would recommend to post a constraint or an objective function when searching for the next solution, something like

model.add( Minimise( Sum([x == v for x,v in zip(variables,solution)]) ) )

(assuming that variables is an array of variables, and solution an array of integers)

You could even do:

model.add( Minimise( Sum([x == y for x,y in zip(vars1,vars2)]) ) )

and post your constraints both on vars1 and vars2 (and probably add the symmetry breaking constraint "vars1 <= vars2")

[braingineer]

Hello,

Thanks for the response.

Do you mean something along the lines of:

   while solver.getNextSolution() == Numberjack.SAT:

            syms = [sym for sym in sym_dict if sym.get_value()!=0]
            new_constraint = Numberjack.Sum([sym==1 for sym in syms])
            model.add(Numberjack.Minimise(new_constraint))

Where, symdict is holding all of the Numberjack variables as keys (and some meta information as the values)

I am uncertain about something you had specified. You said to use model.add, but does that update the solver? Don't I need to do solver.post?

However, I tried solver.post instead of model.add, but I was getting an error:

  File "/home/cogniton/anaconda/lib/python2.7/site-packages/Numberjack/__init__.py", line 3345, in post
    self.solver.post(exp.operator, exp.children[0].var_list[self.solver_id - 1], exp.children[1])
IndexError: list index out of range

Though, I do seem to be getting more diverse results faster with the formulation I pasted above. So, it's working, but I'm still a little confused about the different between solver.post and model.add and how they act during runtime.

[9thbit]

Hi Brian, I've added an example of finding diverse solutions to the examples folder which is using @ehebrard's approach: https://github.com/eomahony/Numberjack/blob/master/examples/DiverseSolutions.py

You'll need to reload and build a new model each iteration because of the objective changing. This approach has the added benefit that it will work with any solver, whereas post() only works for Mistral and MiniSat for now.

Regards, Barry

[braingineer]

Hi Barry,

Thank you for your answer and example! And thank you @ehebrard for the help as well.

Best, Brian