Counting how many decision variables are equal

Question

I'm a beginner user of Google OR-Tools, especially the CP-SAT. I'm using version 9.3, and I'm interested in the C++ version.

I'm modeling a problem where I need to count how many pairs of decision variables have the same (assigned) value. So, let's suppose I have a set of integer variables like this:

std::vector<IntVar> my_vars;

I also have a set of pairs like this:

std::vector<std::pair<size_t, size_t>> my_pairs;

Assume that all bounds are valid, size, etc, are valid. Now, I want to compute how many of these pairs have the same value. Using IBM Ilog Concert, I can do it very straightforward using:

// Using Ilog Concert technology.
IloIntVar count(env, 0, MY_UPPER_BOUND);

IloIntExpr expr_count(env);
for(const auto& [u, v] : my_pairs) {
    expr_count += (my_vars[u] == my_vars[v]);
}
        
model.add(count == expr_count);

Here, count is a decision variable that holds how many pairs have the same value in a given solution. The expression is a sum of boolean values comparing the actual decision variable's values, not the variable objects themselves (i.e., is the object representing variable u is the same object representing variable v).

Using OR-Tools, the equality operator ==, compares whether the variable objects (or representation of them) are equal, not the decision variable values. So, the following fails by generating an empty expression:

// Using Google Or-Tools CP-SAT.
IntVar count = cp_model
    .NewIntVar(Domain(0, my_pairs.size()))
    .WithName("count");

LinearExpr expr_count;
for(const auto& [u, v] : my_pairs) {
    expr_count += (my_vars[u] == my_vars[v]);
}

cp_model.AddEquality(count, expr_count);

Note that, according to Google OR-Tools code (here), we have that:

class IntVar {
  //...
  bool operator==(const IntVar& other) const {
    return other.builder_ == builder_ && other.index_ == index_;
  }
  //...
};

i.e., comparing if the variables are the same, but not the value assigned to them. Therefore, we cannot compare decision variables directly using CP-SAT, and we need to recur to another method.

Obviously, I can change the model using some big-M notation and linearize such expressions. However, can I do count without to recur to "remodeling"? I.e., is there a construct I can use "more or less" easily so that I address such cases?

I must mention while I only depict one case here, I have quite a few counting variables of several sets like that. So, remodeling using big-M will be a big headache. I would prefer a simpler and straightforward approach like Ilog Concert.

(Update) Little extension

Now, I want do the same but comparing decision variables with scalars. For example:

std::vector<int> my_scalars;

for(size_t i = 0; i < my_scalars.size(); ++i) {
    expr_count += (my_vars[i] == my_scalars[i]);
}

While this can be done using Ilog, it even did not compile on OR-Tools.

THanks,

Carlos

Answer 1

here is a tentative code:

IntVar count = model.NewIntVar(0, MY_UPPER_BOUND);

LinearExpr expr_count;
for(const auto& [u, v] : my_pairs) {
    BoolVar is_equal = model.NewBoolVar();
    model.AddEquality(my_vars[u], my_vars[v]).OnlyEnforceIf(is_equal);
    model.AddNotEqual(my_vars[u], my_vars[v]).OnlyEnforceIf(is_equal.Not());
    expr_count += is_equal;
}

model.AddEquality(expr_count, count);

Answer 2

With help of @sascha and @Laurent, my solution is this one:

vector<BoolVar> is_equal;
is_equal.reserve(my_pairs.size());

for(const auto& [u, v] : my_pairs) {
    is_remainder_equal.push_back(cp_model.NewBoolVar());
    cp_model
        .AddEquality(my_vars[u], my_vars[v])
        .OnlyEnforceIf(is_equal.back());
    cp_model
        .AddNotEqual(my_vars[u], my_vars[v])
        .OnlyEnforceIf(Not(is_equal.back()));
}

cp_model.AddEquality(LinearExpr::Sum(is_equal), count);

It is the same as @Laurent in the very end, but I save the boolean vars for late use.

For scalars, it looks like I don't need to make a constant, just compare directly with the expression.

Thanks, @Laurent and @sascha. You guys were very helpful.