Or-Tools (CP-SAT), Python-Implementierung schneller als C ++ ⇐ C++

[Anonymous]

Ich habe an der Lösung des Mindestproblems des dominierenden Sets mit CP_SAT gearbeitet und es zunächst in Python implementiert. Die Python -Version war sehr schnell, daher habe ich beschlossen, sie in mein Hauptprojekt C ++ einzubeziehen. Wenn ich es jedoch genauso in C ++ modelliert habe, stellte sich heraus, dass es 100 -mal langsamer war. Die tatsächliche Lösung ist langsam. Als C ++ - Version verzweigt sich aus irgendeinem Grund viel. < /P>
Python: < /p>

Code: Select all

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

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

model.minimize(sum(nodes))
< /code>
C ++: < /p>
int index = 0;
for (int i = 0; i < boost::num_vertices(graph); ++i)
{
if (mds_context.is_undetermined(newToOldIndex[i])){
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[i]) || mds_context.is_ignored(newToOldIndex[i])){
continue;
}
auto [neigh_itt, neigh_itt_end] = boost::adjacent_vertices(i, graph);
std::vector 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[i])){
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[i]];
cp_model.AddGreaterOrEqual(sum , 1);
}

}
LinearExpr sum;
for (auto decision_var : decision_vars) {
sum += decision_var;
}
cp_model.Minimize(sum);
< /code>
Wird dies durch bestimmte Parameter verursacht?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)