MIP: Multiply two boolean variables

[Julian]

I would like to multiply two boolean variables given a MIP solver in Python to define a cost but somehow my program crashes with a TypeError. Below I add a minimum nonsensical example where the issue happens.

My question would be:

Why do I crash? I can multiply with other things (like scalars): is it not possible to use two variables for a solver.Sum?

Thank you very much for any help

from ortools.linear_solver import pywraplp as mip

# unaries

A1 = 0.9

A2 = 0.9

A3 = 0.9

B1 = 0.9

B2 = 0.9

B3 = 0.9

solver = mip.Solver('t', mip.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Sum = []

Rho = {}

V = [A1, A2, A3, B1, B2, B3]

n = len(V)

for idx in range(n):

    Rho[idx] = solver.BoolVar('rho[%i]' % idx)

    

s = solver.Sum(

    Rho[idx] * V[idx] for idx in range(n))

Sum.append(s)

E = [(0, 1, 2), (3, 4)]

for clique in E:

    #s = solver.Sum(Rho[a] for a in clique for b in clique if a != b)

    s = solver.Sum(Rho[a] * Rho[b] for a in clique for b in clique if a != b)

    

solver.Maximize(solver.Sum(Sum))

RESULT = solver.Solve()

print("Time = ", solver.WallTime(), " ms")

print("result:", RESULT)

print('\nTotal cost:', solver.Objective().Value())

for idx in range(n):

    print('node ' + str(idx) + ' -> ', Rho[idx].solution_value())

 

[Laurent Perron]

By definition, the product of two variables is not linear.

As these are booleans, it is easy to fit this into a linear solver.

See: 

  https://www.leandro-coelho.com/linearization-product-variables/

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

--
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.

[Paul Trow]

For Boolean variables x and y, 

   x * y = min(x, y)

The value of either side is 1 if both x and y are true, and 0 otherwise.

Perhaps solver.Sum(solver.Min(Rho[a], Rho[b]) ...  ?

[Julian]

Thanks for the idea! However, min should not be linear as well, should it? And if I try something like

s = solver.Sum(min(Rho[a], Rho[b]) for a in clique for b in clique if a < b)

I get 

ValueError: Operators "<" and ">" not supported with the linear solver

which I guess kind of makes sense..

My goal was to count the number of valid edges in a graph where Rho enables/disables a vertex so an edge needs two valid vertices to be counted as valid and my goal was to 'cheat' and use exclusively Rho to also check for valid edges. I solve it now the simply adding a second boolean variable for those edges which works well for me.

Thanks :)

[Laurent Perron]

That was for the CP or CP-SAT solver.

Min is not part of the linear solver.

Regarding < and >, as linear solver works on double, and have an inherent epsilon when doing computation, < and > are ill defined, thus we only support <= and >=.

--Laurent

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

--