Wrong constraints evaluation and error propagation

[riccardozucchetto]

Hi Iain,

First of all, I would like to thank you for your Decider, it’s very powerful and useful!

During the development of our program, we have found some cases in which the propagation of the error and the evaluation of the constraints was not correct, eventually ending into wrong results being returned. We have managed to extract a code fragment that reproduces this issue. Before pasting the code, I would like to give you a little bit of context: what we are trying to calculate is the number of breaks (and shifts) an employee can get according to the number of hours he works (i.e.: if someone works 6 hours he is entitled of a break of 30 minutes, so work from 8:00-12:00, break 12:00-12:30, work 12:30-14:30). The values you will see later are expressed in quarter of hours, meaning that you need to multiply by 15 to get the value in minutes (1 = 15 minutes, 2 = 30 minutes, 4 = 1 hour, 8 = 2 hours, etc).

Code:

VariableInteger netDuration = new VariableInteger("netDuration", 24, 36); //This is the duration of the shift, between 6 and 9 hours
VariableInteger breakDuration = new VariableInteger("breakDuration", 0, 4); //This is the duration of the break, between 0 and 1 hour
VariableInteger numActivities = new VariableInteger("numActivities", 1, 3); //This is the number of shifts, between 1 (no breaks) and 3 (2 breaks)

ConstrainedArray minActivities = new ConstrainedArray(Enumerable.Repeat(0, 25).Concat(Enumerable.Repeat(1, 16)));
ConstrainedArray maxActivities = new ConstrainedArray(Enumerable.Repeat(0, 25).Concat(Enumerable.Repeat(1, 16)));

ConstrainedArray minBreakTime = new ConstrainedArray(Enumerable.Repeat(0, 25).Concat(Enumerable.Repeat(2, 16)));
ConstrainedArray maxBreakTime = new ConstrainedArray(Enumerable.Repeat(0, 25).Concat(Enumerable.Repeat(2, 16)));

var variables = new List<IVariable<int>> { netDuration, breakDuration, numActivities };
var constraints = new List<IConstraint>
{
  new ConstraintInteger(numActivities >= minActivities[netDuration] + 1),
  new ConstraintInteger(numActivities <= maxActivities[netDuration] + 1),
  new ConstraintInteger(breakDuration >= minBreakTime[netDuration]),
  new ConstraintInteger(breakDuration <= maxBreakTime[netDuration]),
  new ConstraintInteger((numActivities == 1 & breakDuration == 0) | (breakDuration >= numActivities - 1 & numActivities > 1)),
  new ConstraintInteger((numActivities == 1 & netDuration >= 24 & netDuration <= 24) | (numActivities > 1 & netDuration >= 12 * numActivities & netDuration <= 18 * numActivities))
};

var state = new StateInteger(variables, constraints);
var searchResult = state.SearchAllSolutions();

foreach (var sol in state.Solutions)
    Debug.WriteLine($"{sol["netDuration"].InstantiatedValue}\t{sol["breakDuration"].InstantiatedValue}\t{sol["numActivities"].InstantiatedValue}");
// Solution netDuration = 36, breakDuration = 2, numActivities = 3 is not valid

As you can see in the comment in the last row, we get that situation that is actually not valid, because for a shift of 9 hours only one break should be given, not two.

To fix this, we have changed the following lines in your code:

• file ConstraintInteger.cs, line 101: we have changed the “&=” to “&”
• file ExpressionInteger.cs, line 504: we have changed “<” to “<=”
• file ExpressionInteger.cs, line 574: we have changed “>” to “>=”

As a side note: if you change the value 24 to 35 in the first line of the code, then it would give the right result without changing your code.

In our case, those 3 changes were enough to get the right results, but we didn’t want to open a pull request because we don’t know if it is the right approach or if it breaks anything else.

Another smaller (possible) issue: we ended up having a few cases where we got an exception in the EvaluateBounds method in ConstrainedArray.cs because the “elements” variable was empty. We changed line 72 of that file as follows, by adding a DefaultIfEmpty():

return new Bounds<int>(elements.DefaultIfEmpty().Min(), elements.DefaultIfEmpty().Max());

We aren’t able to reproduce this case in a snippet, but we would like to let you know this possible issue as well.

Thank you, Riccardo

[lifebeyondfife]

Thanks @riccardozucchetto. This got missed in a sea of notifications, so apologies for the long delay in responding. I really appreciate the detailed write-up, and also solution.

If you would like to send a PR, I'll happily accepting after testing, so you can be a contributor. Otherwise, I'll examine your suggestions and implement when I get a chance.

Cheers!

[riccardozucchetto]

Hi Iain, Thank you, I sent the PR: it looks like that the tests are succesfully passed, but please double check it, also if you have more tests to run.

Thank you, Riccardo

[lifebeyondfife]

Thanks again, Riccardo. Your fixes are published in v1.0.5.