Search code examples
pythonconstraintsor-toolscp-satcover

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


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.


Solution

  • 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)