Multiplying boolean variables together in a constraint (CP-SAT)

[Louie Hext]

Hi,

I have a grid of cells and im trying to assign them to a list of rooms based on a set of constraint and get a large list of feasible solutions.

I'm using the CP-SAT solver from OR-TOOLS v9.3 to solve a positional  matrix  P_i,j which is 1 if cell j is in room i and 0 otherwise.

An important constraint is that all cells in a room are simply connected.

One of the sufficient checks for this involves the expression detailed below. But it involves calculating.

P_ij * P_ik  (both of which will be boolean vars) inside a summation.

When I try and evaluate this it throws a "is not a number" error. Is there an issue multiplying constraints together? im believe that this makes it non-linear but I thought the CP-Sat solver could handle that?

I've tried implementing it another way to avoid the explicit multiplication as its just a Boolean check , but this throws a "NotImplementedError: Evaluating a LinearExpr instance as a Boolean is not implemented" error.

Im not sure if im approaching this wrong but it seems like it should be a simple thing to do, is the CP-Sat solver not the best thing to use?

Or is there a function im missing which will allow me to implement this constraint?

       

Context

======

Code

======

#first method with explicit sum

     

self.model.Add(sum(

                                     sum(       self.adjacency_matrix[j,k]*self.position_matrix[n,j]*self.position_matrix[n,k]

                                    for j in range(k,self.num_cells)

                                    )

                                    for k in range(self.num_cells)  

                                )  

                                    >=

                                    sum(

                                        self.position_matrix[n,jj] for jj in self.num_cells

                                        ) -1

                           )

#second method with internal boolean check,

self.model.Add(sum(

                               sum(

                                    self.adjacency_matrix[j,k]

                                    for j in range(k,self.num_cells)

                                    if self.position_matrix[n,j] and self.position_matrix[n,k]

                                   )

                                    for k in range(self.num_cells)

                                )

                                    >=

                                    sum(

                                        self.position_matrix[n,jj] for jj in self.num_cells

                                        ) -1

                            )

             

[blind.lin...@gmail.com]

Hi,

I think perhaps you cannot multiply two IntVars directly.

First, looking at the python API, I see

    def __mul__(self, arg):
        arg = cmh.assert_is_a_number(arg)
        if cmh.is_one(arg):
            return self
        elif cmh.is_zero(arg):
            return 0
        return _ProductCst(self, arg)

which maybe is the assert you are hitting?

Second, reading the docs on CPSAT here: https://github.com/google/or-tools/blob/stable/ortools/sat/docs/boolean_logic.md#product-of-two-boolean-variables

There is a long section on a trick for multiplying two boolean variables.

So probably you cannot just multiply the variables, but instead need to create new booleans for each multiplication and set it up properly using the channeling constraints.

In your case this is a bit of a pain, but sometimes programming is all about tedium to avoid more tedium.

Maybe this will work:

for n in range(roomsorcells_idunno):
    for k in range(self.num_cells):
        pnk = self.position_matrix[n, k]

        for j in range(k, self.num_cells):
            pnj = self.position_matrix[n, j]
            ajk = self.adjacency_matrix[j, k]

            # copy paste coding
            ppjk = model.NewBoolVar(f"j={j} and k={k} in same room")
            # x and y implies p, rewrite as not(x and y) or p
            model.AddBoolOr(pnk.Not(), pnj.Not(), ppjk)

            # p implies x and y, expanded into two implication
            model.AddImplication(ppjk, pnk)
            model.AddImplication(ppjk, pnj)

            # then do it all again?  Is there an easier way with AddBoolOr?  Probably should create the full truth table and use that
            # copy paste again
            appjk = model.NewBoolVar(f"j={j} and k={k} in same room and adjacent")
            # x and y implies p, rewrite as not(x and y) or p
            model.AddBoolOr(ajk.Not(), ppjk.Not(), appjk)

            # p implies x and y, expanded into two implication
            model.AddImplication(appjk, ajk)
            model.AddImplication(appjk, ppjk)

Probably a smarter idea is to write out the full truth table for the triple multiplication (similar to what is done in the docs page linked above) and then be more clever about the implications, rather than doing the cargo cult double multiply I do above.

Hope that helps,

James

[Eyal Gruss]

You can add a new variable and use AddMultiplicationEquality(new_var, list_of_vars_to_multiply)

Then you new_var in the constraints.

Eyal.

[blind.lin...@gmail.com]

Ah much cleaner. I'm still climbing the API learning curve on the CP-SAT side of the solver. I was hoping if I piped up something dumb someone else would improve it.

James

[Laurent Perron]

Not dumb, the multiplication of Booleans will be presolved into a set of clauses

https://github.com/google/or-tools/blob/49b6301e1e1e231d654d79b6032e79809868a70e/ortools/sat/cp_model_presolve.cc#L1199

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

Le mer. 11 mai 2022 à 16:55, blind.lin...@gmail.com <blind.lin...@gmail.com> a écrit :

Ah much cleaner. I'm still climbing the API learning curve on the CP-SAT side of the solver. I was hoping if I piped up something dumb someone else would improve it.

James

--
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/YnvObGN9pf65VbWn%40b3493d06ae14.

[Louie Hext]

Thanks for all the information,

I think i'll be able to get this working now. 

Louie

[Louie Hext]

Thought i'd post how I got it working in the end,

This is how I set up the product matrix variables.

essentially a large matrix which holds all the products, following the set up from -https://github.com/google/or-tools/blob/stable/ortools/sat/docs/boolean_logic.md#product-of-two-boolean-variables

from here I could use these values when forming constraints in the model.

[Louie Hext]

Hi Laurent,

is it better to set up the boolean multiplication in this explicit way than using the addMultiplicationEquality() method?

On Wednesday, May 11, 2022 at 4:09:10 PM UTC+1 Laurent Perron wrote:

[Laurent Perron]

I believe the end result will be the same. But it would be more efficient just creating the clauses.

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/991dcf81-b562-41b6-90a9-42c7311c8d81n%40googlegroups.com.