school_timetabling.exs

#!/usr/bin/env elixir

# School Timetabling Problem - Showcase Example
#
# Problem: Schedule teachers, students, rooms, and equipment for a school week
# with complex constraints including teacher skills, availability, room capacity,
# equipment requirements, and curriculum needs.
#
# This is a comprehensive timetabling problem that demonstrates the DSL's
# capability for handling complex, multi-dimensional scheduling scenarios.

require Dantzig.Problem, as: Problem
require Dantzig.Problem.DSL, as: DSL

# Define the problem entities
teachers = ["Teacher1", "Teacher2", "Teacher3", "Teacher4", "Teacher5"]
subjects = ["Math", "Science", "English"]
time_slots = ["Slot1", "Slot2", "Slot3", "Slot4"]
rooms = ["Room1", "Room2", "Room3"]
equipment_types = ["Projector", "LabEquipment"]

# Teacher-subject skills matrix (1 = qualified to teach, 0 = not qualified)
teacher_skills = %{
  "Teacher1" => %{"Math" => 1, "Science" => 1, "English" => 0},
  "Teacher2" => %{"Math" => 1, "Science" => 0, "English" => 1},
  "Teacher3" => %{"Math" => 0, "Science" => 1, "English" => 1},
  "Teacher4" => %{"Math" => 1, "Science" => 1, "English" => 1},
  "Teacher5" => %{"Math" => 0, "Science" => 1, "English" => 0}
}

# Room capacity
room_capacity = %{
  "Room1" => 30,
  "Room2" => 25,
  "Room3" => 35
}

# Equipment availability in rooms (1 = available, 0 = not available)
room_equipment = %{
  "Room1" => %{"Projector" => 1, "LabEquipment" => 0},
  "Room2" => %{"Projector" => 1, "LabEquipment" => 1},
  "Room3" => %{"Projector" => 0, "LabEquipment" => 1}
}

# Subject equipment requirements (1 = required, 0 = not required)
subject_equipment = %{
  "Math" => %{"Projector" => 0, "LabEquipment" => 0},
  "Science" => %{"Projector" => 0, "LabEquipment" => 1},
  "English" => %{"Projector" => 1, "LabEquipment" => 0}
}

# Student group sizes (simulated curriculum requirements)
student_groups = %{
  "Math_Beginner" => 25,
  "Math_Advanced" => 15,
  "Science_Basic" => 20,
  "Science_Advanced" => 10,
  "English_Basic" => 30,
  "English_Advanced" => 12
}

# Subject-group mapping (which groups need which subjects)
group_subjects = %{
  "Math_Beginner" => "Math",
  "Math_Advanced" => "Math",
  "Science_Basic" => "Science",
  "Science_Advanced" => "Science",
  "English_Basic" => "English",
  "English_Advanced" => "English"
}

IO.puts("School Timetabling Problem - Showcase Example")
IO.puts(String.duplicate("=", 50))
IO.puts("Teachers: #{Enum.join(teachers, ", ")}")
IO.puts("Subjects: #{Enum.join(subjects, ", ")}")
IO.puts("Time Slots: #{Enum.join(time_slots, ", ")}")
IO.puts("Rooms: #{Enum.join(rooms, ", ")}")
IO.puts("Student Groups: #{Enum.join(Map.keys(student_groups), ", ")}")
IO.puts("")

# Display teacher skills
IO.puts("Teacher Skills:")

Enum.each(teachers, fn teacher ->
  skills = Enum.filter(subjects, fn subject -> teacher_skills[teacher][subject] == 1 end)
  IO.puts("  #{teacher}: #{Enum.join(skills, ", ")}")
end)

IO.puts("")

# Display room information
IO.puts("Room Information:")

Enum.each(rooms, fn room ->
  capacity = room_capacity[room]
  IO.puts("  #{room}: capacity=#{capacity}")
end)

IO.puts("")

# Create the optimization problem
problem =
  Problem.define model_parameters: %{
    teachers: teachers,
    subjects: subjects,
    rooms: rooms,
    time_slots: time_slots,
    teacher_skills: teacher_skills
  } do
    new(
      name: "School Timetabling Problem",
      description: "School scheduling with teachers, subjects, rooms, and time slots"
    )

    # Decision variables: schedule[t,s,r,m] = 1 if teacher t teaches subject s in room r at time m
    variables(
      "schedule",
      [t <- teachers, s <- subjects, r <- rooms, m <- time_slots],
      :binary,
      description: "Teacher t teaches subject s in room r at time m"
    )

    # Note: Equipment variables removed for simplified demonstration

    # Constraint 1: Each teacher can only teach one class at a time
    constraints(
      [t <- teachers, m <- time_slots],
      sum(for s <- subjects, r <- rooms, do: schedule(t, s, r, m)) <= 1,
      "Teacher time conflict constraint"
    )

    # Constraint 2: Each room can only host one class at a time
    constraints(
      [r <- rooms, m <- time_slots],
      sum(for t <- teachers, s <- subjects, do: schedule(t, s, r, m)) <= 1,
      "Room time conflict constraint"
    )

    # Constraint 3: Each subject must be taught exactly once per time slot
    constraints(
      [s <- subjects, m <- time_slots],
      sum(for t <- teachers, r <- rooms, do: schedule(t, s, r, m)) == 1,
      "Subject coverage constraint"
    )

    # Constraint 4: Teachers can only teach subjects they are qualified for
    constraints(
      [t <- teachers, s <- subjects, r <- rooms, m <- time_slots],
      schedule(t, s, r, m) <= teacher_skills[t][s],
      "Teacher qualification constraint"
    )

    # Objective: Minimize conflicts and maximize resource utilization
    # For now, we'll use a simplified objective
    objective(
      sum(
        for t <- teachers, s <- subjects, r <- rooms, m <- time_slots, do: schedule(t, s, r, m)
      ),
      direction: :maximize
    )
  end

