or-tools - Compute the stdev from a SumArray()

Question

I need to generate plannings for employees using Google's Optimization Tools. One of the constraints would be that every employee has approximately the same amount of working hours.

Thus, I want to aggregate in a list how many hours each employee is working, and then minimize the standard deviation of this list.

var workingTimes = new List<SumArray>();
foreach (var employee in employees) {
    // Gather the duration of each task the employee is
    // assigned to in a list
    // o.IsAssign is an IntVar and task.Duration is an int
    var allDurations = shifts.Where(o => o.Employee == employee.Name)
                .Select(o => o.IsAssigned * task[o.Task].Duration);

    // Total time the employee is working
    var workTime = new SumArray(allDurations);
    workingTimes.Add(workTime);
}

Now I want to minimize the stdev of workingTimes. I tried the following:

IntegerExpression workingTimesMean = new SumArray(workingTimes) * (1/workingTimes.Count);    
var gaps = workingTimes.Select(o => (o - workingTimesMean)*(o - workingTimesMean));
var stdev = new SumArray(gaps) * (1/gaps.Count());
model.Minimize(stdev);

But the LINQ query at the 2nd line of the last code snippet is throwing me an error:

Can't apply operator * to IntegerExpression and IntegerExpression

How can I compute the standard deviation of a Google.OrTools.Sat.SumArray?

Answer 1

The 'natural' API only supports linear expressions. You need to use the AddProductEquality() API.

Please note that 1 / Gaps.Count() will always return 0 (we are in integer arithmetic). So you need to scale everything up.

Personally, I would just minimize the unscaled sum of abs(val - average). No need to divide by the number of elements. Just check that the computation of the average has the right precision (once again, we are in integer arithmetic).

You could also consider just minimize the max(abs(val - average)). This is simpler and may be good enough.