or-tools handling nonlinear constraints

[Madalina Erascu]

Hello!

How could I encode the following 3 constraints into OR-Tools Python API? The variables are either integer or real numbers.

x11**2 > 0
x21**2 > 0
 x11*x21 == 0

From what I have read, it's not possible. Moreover, if I write a Minizinc model for the above and run OR-tools directly from the IDE (versions 12.2.1), I get an error which I suspect is because of non-linearity as Gecode does not give an error but Chuffed the same one.

Thanks for your input!

Madalina

[christoph...@gmail.com]

It's easy enough to encode these in the Sat solver, but what solution do you expect? The three constraints taken together are infeasible. By the last constraint, one of the numbers must be zero, but by the first two constraints, neither can be 0.

[Madalina Erascu]

Those constraints are generated by some n and m which generate the number of variables and I need to check how much the tool scales.

For the below none of the tools I used (Gecode, SMT solvers, computer algebra systems) was able to give me a solution.

So, how could I encode the initial problem and the one below for or-tools? I need it in my experiments. Thanks!

0 + x11**2 + x12**2 + x13**2 + x14**2 > 0
0 + x21**2 + x22**2 + x23**2 + x24**2 > 0
0 + x31**2 + x32**2 + x33**2 + x34**2 > 0
0 + x41**2 + x42**2 + x43**2 + x44**2 > 0
0 + x51**2 + x52**2 + x53**2 + x54**2 > 0
0 + x11*x21 + x12*x22 + x13*x23 + x14*x24 == 0
0 + x11*x31 + x12*x32 + x13*x33 + x14*x34 == 0
0 + x11*x41 + x12*x42 + x13*x43 + x14*x44 == 0
0 + x11*x51 + x12*x52 + x13*x53 + x14*x54 == 0
0 + x21*x31 + x22*x32 + x23*x33 + x24*x34 == 0
0 + x21*x41 + x22*x42 + x23*x43 + x24*x44 == 0
0 + x21*x51 + x22*x52 + x23*x53 + x24*x54 == 0
0 + x31*x41 + x32*x42 + x33*x43 + x34*x44 == 0
0 + x31*x51 + x32*x52 + x33*x53 + x34*x54 == 0
0 + x41*x51 + x42*x52 + x43*x53 + x44*x54 == 0

[christoph...@gmail.com]

You could do it exactly as written by introducing helping variables for the products and using AddMultiplicationEquality.  This is the c# code, I don't have a Python version handy, but Python will be similar, the + and comparison operators are also overloaded but the method is called AddMultiplicationEquality instead of AddProdEquality.

const long domain = 100;
IntVar x11 = model.NewIntVar(0, domain, "x11");
IntVar x12 = model.NewIntVar(0, domain, "x12");
IntVar x13 = model.NewIntVar(0, domain, "x13");
IntVar x14 = model.NewIntVar(0, domain, "x14");
IntVar x21 = model.NewIntVar(0, domain, "x21");
IntVar x22 = model.NewIntVar(0, domain, "x22");
IntVar x23 = model.NewIntVar(0, domain, "x23");
IntVar x24 = model.NewIntVar(0, domain, "x24");

IntVar x11Sqr = model.NewIntVar(0, domain * domain, "x11Sqr");
IntVar x12Sqr = model.NewIntVar(0, domain * domain, "x12Sqr");
IntVar x13Sqr = model.NewIntVar(0, domain * domain, "x13Sqr");
IntVar x14Sqr = model.NewIntVar(0, domain * domain, "x14Sqr");

IntVar x11x21 = model.NewIntVar(0, domain * domain, "x11x21");
IntVar x12x22 = model.NewIntVar(0, domain * domain, "x12x22");
IntVar x13x23 = model.NewIntVar(0, domain * domain, "x13x23");
IntVar x14x24 = model.NewIntVar(0, domain * domain, "x14x24");

model.AddProdEquality(x11Sqr, new IntVar[] { x11, x11 });
model.AddProdEquality(x12Sqr, new IntVar[] { x12, x12 });
model.AddProdEquality(x13Sqr, new IntVar[] { x13, x13 });
model.AddProdEquality(x14Sqr, new IntVar[] { x14, x14 });

model.AddProdEquality(x11x21, new IntVar[] { x11, x21 });
model.AddProdEquality(x12x22, new IntVar[] { x12, x22 });
model.AddProdEquality(x13x23, new IntVar[] { x13, x23 });
model.AddProdEquality(x14x24, new IntVar[] { x14, x24 });

model.Add((x11Sqr + x12Sqr + x13Sqr + x14Sqr) > 0);
model.Add((x11x21 + x12x22 + x13x23 + x14x24) == 0);

I recall having read that there are some issues when the multiplicands span 0, i.e. have both negative and positive values so avoid this if possible.

But really, the first constraints are basically saying that at least one of the values is not 0, and the last (if you're not spanning 0) that at least one of each pair is zero. The solver would more easily find solutions if you introduced Booleans for these conditions and constrained them directly.

[Madalina Erascu]

I don't want the variable to be from 0 to 100 but from -infinity to infinity. What if the solution does not lie in the interval [0,100]?

The features  from code which you just showed I knew. 

ME

[christoph...@gmail.com]

In the SAT solver you have to constraint the domain, it doesn't work with infinite domains. 

[Madalina Erascu]

I see. But then the method is not complete, in the sense that it assures that there is no solution in the given interval, right?

What about the case when the variables are real numbers? How can non-linearity can be encoded?

ME

[christoph...@gmail.com]

You have to scale real numbers to integers. The SAT solver only works with integers. If you use reals in Python it converts them integers, probably without informing.