How to implement a circuit constraint ?

[Claudio Cesar de Sa]

Hi Everyone:

I am new here, as well as, I am learning Python using the OR-TOOLS as a nice motivation. I did some models
using the OR-TOOLS translating some models from Minizinc or Picat (languages that I am used to work).
Well, at moment I am stopped in constraint such the circuit for a vector. I am trying to write this constraint from scratch,
but without success.

The circuit constraint returns true for a sequence as :  [1, 3, 0, 2] from any index, I will be returning at the starting point
after n steps. This constraint is the kernel for my idea of TSP.

My codes are in: https://github.com/claudiosa/CCS/tree/master/python/or-tools

Another help:

To build another constraint such X <==> Y (Equivalent Relation) I tried something such:

def equivalence_constraint(model , x, y ):
    model.AddImplication(x,y)
    model.AddImplication(y,x)
It does not work ....

Can I use some user functions in models under of OR-TOOLS?

Thanks indeed

I am looking forward to hearing from you


Claudio

[Xiang Chen]

I didn't quite understand what you meant but there is already a circuit constraint:

https://google.github.io/or-tools/python/ortools/sat/python/cp_model.html#cp_model.CpModel.AddCircuit

Example: https://github.com/google/or-tools/blob/stable/examples/python/jobshop_ft06_distance_sat.py#L87

Your equivalence_constraint works but you could also just use model.Add(x == y) or remove one of the variables.

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2136629c-4bfc-474d-944e-fb82acd99e64%40googlegroups.com.

[Hakan Kjellerstrand]

Hi Claudio.

For inspiration you can also see my decomposition of circuit which I implemented long time ago: https://github.com/google/or-tools/blob/stable/examples/contrib/circuit.py

It's fairly easy to extend this to also show the path, i.e. not only the circuit.

/Hakan

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2136629c-4bfc-474d-944e-fb82acd99e64%40googlegroups.com.

--

Hakan Kjellerstrand
http://www.hakank.org/
http://www.hakank.org/webblogg/
http://www.hakank.org/constraint_programming_blog/
http://twitter.com/hakankj
https://www.facebook.com/hakankj

[Claudio Cesar de Sa]

Thanks Xiang for your ready answer

Really I would like learn to build these constraints such "circuit". Your indication was great, but the code presented
inside of AddCircuit is very incomprehensible (it is in a high-level for me at moment).
In addition this constraints does not work for my list numbers.

I was looking for a solution as presented by Hakan (see below... ), but also I did some customization for CP-SAT.
Anyway I will keep in my studies.

About the equivalence, a <=> b, works if one side is constant, but when the  both side are constraints variable, maybe I need some reyfing approach.
A case like this model.Add( (x[i][j] == 1) == (tour[i] == j)) does not work once, "x" and "tour" are variables ....
It means  (x[i][j] == 1) is true only if (tour[i] == j) is true ... both side are variable.

Well, Xiang, once indeed thanks for your help

Claudio

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Claudio Cesar de Sa]

Thanks Hakan

After some days trying, any imprecise progress. I did a circuit verifier/cheker in Python  and tried to convert it to CP-SAT. In this second part I lost again.

I got your code and did minors changes for CP-SAT syntax. It is a function inside of my tsp.py.
For instance:

            # solution: use Element instead
            # solver.Add(z[i] == solver.Element(x, z[i - 1])) 
            ## MODIFIED here by CCS
            solver.AddElement(z[i-1] , x, z[i])      ### NEW

just adapted for CP-SAT syntax.

Anyway, now I have an idea how to implement this constraint. I resume my approach considering yours ideas.

Thanks indeed again

Claudio

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2136629c-4bfc-474d-944e-fb82acd99e64%40googlegroups.com.

[Laurent Perron]

Note that it will be 100s of time slower that way.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/024bfb2d-9bae-4ca5-add3-16553f3915d2%40googlegroups.com.

[Claudio Cesar de Sa]

Laurent

I agree with your performance view ... but there are some points:

a) In another moment, other specific constraints should be built, and some I want to know, this "how to do it....."