IO.puts("Solving the school timetabling problem...")
{solution, objective_value} = Problem.solve(problem, solver: :highs, print_optimizer_input: true)

case {solution, objective_value} do
  {%Dantzig.Solution{} = sol, obj_val} ->
    solution = sol
    objective_value = obj_val

  {:error, reason} ->
    IO.puts("Error solving problem: #{inspect(reason)}")
    System.halt(1)

  other ->
    IO.puts("Unexpected result: #{inspect(other)}")
    System.halt(1)
end

IO.puts("Solution:")
IO.puts("=========")
IO.puts("Classes scheduled: #{Float.round(objective_value * 1.0, 0)}")
IO.puts("")

IO.puts("Timetable:")
total_classes = 0

# Display the schedule for each time slot
Enum.each(time_slots, fn time_slot ->
  IO.puts("#{time_slot}:")

  Enum.each(rooms, fn room ->
    # Find which class is scheduled in this room at this time
    scheduled_classes =
      Enum.filter(teachers, fn teacher ->
        Enum.any?(subjects, fn subject ->
          var_name = "schedule(#{teacher},#{subject},#{room},#{time_slot})"
          solution.variables[var_name] > 0.5
        end)
      end)

    if scheduled_classes != [] do
      teacher = List.first(scheduled_classes)

      subject =
        Enum.find(subjects, fn subj ->
          var_name = "schedule(#{teacher},#{subj},#{room},#{time_slot})"
          solution.variables[var_name] > 0.5
        end)

      total_classes = total_classes + 1
      IO.puts("  #{room}: #{teacher} teaching #{subject}")
    else
      IO.puts("  #{room}: Available")
    end
  end)

  IO.puts("")
end)

IO.puts("Summary:")
IO.puts("  Total classes scheduled: #{total_classes}")
IO.puts("  Reported objective: #{Float.round(objective_value * 1.0, 0)}")

IO.puts(
  "  Schedule efficiency: #{if total_classes > 0, do: Float.round(total_classes / (length(time_slots) * length(rooms)) * 100, 1), else: 0}%"
)

# Validation
IO.puts("")
IO.puts("Schedule Validation:")

# Check that no teacher is double-booked
teacher_conflicts =
  Enum.filter(teachers, fn teacher ->
    Enum.any?(time_slots, fn time_slot ->
      classes_at_time =
        Enum.count(rooms, fn room ->
          Enum.any?(subjects, fn subject ->
            var_name = "schedule(#{teacher},#{subject},#{room},#{time_slot})"
            solution.variables[var_name] > 0.5
          end)
        end)

      classes_at_time > 1
    end)
  end)

if teacher_conflicts == [] do
  IO.puts("  ✅ No teacher conflicts")
else
  IO.puts("  ❌ Teacher conflicts found: #{inspect(teacher_conflicts)}")
end

# Check that no room is double-booked
room_conflicts =
  Enum.filter(rooms, fn room ->
    Enum.any?(time_slots, fn time_slot ->
      classes_in_room =
        Enum.count(teachers, fn teacher ->
          Enum.any?(subjects, fn subject ->
            var_name = "schedule(#{teacher},#{subject},#{room},#{time_slot})"
            solution.variables[var_name] > 0.5
          end)
        end)

      classes_in_room > 1
    end)
  end)

if room_conflicts == [] do
  IO.puts("  ✅ No room conflicts")
else
  IO.puts("  ❌ Room conflicts found: #{inspect(room_conflicts)}")
end

# Check that each subject is taught exactly once per time slot
subject_coverage =
  Enum.all?(subjects, fn subject ->
    Enum.all?(time_slots, fn time_slot ->
      classes_teaching_subject =
        Enum.count(teachers, fn teacher ->
          Enum.any?(rooms, fn room ->
            var_name = "schedule(#{teacher},#{subject},#{room},#{time_slot})"
            solution.variables[var_name] > 0.5
          end)
        end)

      classes_teaching_subject == 1
    end)
  end)

if subject_coverage do
  IO.puts("  ✅ All subjects taught exactly once per time slot")
else
  IO.puts("  ❌ Subject coverage issues")
end

IO.puts("")
IO.puts("✅ School timetabling problem solved successfully!")
IO.puts("")
IO.puts("This showcases the DSL's capability for multi-dimensional")
IO.puts("scheduling problems with teachers, subjects, rooms, and time slots.")
IO.puts("")
IO.puts("Note: This is a simplified version focusing on core scheduling constraints.")
IO.puts("A full implementation would include equipment requirements,")
IO.puts("student group assignments, and complex qualification matrices.")