[kiwijs] Constraint C Strength affects the priority at which constraint A beats constraint B

[cacaodev]

In this setup, there is initially one variable and two constraint. One Constraint (A) is an inequality, the other constraint (B) is an equality used to set a value on the variable. B can break A or not.

priority is a strength created like this : kiwi.Strength.create(0, 1, 0, priority).

A: variable >= 100 (priority 501)
B: variable = 90 (500)

After solving, the result is variable = 100 and is the expected result.

Now, if I add another equality constraint C with a very low priority variable = 50 (10) the variable value after solving is 90. It means that adding this constraint helps constraint B to break constraint A even if constraint B priority < A priority && C priority < A&B priority.

With the C constraint, the A priority needed to break constraint B is equal to (B + C).

A: variable >= 100 (501)
B: variable = 90 (500)
C: variable = 10 (10)

=> variable == 90 (Not expected)

A: variable >= 100 (511)
B: variable = 90 (500)
C: variable = 10 (10)

=> variable == 100 (Expected)

I also tried to suggestValue(variable, 90) instead of using constraint B and got the same results.

It seems that a third constraint affects the priority at which a constraint beats another , even if this third constraint priority is lower than the two other constraints fighting.

Is this a bug or the regular behavior ?

Test here: https://runkit.com/cacaodev/kiwi-bug (Hit the green button to run the test).

[sccolbert]

This is expected behavior, because there is not enough difference in the weights/strengths to express your intent. Instead of using hand-coded numerical strengths, try using the predefined strengths, which have sufficient delta that they wont trample each other: https://github.com/nucleic/kiwi/blob/master/kiwi/strength.h#L28-L34

For performance, stengths/weights are not treated with pure lexographic ordering. Instead they are converted to a sufficiently large number base so that strengths of a lower order will not effect strengths of a higher order.

In the end, a strength is just a multiplier on an error term, and the solver minimizes the error. The difference between 500 and 501 is not sufficient to make the error for the 100 solution be larger than the error for the 90 solution. However, the difference between 500 and 511 is (for this case).

Note that the difference between each of the three weak, medium, strong built in strengths is three orders of magnitude.

[cacaodev]

Thanks a lot, i have been able to get the correct result when using different strengths.

In case we need more than the 3 levels available (it is my case), I wonder is there is a way to calculate the minimum distance between levels to avoid that they clash each other.

[sccolbert]

There's not a really way to do that, since it depends on how large the error is for the associated terms, and that varies based on the system of constraints which is being solved. The right way to solve it, would be to fully lexographic order the strengths internally. But as I mentioned, that way would be much slower than what we currently do.

[sccolbert]

Your case may be fine by picking a 4 strength in the middle of the two you care about, or creating some other set of 4 (or more) strengths with sufficient distance between them.

[cacaodev]

I created sub-strengths but I was getting conflicts between them. The solution for me was to just generate numbers corresponding to new strengths higher than strong and with the same order of magnitude x1000 . Of course I had to redefine required higher.

[MatthieuDartiailh]

Closing as the primary issue is fixed.