Counting whenever variable is less than n constant (CP-SAT)

[tomasz.ko...@gmail.com]

Hi Guys,

I am trying to count number of times when variable X (array) is less then 12 (using cp_model).

The count will be used as a part of goal minimization function (there will be penalty to the goal for above instances).

I can do it in a following way (using channeling), but I wonder if it is the most efficient way (in terms of optimization process time and memory efficiency).

x = [[model.NewIntVar(0, 100, "") for j in range(all_j)] for i in range(all_i)]
IsLessThan12 = [[model.NewBoolVar("") for j in range(all_j)] for i in range(all_i)]

for j in range all_i:
  for i in range all_j:
     model.Add(x[i][j] < 12).OnlyEnforceIf(IsLessThan12[i][j])
     model.Add(x[i][j] >= 12).OnlyEnforceIf(IsLessThan12[i][j].Not())

Penalty = sum( IsLessThan12[i][j] for j in range(all_j)] for i in range(all_i)) * 500

Could you please tell me if the solution is right or it could be improved?

Range of "i" dimension is around 300, range of "j" is around 30.

I have spotted also solver.Count and solver.Distribute methods, but it was't clear for me if they could and should be used in such a case.

What would be your approaches here?
Thank you!

[Laurent Perron]

This is the right method,

The solver.XXX methods are from a different solver, which is less efficient, and not recommended.

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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/6eaea813-0ae8-47d9-a3c9-80ab90d0f541n%40googlegroups.com.

[tomasz.ko...@gmail.com]

Thank you!

[tomasz.ko...@gmail.com]

Hi Guys,

I need to update the model sligtly - boolean ExIsBetween1and11 should be true when variable x is in range 0 < x < 12 (previously it was only single condition x < 12).

I have two questions:

1. I thought the easiest way would be by using XOR:

x = [[model.NewIntVar(0, 100, "") for j in all_j] for i in all_i]
ExIsBetween1and11 = [[model.NewBoolVar("") for j in all_j] for i in all_i]

for j in all_i:
  for i in all_j:
    model.AddBoolXOr([x[i][j] == 0, x[i][j] >= 12, ExIsBetween1and11[i][j]])

But I got TypeError: NotSupported: model.GetOrMakeBooleanIndex(unnamed_var_0 == 0).

How to do it in the right way?
I tried to make some literals, like below (probably incorrectly), but it did not work:
ExIsZero = x[i][j] == 0
ExIsAtLeast12 = x[i][j] >=12

Should I make more BoolVars, like:

ExIsZero = [[model.NewBoolVar("") for j in range(all_j)] for i in range(all_i)]
ExIsAtLeast12 = [[model.NewBoolVar("") for j in range(all_j)] for i in range(all_i)]
And then
for j in all_i:
  for i in all_j:
    model.Add(x[i][j] == 0).OnlyEnforceIf(ExIsZero[i][j])
    model.Add(x[i][j] != 0).OnlyEnforceIf(ExIsZero[i][j].Not())
    model.Add(x[i][j] >= 12).OnlyEnforceIf(ExIsAtLeast12[i][j])
    model.Add(x[i][j] < 12).OnlyEnforceIf(ExIsAtLeast12[i][j].Not())
    
    model.AddBoolXOr([ExIsZero[i][j], ExIsAtLeast12[i][j], ExIsBetween1and11[i][j]])

I thought it would be overkill, but maybe it cannot be done more easily?.

2. What would be the most efficient (in terms of optimization/processor efficiency) way of achievieng the mentioned condition (ExIsBetween1and11 == True when 0 < x < 12)?

a) A way descripted above (with XOR and maybe anyhow correct literals instead of all those BoolVars)?
b) Using OnlyEnforceIf, like a variant of:
model.Add(ExIsBetween1and11[i][j]).OnlyEnforceIf([x[i][j] != 0, x[i][j] >=12])
c) using implication, like a variant of:
model.AddImplication([x[i][j] != 0, x[i][j] >=12], ExIsBetween1and11[i][j])

Probably it could be done with some correct literals (instead of all those BoolVars), but in none of my trials I could make it work.

Could you tell me what is the right approach?

[Xiang Chen]

Probably something like:

    model.AddLinearExpressionInDomain(x[i][j], cp_model.Domain(1, 11)).OnlyEnforceIf(
        ExIsBetween1and11[i][j]
    )
    model.AddLinearExpressionInDomain(
        x[i][j], cp_model.Domain.FromValues([0, *range(12, 101)])
    ).OnlyEnforceIf(ExIsBetween1and11[i][j].Not())

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f06ab2ce-d9cb-475d-8aea-18c924280f9bn%40googlegroups.com.

[tomasz.ko...@gmail.com]

Thank you very much Xiang for a possible solution!

And for a depper understanding of potential alternatives:

If I wanted to use XOR, like a variant of following:

model.AddBoolXOr([x[i][j] == 0, x[i][j] >= 12, ExIsBetween1and11[i][j]])

or Implication, like a variant of following:
model.AddImplication(AddBoolAnd(x[i][j] != 0, x[i][j] >=12), ExIsBetween1and11[i][j])

Is any of the above possible to be done easily (e.g. with some kind of literals) or it would require declaring all the additional BoolVars, like:

ExIsZero = [[model.NewBoolVar("") for j in range(all_j)] for i in range(all_i)]

ExIsAtLeast12 = [[model.NewBoolVar("") for j in range(all_j)] for i in range(all_i)]?

[Laurent Perron]

xor takes an array of Boolean literals, and does not support enforcement literals.

and, or constraints take an array of Boolean literals

implications takes two literals, not a constraint and a literal.

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/eda705fe-e185-4492-b9d4-29efd3595b4en%40googlegroups.com.

[tomasz.ko...@gmail.com]

Sorry for dumb question about "literal" exact meaning, but to make sure:

So to have literals, for each of them I need to add model.NewBoolVar, is it right?

In this case:

ExIsZero = [[model.NewBoolVar("") for j in all_j] for i in all_i]

ExIsAtLeast12 =  [[model.NewBoolVar("") for j in all_j] for i in all_i]

And there is no way to add two "literals" (?) like x[i][j] > 0 and  x[i][j] < 12 and use them both in xor or implication without adding above additional  NewBoolVars?

Thank you in advance and please forgive dumb question. I hope that it will be educational for other beginners also.

[Laurent Perron]

a literal is a Boolean variable or its negation.

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/ddf42401-7b72-494a-a94b-4f10e47c5313n%40googlegroups.com.

[tomasz.ko...@gmail.com]

Ok, thank you.