[Python] OR-tools (CP-SAT), Python implementation way faster than c++

I was working on solving the Minimum Dominating Set problem using CP_SAT, and I initially implemented it in Python. The Python version was very fast, so I decided to incorporate it into my main C++ project. However, when I modeled it exactly the same way in C++, it turned out to be 100 times slower.

IMPORTANT: setting up the rules is fast. The actual solving is slow. As the c++ version branches a lot for some reason.

Python:

# create decision variables.
nodes = [model.new_int_var(0, 1, f"node_{i + 1}") for i in range(num_vertices) if (included == 0 and excluded == 0 and removed == 0)]

# create constraints.
for i in range(num_vertices):
if included == 1 or dominated == 1 or ignored == 1:
continue
neighbors = adjacencyList
undetermined_neighbors = [j for j in neighbors if (included[j] == 0 and excluded[j] == 0 and removed[j] == 0)]
if excluded == 0 and removed == 0:
model.Add(sum(nodes[translation_pace_to_ilp[j]] for j in undetermined_neighbors) + nodes[translation_pace_to_ilp] >= 1)
else:
model.Add(sum(nodes[translation_pace_to_ilp[j]] for j in undetermined_neighbors) >= 1)

model.minimize(sum(nodes))


c++:

int index = 0;
for (int i = 0; i < boost::num_vertices(graph); ++i)
{
if (mds_context.is_undetermined(newToOldIndex)){
decision_vars.push_back(cp_model.NewIntVar(domain).WithName(std::to_string(i)));
}
//Create constraint.
for (int i = 0; i < boost::num_vertices(graph); i++) {
if (mds_context.is_dominated(newToOldIndex) || mds_context.is_ignored(newToOldIndex)){
continue;
}
auto [neigh_itt, neigh_itt_end] = boost::adjacent_vertices(i, graph);
std::vector<int> undetermined_neighbours;
undetermined_neighbours.reserve(std::distance(neigh_itt, neigh_itt_end));
for (auto vertex = neigh_itt ; vertex != neigh_itt_end; ++vertex) {
if (mds_context.is_undetermined(newToOldIndex[*vertex])){
undetermined_neighbours.push_back(*vertex);
}
}
LinearExpr sum;
if (mds_context.is_excluded(newToOldIndex)){
for (int j : undetermined_neighbours) {
sum += decision_vars[translation_pace_to_ilp[j]];
}
cp_model.AddGreaterOrEqual(sum, 1);
} else {
for (int j : undetermined_neighbours) {
sum += decision_vars[translation_pace_to_ilp[j]];
}
sum += decision_vars[translation_pace_to_ilp];
cp_model.AddGreaterOrEqual(sum , 1);
}

}
LinearExpr sum;
for (auto decision_var : decision_vars) {
sum += decision_var;
}
cp_model.Minimize(sum);


Is this caused by certain parameters?

I looked at the forum, I tried different ways to model the variables etc.

I did some logging and I found this:

CpSolverResponse summary: (Python)
status: OPTIMAL
objective: 351
best_bound: 351
integers: 1260
booleans: 1224
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 1
restarts: 0
lp_iterations: 0
walltime: 3.23695
usertime: 3.23695
deterministic_time: 45.6058
gap_integral: 83.2848
solution_fingerprint: 0x515d9087463252ea

c++:
status: OPTIMAL objective: 351
best_bound: 351
integers: 1265
booleans: 1229
conflicts: 0
branches: 2458
propagations: 118
integer_propagations: 2577
restarts: 2458
lp_iterations: 0
walltime: 159.73
usertime: 159.73
deterministic_time: 63.0662
gap_integral: 77.2995
solution_fingerprint: 0xa9edfc94d7cbe493

c++ Initial optimization model '': (model_fingerprint: 0x7190c09ab1ffe3f2)
#Variables: 1'229 (#bools: 1'229 in objective)
(1'229 primary variables) - 1'229 Booleans in [0,1]
#kLinear2: 59 #kLinear3: 220
#kLinearN: 929 (#terms: 3'872)

python: Initial optimization model '': (model_fingerprint: 0x8456b0693417e1f1)
#Variables: 1'229 (#bools: 1'229 in objective) - 1'229 Booleans in [0,1]
#kLinear2: 59
#kLinear3: 220 #kLinearN: 929 (#terms: 3'872)

Continue reading...