Efficiently count IntervalVars between given start/end times

Question

Is there an efficient way to count the number of IntervalVars between a given start and end time?

I'm trying to implement an employee rostering script. We have a demand that we have already generated that tells us how many employees should be working during a given interval.

What I would like to end up with is an IntVar for each i in the 24 (hour) intervals, givin the total employees with a starttime <= i <= endtime.

Below is a simple example.

from ortools.sat.python import cp_model

def main():

    # init model
    model = cp_model.CpModel()

    emps = range(0,3)

    emp_intervalvars = []
    for e in emps:
        start = model.NewIntVar(0,24,'st_e%i' % e)
        end = model.NewIntVar(0,24,'et_e%i' % e)
        dur = model.NewIntVar(0,24,'dur_e%i' % e)
        pres = model.NewBoolVar('pres_e%i' % e)
        interval = model.NewOptionalIntervalVar(start, dur, end, pres, 'interval_e%s' % e)

        # calc start
        model.Add(start == (end - dur)).OnlyEnforceIf(pres)

        # make sure to set start/end to 0 if not present
        model.Add(dur == 0).OnlyEnforceIf(pres.Not())
        model.Add(start == 0).OnlyEnforceIf(pres.Not())
        model.Add(end == 0).OnlyEnforceIf(pres.Not())

        # make sure to set start/duration to > 0 if present
        model.Add(dur > 0).OnlyEnforceIf(pres)
        model.Add(end > 0).OnlyEnforceIf(pres)

        # all emps between 8am and 6pm
        model.Add(start >= 8).OnlyEnforceIf(pres)
        model.Add(end <= 18).OnlyEnforceIf(pres)

        if e == 0:
            # lets say emp0 works mornings
            model.Add(end <= 14)
        elif e == 2:
            # and emp2 works evenings
            model.Add(start >= 11)

        emp_intervalvars.append({
            "present":pres,
            "start":start,
            "end":end,
            "duration":dur,
            "interval":interval
        })

    # simple objective
    durations = list(map(lambda v: v["duration"], emp_intervalvars))
    model.Maximize(sum(durations))

    solver = cp_model.CpSolver()
    solver.parameters.num_search_workers=8
    solver.parameters.max_time_in_seconds=30
    solver.parameters.log_search_progress=True
    status = solver.Solve(model)
    print(solver.StatusName(status))

    for i,field in enumerate(model._CpModel__model.variables):
        if field.name == '':
            continue
        print("{} : {}".format(field.name,solver._CpSolver__solution.solution[i]))

    return


if __name__ == '__main__':
    main()

Answer 1

a few comments:

    # calc start
    model.Add(start == (end - dur)).OnlyEnforceIf(pres)

This is already enforced by the interval var (which is actually exactly this constraint).

    model.Add(end > 0).OnlyEnforceIf(pres)

is most likely not useful. But you can keep it.

Now, to your question:

given start and end variables and a time i

overlap_i = model.NewBoolVar('overlap_%i' % i)
before_i = model.NewBoolVar('before_%i' % i)
after_i = model.NewBoolVar('after_%i' % i)

model.Add(start <= i).OnlyEnforceIf(overlap_i)
model.Add(end > i).OnlyEnforceIf(overlap_i)  # Intervals are open ended on the right

model.Add(end <= i).OnlyEnforceIf(before_i)
model.Add(start > i).OnlyEnforceIf(after_i)

model.Add(overlap_i + before_i + after_i == 1)

should do the trick