SpeakerSchedulingSat.cs

// Copyright 2010-2022 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using Google.OrTools.Sat;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System;

class SpeakerScheduling
{
    struct Entry
    {
        public BoolVar var;
        public int start;

        public Entry(BoolVar v, int s)
        {
            var = v;
            start = s;
        }
    }

    static void Solve(int first_slot)
    {
        Console.WriteLine("----------------------------------------------------");

        // the slots each speaker is available
        int[][] speaker_availability = {
            new int[] { 1,  3,  4,  6,  7,  10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35,
                        36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59 },
            new int[] { 1,  2,  7,  8,  10, 11, 16, 17, 18, 21, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38,
                        39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 60 },
            new int[] { 5,  6,  7,  10, 12, 14, 16, 17, 21, 22, 23, 24, 33, 35, 37, 38,
                        39, 40, 41, 42, 43, 44, 45, 46, 51, 53, 55, 56, 57, 58, 59 },
            new int[] { 1,  2,  3,  4,  5,  6,  7,  11, 13, 14, 15, 16, 20, 24, 25, 33, 34, 35, 37, 38,
                        39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60 },
            new int[] { 4,  7,  8,  9,  16, 17, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35, 36,
                        37, 38, 39, 40, 41, 42, 43, 49, 50, 51, 53, 55, 56, 57, 58, 59, 60 },
            new int[] { 4,  7,  9,  11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 24, 33, 34,
                        35, 36, 38, 39, 42, 44, 46, 48, 49, 51, 53, 54, 55, 56, 57 },
            new int[] { 1, 2, 3, 4, 5, 6, 7, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 54, 55, 56, 57, 58, 59, 60 },
            new int[] { 1,  3,  11, 14, 15, 16, 17, 21, 22, 23, 24, 25, 33, 35, 36, 37, 39, 40,
                        41, 42, 43, 44, 45, 47, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 },
            new int[] { 1,  2,  3,  4,  5,  7,  8,  9,  10, 11, 13, 18, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35,
                        36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 50, 51, 52, 53, 54, 55, 56, 57, 59, 60 },
            new int[] { 24, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45,
                        49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 },
            new int[] { 1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 16, 17, 18,
                        19, 20, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
                        44, 45, 46, 47, 48, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60 },
            new int[] { 3,  4,  5,  6,  13, 15, 16, 17, 18, 19, 21, 22, 24, 25, 33, 34, 35,
                        36, 37, 39, 40, 41, 42, 43, 44, 45, 47, 52, 53, 55, 57, 58, 59, 60 },
            new int[] { 4,  5,  6,  8,  11, 12, 13, 14, 17, 19, 20, 22, 23, 24, 25, 33, 34,
                        35, 36, 37, 39, 40, 41, 42, 43, 47, 48, 49, 50, 51, 52, 55, 56, 57 },
            new int[] { 2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
                        20, 21, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,
                        45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 },
            new int[] { 12, 25, 33, 35, 36, 37, 39, 41, 42, 43, 48, 51, 52, 53, 54, 57, 59, 60 },
            new int[] { 4, 8, 16, 17, 19, 23, 25, 33, 34, 35, 37, 41, 44, 45, 47, 48, 49, 50 },
            new int[] { 3, 23, 24, 25, 33, 35, 36, 37, 38, 39, 40, 42, 43, 44, 49, 50, 53, 54, 55, 56, 57, 58, 60 },
            new int[] { 7,  13, 19, 20, 22, 23, 24, 25, 33, 34, 35, 38, 40, 41,
                        42, 44, 45, 46, 47, 48, 49, 52, 53, 54, 58, 59, 60 }
        };
        // how long each talk lasts for each speaker
        int[] durations = { 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        int sum_of_durations = durations.Sum();
        int number_of_speakers = durations.Length;

        // calculate the total number of slots (maximum in the availability array)
        // (and add the max durations)
        int last_slot = (from s in Enumerable.Range(0, number_of_speakers) select speaker_availability[s].Max()).Max();
        Console.WriteLine($"Scheduling {number_of_speakers} speakers, for a total of " +
                          $"{sum_of_durations} slots, during [{first_slot}..{last_slot}]");

        CpModel model = new CpModel();

        // We store the possible entries (var, start) for all talks filtered
        // from the duration and the speaker availability.
        List<Entry>[] entries = new List<Entry>[number_of_speakers];
        for (int speaker = 0; speaker < number_of_speakers; ++speaker)
        {
            entries[speaker] = new List<Entry>();
        }

        List<BoolVar>[] contributions_per_slot = new List<BoolVar>[last_slot + 1];
        for (int slot = 1; slot <= last_slot; ++slot)
        {
            contributions_per_slot[slot] = new List<BoolVar>();
        }

        for (int speaker = 0; speaker < number_of_speakers; ++speaker)
        {
            List<BoolVar> all_vars = new List<BoolVar>();
            int duration = durations[speaker];
            // Let's filter the possible starts.
            int availability = speaker_availability[speaker].Length;
            for (int index = 0; index < availability; ++index)
            {
                bool ok = true;
                int slot = speaker_availability[speaker][index];
                if (slot < first_slot)
                {
                    continue;
                }
                for (int offset = 1; offset < duration; ++offset)
                {
                    if (index + offset >= availability ||
                        speaker_availability[speaker][index + offset] != slot + offset)
                    {
                        // discontinuity.
                        ok = false;
                        break;
                    }
                }
                if (ok)
                {
                    BoolVar var = model.NewBoolVar("speaker " + (speaker + 1) + " starts at " + slot);
                    entries[speaker].Add(new Entry(var, slot));
                    all_vars.Add(var);
                    for (int offset = 0; offset < duration; ++offset)
                    {
                        contributions_per_slot[slot + offset].Add(var);
                    }
                }
            }
            model.AddExactlyOne(all_vars);
        }
        // Force the schedule to be consistent.
        for (int slot = first_slot; slot <= last_slot; ++slot)
        {
            model.AddAtMostOne(contributions_per_slot[slot]);
        }

        // Creates last_slot.
        IntVar last_slot_var = model.NewIntVar(first_slot + sum_of_durations - 1, last_slot, "last_slot");
        for (int speaker = 0; speaker < number_of_speakers; speaker++)
        {
            int duration = durations[speaker];
            foreach (Entry e in entries[speaker])
            {
                model.Add(last_slot_var >= e.start + duration - 1).OnlyEnforceIf(e.var);
            }
        }

        model.Minimize(last_slot_var);

        // Creates the solver and solve.
        CpSolver solver = new CpSolver();
        solver.StringParameters = "num_search_workers:8";
        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal)
        {
            Console.WriteLine("\nLast used slot: " + solver.Value(last_slot_var));
            Console.WriteLine("Speakers (start..end):");
            for (int speaker = 0; speaker < number_of_speakers; speaker++)
            {
                foreach (Entry e in entries[speaker])
                {
                    if (solver.BooleanValue(e.var))
                    {
                        Console.WriteLine("  - speaker {0,2}: {1,2}..{2,2}", (speaker + 1), e.start,
                                          (e.start + durations[speaker] - 1));
                    }
                }
            }
        }

        // Statistics.
        Console.WriteLine(solver.ResponseStats());
    }

    public static void Main(String[] args)
    {
        int start = 1;
        if (args.Length >= 2)
        {
            start = int.Parse(args[1]);
        }
        Stopwatch s = new Stopwatch();
        s.Start();
        for (int i = start; i < 40; i++)
        {
            Solve(i);
        }

        s.Stop();
        Console.WriteLine("Finished in " + s.ElapsedMilliseconds + " ms");
    }
}