CODEWITHSUNDEEP
pythonor-tools
Toby
Toby

Reputation: 2294

NoCycle constraint in OR-Tools and Python

I am implementing the Knight Tour Problem with OR-Tools in Python and I am struggling with the No-Cycle constraint. In C++, there is the MakeNoCycle global constraint, and I am assuming that in the Python wrapper, the equivalent to this is the TreeNoCycle constraint.

The simplified code I have so far (I copied the TreeNoCycle part from some broken example):

# side length of board
n = 5

# where the knight jumps to from field i, starting at 0, ending at n*n
jump_to = [solver.IntVar(1, n*n) for i in range(n*n)]

# snip other constraints

# the no cycle constraint
active = [solver.IntVar(1, 1) for i in range(dim * dim)]
for t in active:
    solver.Add(t == 1)
solver.Add(solver.TreeNoCycle(jump_to, active, lambda: None))

where when executed, the last part gets me the following error:

python3.6/site-packages/ortools/constraint_solver/pywrapcp.py", line 337, in NextSolution return _pywrapcp.Solver_NextSolution(self) SystemError: returned a result with an error set

The rest of my code works, i.e. when I omit the part with the TreeNoCycle constraint, I get many solutions, but some with disconnected graphs.

Is my assumption correct that TreeNoCycle is the Python method for MakeNoCycle? And if yes, how do I use TreeNoCycle correctly? If. If I cannot use TreeNoCycle, any ideas how to implement this differently?

Upvotes: 1

Views: 584

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11064

Please use the CP-SAT solver.

Please note that in that case, modeling should be a bit different, as the Circuit constraint takes a graph labeled by Boolean literals (a Boolean variable or its negation). You do not need the integer variables.

Some documentation:

https://github.com/google/or-tools/tree/stable/ortools/sat/doc

https://developers.google.com/optimization/cp/cp_solver#cp-sat_example

And python examples (look for the _sat.py suffix):

https://github.com/google/or-tools/tree/stable/examples/python

Upvotes: 1

Related Questions