b) In addition, it is frustrating for a beginner (like me) tries something such simple as:

....................................................

    n  = 7  #  number of nodes ( n x n matrix)

    the_model = cp_model.CpModel()

    tour = [ the_model.NewIntVar(0, (n-1), 'tour' ) 

             for i in range(n)

            ]

   the_model.AddCircuit( tour )

.................................................... 

runs it and an answer like:

.................................................... 

 File "study_circuit.py", line 28, in model_CIRCUIT

    the_model.AddCircuit( tour )

  File "/home/ccs/.local/lib/python3.8/site-packages/ortools/sat/python/cp_model.py", line 855, in AddCircuit

    cp_model_helper.AssertIsInt32(arc[0])

TypeError: 'IntVar' object is not subscriptable

.................................................... 

A bad feeling with this answer for a beginner ...

In another CP languages with this constraint is direct, for instance:
....................................

> L =[X1,X2], circuit(L). 
L = [2,1]
...................................

Really, maybe it is fault also ....  but the constraint done by-hand by Hakan works as expected.

Maybe in the manual of OR-TOOLS are missing some small examples to use these constraints.

Anyway, thanks very much

cc

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/Tv9TSXVSpLg/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeaEqFBOx4j33uvf-bfNXUTnCLZEBUR%3DJK2NO%3DqXCw_8Kw%40mail.gmail.com.

--

claudio

**********************************************************************

Whatsapp: +55 47 992451825
https://claudiocesar.wordpress.com/ (my links HERE)

https://github.com/claudiosa

https://www.udemy.com/picat-uma-linguagem-de-programacao-multiparadigma/

***********************************************************************

[Xiang Chen]

I might be wrong but your examples look more like an AddAllDiferent than a circuit.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAHQhj4rTnJShOMMeEPNkDYr4x9BjrS_3X%2BLaSb1si8245UcFig%40mail.gmail.com.

[Laurent Perron]

The circuit does not use integer variables, they are a non useful complication over Boolean variables.

There are plenty of examples using the circuit constraint. 

C++: https://github.com/google/or-tools/blob/858fa626959f7e386153af82756384b79f983b5a/examples/cpp/jobshop_sat.cc#L275

Python: https://github.com/google/or-tools/blob/858fa626959f7e386153af82756384b79f983b5a/examples/python/jobshop_ft06_distance_sat.py#L108

+ documentation:

C++: http://google.github.io/or-tools/cpp_sat/classoperations__research_1_1sat_1_1CircuitConstraint.html and http://google.github.io/or-tools/cpp_sat/classoperations__research_1_1sat_1_1CpModelBuilder.html#a75c76026eaca8ea83038fb6dfc9e734e

Python: http://google.github.io/or-tools/python/ortools/sat/python/cp_model.html#cp_model.CpModel.AddCircuit

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CANuGQjwsb-KeUVzAHm%2B-zbfSo_ui%2B8z%3DNa3EvYWkPrxxQiVo4A%40mail.gmail.com.

[Claudio Cesar de Sa]

Laurent

I will be checking these examples ...

Thank you

Claudio

Xiang:

Consider the index starts in 1 up to 5. See some examples:

.....

[2,5,4,1,3]

...............

[3,1,5,2,4]

.......

[5,4,2,1,3]

.............

In N steps you will back to the origin, seems the allDifferent ... it does a cycle....
In Picat it runs directly such: 

Picat> L =[X1,X2,X3,X4,X5], circuit(L), solve(L), writeln(L),  fail.

Claudio

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYe5%2Bfxdsk0YrHDPYb53O9aeO%2BqUDi4W8ow2TUYEH1anQ%40mail.gmail.com.

[alireza...@gmail.com]

Dear Laurent, 
Would it be possible to provide a super basic and easy to understand example of circuit constraint ? 
I have difficulty to understand the concept and application of circuit constraint ?

Thanks in advance 

Alireza

[Laurent Perron]

https://github.com/google/or-tools/blob/master/examples/python/tsp_sat.py

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c2950b12-65ec-45ca-9fdf-6601901b6871n%40googlegroups.com.