3
$\begingroup$

I am trying to solve a scheduling problem in OR-Tools. There are lots of "events" that need to be scheduled to "blocks" (essentially half-days). I am naturally using optional intervals for the events. One of the requirements is that the "run" of events scheduled to a particular block needs to be consecutive, i.e. there must be no gap between the end of one interval and the start of the next. I tried defining it with a new IntervalVar for each block, representing the start, duration and end of the "run" of events and an additional constraint that the duration is equal to the sum of lengths of the events which are active for the given block. Also a NoOverlap constraint is needed to prevent collisions between the events in the run.

Pseudo-C# code:

foreach (var group in events.GroupBy(e => e.Block))
{
    var anyActive = _cpModel.NewBoolVar($"any_active_in_block_{group.Key.Block}");

    _cpModel.Add(LinearExpr.Sum(group.Select(i => i.IsActive)) > 0).OnlyEnforceIf(anyActive);
    _cpModel.Add(LinearExpr.Sum(group.Select(i => i.IsActive)) == 0).OnlyEnforceIf(anyActive.Not());

    var runLength = _cpModel.NewIntVar(0, BLOCK_END - BLOCK_START, $"run_length_in_block_{group.Key.Block}");
	var minEventStart = _cpModel.NewIntVar(BLOCK_START, BLOCK_END, $"minimum_event_start_in_block_{group.Key.Block}");
    var maxEventEnd = _cpModel.NewIntVar(BLOCK_START, BLOCK_END, $"maximum_event_end_in_block_{group.Key.Block}");

    _cpModel.NewIntervalVar(minEventStart, runLength, maxEventEnd, $"block_{group.Key.Block}_interval");

    _cpModel.AddMinEquality(minEventStart, group.Select(e => e.Start));
    _cpModel.AddMaxEquality(maxEventEnd, group.Select(e => e.End));
    _cpModel.Add(runLength == LinearExpr.ScalProd(group.Select(e => e.IsActive), group.Select(e => e.Length))).OnlyEnforceIf(anyActive);

    _cpModel.AddNoOverlap(group.Select(o => o.Interval));
}

While that seems to work, it causes the complexity to explode, with over 10x the number of branches in a solution when I use this code. Is this just the consequence of the size of the search space? Or is there a better way to achieve the goal? There are obviously more constraints in the problem but this one seems to have the biggest impact on performance.

$\endgroup$
5
  • 1
    $\begingroup$ Look at the github.com/google/or-tools/blob/…, to force contiguity, replace the >= by ==. Please note that this makes the problem much harder, and most likely infeasible if intervals have different durations. $\endgroup$ – Laurent Perron Mar 6 '20 at 23:00
  • $\begingroup$ OK, I now understand that using the circuit constraint I can control the order of the events. But what happens with events which are not selected for the given block, i.e. the control variable of their optional interval is false? How can I "exclude" them from the circuit? $\endgroup$ – crypto_rsa Mar 7 '20 at 22:08
  • 1
    $\begingroup$ You have to create a (i, i) loop. $\endgroup$ – Stradivari Mar 7 '20 at 23:49
  • $\begingroup$ with the negations of the task being active as literal. $\endgroup$ – Laurent Perron Mar 9 '20 at 6:33
  • $\begingroup$ Thanks for your comments. I'll summarize it in an answer below. $\endgroup$ – crypto_rsa Mar 10 '20 at 9:26
1
$\begingroup$

As suggested in the comments above, I went with the circuit constraint. While I am not yet sure whether it helps with the performance, it certainly offers a lot more control over the relations between pairs of variables - here specifically it allows forcing a constraint that an event starts at the end of the previous event.

foreach (var group in events.GroupBy(e => e.Block))
{
    var eventsInBlock = group.ToList();
    var anyActive = _cpModel.NewBoolVar($"any_active_in_block_{group.Key.Block}");

    _cpModel.Add(LinearExpr.Sum(group.Select(i => i.IsActive)) > 0).OnlyEnforceIf(anyActive);
    _cpModel.Add(LinearExpr.Sum(group.Select(i => i.IsActive)) == 0).OnlyEnforceIf(anyActive.Not());

    var arcs = new List<Tuple<int, int, ILiteral>>
    {
        Tuple.Create(0, 0, anyActive.Not())
    };

    for (int i = 0; i < eventsInBlock.Count; i++)
    {
        var isFirst = (ILiteral)_cpModel.NewBoolVar($"event_{i + 1}_is_first_in_block_{group.Key.Block}");
		var isLast = (ILiteral)_cpModel.NewBoolVar($"event_{i + 1}_is_last_in_block_{group.Key.Block}");

        arcs.Add(Tuple.Create(0, i + 1, isFirst));
        arcs.Add(Tuple.Create(i + 1, 0, isLast));

        _cpModel.AddImplication(eventsInBlock[i].IsActive.Not(), isFirst.Not());
        _cpModel.AddImplication(eventsInBlock[i].IsActive.Not(), isLast.Not());

        for (int j = 0; j < eventsInBlock.Count; j++)
        {
            if (i == j)
            {
                arcs.Add(Tuple.Create(i + 1, i + 1, eventsInBlock[i].IsActive.Not()));
                continue;
            }

            var literal = (ILiteral)_cpModel.NewBoolVar($"event_{i + 1}_is_before_event_{j + 1}_in_block_{group.Key.Block}");
            arcs.Add(Tuple.Create(i + 1, j + 1, literal));

            _cpModel.AddImplication(literal, eventsInBlock[i].IsActive);
            _cpModel.AddImplication(literal, eventsInBlock[j].IsActive);

            _cpModel.Add(eventsInBlock[i].End == eventsInBlock[j].Start).OnlyEnforceIf(literal);
        }
    }

    _cpModel.AddCircuit(arcs);
}
```
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.