3

I have an optimization problem where I have a list of lists of "BoolVar" objects. So something like this:

[[BoolVar1,BoolVar2],[BoolVar3, BoolVar4],[BoolVar5,BoolVar6]]

I need to evaluate the following:

(BoolVar1 && BoolVar2) || (BoolVar3 && BoolVar4) || (BoolVar5 && BoolVar6)

Do I have to do this as follows:

and12 = model.NewBoolVar("and12")
model.Add(and12 == True).OnlyEnforceIf([BoolVar1,BoolVar2])
and34 = model.NewBoolVar("and34")
model.Add(and34 == True).OnlyEnforceIf([BoolVar3,BoolVar4])
and56 = model.NewBoolVar("and56")
model.Add(and56 == True).OnlyEnforceIf([BoolVar5,BoolVar6])
model.AddBoolOr([and12,and34,and56])

I've tried this code and it seems to be working but I'm doubtful because of the "OnlyEnforceIf" function. What happens if it's not enforced? Is and12 then set to False or can it be either False or True, since then this equation is not enforced? I came to this code based on this post.

ThaNoob
  • 520
  • 7
  • 23
  • I created a more general problem and solution for this kind of problem here: https://stackoverflow.com/questions/70571396/google-or-tools-how-to-evaluate-complex-or-multi-level-boolean-constraints/70571397#70571397 (Special thanks to @Laurent Perron) – ThaNoob Jan 03 '22 at 21:08

1 Answers1

6

  1. OnlyEnforceIf is just an implication. You need to add the reverse direction.

  2. You should stay in the Boolean world:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

and12 = model.NewBoolVar("and12")
BoolVar1 = model.NewBoolVar("b1")
BoolVar2 = model.NewBoolVar("b2")
model.AddBoolAnd([BoolVar1, BoolVar2]).OnlyEnforceIf(and12)
model.AddBoolOr([and12]).OnlyEnforceIf([BoolVar1, BoolVar2])

solver = cp_model.CpSolver()
solver.parameters.enumerate_all_solutions = True
solver.Solve(model, cp_model.VarArraySolutionPrinter([BoolVar1, BoolVar2, and12]))

outputs

Solution 0, time = 0.00 s
  b1 = 0   b2 = 0   and12 = 0 
Solution 1, time = 0.00 s
  b1 = 1   b2 = 0   and12 = 0 
Solution 2, time = 0.00 s
  b1 = 0   b2 = 1   and12 = 0 
Solution 3, time = 0.00 s
  b1 = 1   b2 = 1   and12 = 1
Laurent Perron
  • 8,594
  • 1
  • 8
  • 22
  • Thanks, I'll look at it in more detail tonight. I was wondering why does 'model.add(and12==all([BoolVar1,BoolVar2]))' not work? That would be more intuitive then the only enforce strategy. Because in the code you wrote above, can and12 still be True if BoolVar1&&BoolVar2 is false? – ThaNoob Jan 02 '22 at 08:39
  • And12 should always be true if BoolVar1 &&BoolVar2 is true and it should always be false if this is not the case. – ThaNoob Jan 02 '22 at 08:48
  • 1
    you cannot use python constructs. min, max, all, ... are all interpreted by python before passing to the modelling layer. – Laurent Perron Jan 02 '22 at 09:39
  • Are you sure this is not true ? Alternatively, you can add `model.AddBoolOr([Boolvar1.Not(), Boolvar2.Not(), and12])` – Laurent Perron Jan 02 '22 at 09:40
  • I'm not sure what you mean by "This" :) I think, i understand the code. It's not possible that and12 is true if BoolVar1&&BoolVar2 is false because of "model.AddBoolAnd([BoolVar1, BoolVar2]).OnlyEnforceIf(and12)". So I agree with your real Answer. Not sure about your comment though, imagine BoolVar1 is True and BoolVar2 is False, then and12 can be either true or false, while it should be false. – ThaNoob Jan 02 '22 at 20:54
  • I have asked the solver to enumerate all possible solutions. so this is false. The reason if that `and` requires all variables to be true if the enforcement literal is true. – Laurent Perron Jan 02 '22 at 21:01
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/240660/discussion-between-thanoob-and-laurent-perron). – ThaNoob Jan 02 '22 at 21:13
  • Why do you have AddBoolOr([and12]) when there is only one variable? Is this just so OnlyEnforceIf works? – Simd May 14 '22 at 11:12
  • It implements `boolvar1 && boolvar2 implies and12`. There is only one literal in the rhs. – Laurent Perron May 14 '22 at 13:08