Same solution returned multiple times

[Mark Gritter]

I encountered behavior in the constraint solver I don't understand.  I created a test case which I believed had only one solution, but I'm getting eight calls to OnSolutionCallback.  (I'm using the Python wrappers.)

The model dumped by ModelProto() is generated by code I wrote, but looks as I expect it to.  X1 through X4 represent selection of nodes from a graph.  The first set of contraints are tags on the nodes (all nodes have the same tag.)  The second set of constraints are edges, and I used unique tags to force a single working assignment.  All the constraints are created with AddAllowedAssignments, and I call SearchForAllSolutions to start the search.

variables {

  name: "X1"
  domain: 0
  domain: 4
}
variables {
  name: "X3"
  domain: 0
  domain: 4
}
variables {
  name: "X2"
  domain: 0
  domain: 4
}
variables {
  name: "X4"
  domain: 0
  domain: 4
}
constraints {
  table {
    vars: 0
    values: 0
    values: 1
    values: 2
    values: 3
    values: 4
  }
}
constraints {
  table {
    vars: 1
    values: 0
    values: 1
    values: 2
    values: 3
    values: 4
  }
constraints {
  table {
    vars: 2
    values: 0
    values: 1
    values: 2
    values: 3
    values: 4
  }
}
constraints {
  table {
    vars: 3
    values: 0
    values: 1
    values: 2
    values: 3
    values: 4
  }
}
constraints {
  table {
    vars: 0
    vars: 2
    values: 0
    values: 1
  }
}
constraints {
  table {
    vars: 1
    vars: 3
    values: 4
    values: 0
  }
}
constraints {
  table {
    vars: 2
    vars: 1
    values: 1
    values: 4
  }
}

The callback gets this same solution eight times:

X1 0
X2 1
X3 4
X4 0

CpSolverResponse:
status: FEASIBLE
objective: NA
best_bound: NA
booleans: 51
conflicts: 0
branches: 14
propagations: 58
integer_propagations: 6
walltime: 0.001184
usertime: 0.001147
deterministic_time: 0.000008

Is this expected behavior? What can I do to better understand the behavior of the CP SAT solver?

Other, simpler, examples I tried have produced only the expected number of results.  Removing the meaningless constraints from the model didn't change the behavior, nor did adding a second permissible edge.

[Laurent Perron]

I guess the table constraint creates additional Boolean variables, and these are switched in the different solutions. 

Thanks for the report, we will fix that.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Frederic Didier]

Yes the bug was identified and it will be fixed in the next release.

FYI, this was triggering only on table constraints with just one rows... so without such constraint (that can easily be replaced by fixing variables), the count should be correct.

[Laurent Perron]

This is fixed in the source.

It should be in v6.10, end of this week or next week.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00