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.

Improve this question
$\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
    Commented Mar 6, 2020 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
    Commented Mar 7, 2020 at 22:08
  • 1
    $\begingroup$ You have to create a (i, i) loop. $\endgroup$
    – Stradivari
    Commented Mar 7, 2020 at 23:49
  • $\begingroup$ with the negations of the task being active as literal. $\endgroup$
    – Laurent Perron
    Commented Mar 9, 2020 at 6:33
  • $\begingroup$ Thanks for your comments. I'll summarize it in an answer below. $\endgroup$
    – crypto_rsa
    Commented Mar 10, 2020 at 9:26

1 Answer 1

Reset to default
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);
}
```
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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