Constant Cost of the Computation-Unit in Efficiency Graphs for DCOP Solvers

We show how to ensure a constant cost for the computation-unit in graphs depicting the number of (sequential) computation-units at different (distributed) problem sizes. We report empirical evaluation with ADOPT revealing that the computation cost associated with constraint check (commonly used - and assumed constant - in ENCCCs evaluations) actually varies with the problem size, by orders of magnitude. We therefore propose better computation-units based on a basket of weighted constraint-checks and contexts processing operations.