How to change penalized cover constraint from excess only to target in OR Tools?

34 Views Asked by At

I'm working on a scheduler in CP-Sat on OR Tools (Python) and I'm trying to extend this constraint

// Cover constraints
    foreach (int s in Range(1, numShifts))
    {
        foreach (int w in Range(numWeeks))
        {
            foreach (int d in Range(7))
            {
                var works = new BoolVar[numEmployees];
                foreach (int e in Range(numEmployees))
                {
                    works[e] = work[e, s, w * 7 + d];
                }

                // Ignore off shift
                var minDemand = weeklyCoverDemands[d][s - 1];
                var worked = model.NewIntVar(minDemand, numEmployees, "");
                model.Add(LinearExpr.Sum(works) == worked);

                var overPenalty = excessCoverPenalties[s - 1];
                if (overPenalty > 0)
                {
                    var name = $"excess_demand(shift={s}, week={w}, day={d}";
                    var excess = model.NewIntVar(0, numEmployees - minDemand, name);
                    model.Add(excess == worked - minDemand);
                    obj.AddTerm(excess, overPenalty);
                }
            }
        }

As I understand, it penalize too many shifts per day.

How I can extend/edit it so it will try to reach the target (minDemand)? In other words: how I can penalize both excess and insufficiency? Ideally with some kind a multiplication on a cost, so the further from the target, the higher the cost. All my efforts ended on INFEASIBLE or UNKNOWN statuses.

1

There are 1 best solutions below

2
Laurent Perron On BEST ANSWER

It is implemented here: https://github.com/google/or-tools/blob/d37317b17ca16658451cafe05085fc22c39dd6c8/examples/python/shift_scheduling_sat.py#L131

    cost_variables = []
    cost_coefficients = []
    sum_var = model.NewIntVar(hard_min, hard_max, "")
    # This adds the hard constraints on the sum.
    model.Add(sum_var == sum(works))

    # Penalize sums below the soft_min target.
    if soft_min > hard_min and min_cost > 0:
        delta = model.NewIntVar(-len(works), len(works), "")
        model.Add(delta == soft_min - sum_var)
        # TODO(user): Compare efficiency with only excess >= soft_min - sum_var.
        excess = model.NewIntVar(0, 7, prefix + ": under_sum")
        model.AddMaxEquality(excess, [delta, 0])
        cost_variables.append(excess)
        cost_coefficients.append(min_cost)

    # Penalize sums above the soft_max target.
    if soft_max < hard_max and max_cost > 0:
        delta = model.NewIntVar(-7, 7, "")
        model.Add(delta == sum_var - soft_max)
        excess = model.NewIntVar(0, 7, prefix + ": over_sum")
        model.AddMaxEquality(excess, [delta, 0])
        cost_variables.append(excess)
        cost_coefficients.append(max_cost)