298 lines
11 KiB
Python
298 lines
11 KiB
Python
#!/usr/bin/env python3
|
|
# Copyright 2010-2025 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.
|
|
|
|
"""Horse Jumping Show.
|
|
|
|
A major three-day horse jumping competition is scheduled next winter in Geneva.
|
|
The show features riders and horses from all over the world, competing in
|
|
several different competitions throughout the show. Six months before the show,
|
|
riders submit the entries (i.e., rider name, horse, competition) to the
|
|
organizers. Riders can submit multiple entries, for example, to compete in the
|
|
same competition with multiple horses, or to compete in several competitions.
|
|
|
|
There are additional space limitations. For example, the venue has 100 stalls,
|
|
4 arenas (where competitions can be scheduled), and 6 paddocks (where riders
|
|
warm up before their turn). It is also ideal that paddocks are not overloaded by
|
|
riders from multiple competitions.
|
|
|
|
The organizer's goal is find a schedule in which competitions don't overlap, and
|
|
the times at which they happen are scattered throughout the day (and hopefully
|
|
not that early in the morning). The starting times of the competitions should be
|
|
at the hour or 30 minutes past the hour (e.g. 9:30, 10:00, 10:30, etc.).
|
|
Competitions can only be scheduled while there is daylight, except for
|
|
competitions scheduled in the Main Stage arena, which is covered and has proper
|
|
lighting. Also, beginner competitions (1.10m or less) are scheduled on the first
|
|
day, and advanced competitions (1.50m or more) are scheduled on the last day.
|
|
|
|
The information for next winter's show is as follows:
|
|
Available stalls: 100
|
|
Number of riders: 100
|
|
Number of horses: 130
|
|
Number of requested Entries: 200
|
|
Number of competitions: 15
|
|
|
|
Venue:
|
|
- Main Stage arena: Covered (9AM-11PM)
|
|
- Highlands arena: Daylight Only (9AM-5PM)
|
|
- Sawdust arena: Daylight Only (9AM-5PM)
|
|
- Paddock1 has capacity for 10 riders and serves Main Stage
|
|
- Paddock2 has capacity for 6 riders and serves Main Stage
|
|
- Paddock3 has capacity for 8 riders and serves Main Stage, Highlands
|
|
- Paddock4 has capacity for 8 riders and serves Highlands, Sawdust
|
|
- Paddock5 has capacity for 9 riders and serves Sawdust
|
|
- Paddock6 has capacity for 7 riders and serves Sawdust
|
|
|
|
competitions:
|
|
- C_5_1.10m_Year_Olds 1.10m - 60 minutes
|
|
- C_6_1.25m_Year_Olds 1.25m - 90 minutes
|
|
- C_7_1.35m_Year_Olds 1.35m - 120 minutes
|
|
- C_0.8m_Jumpers 0.80m - 240 minutes
|
|
- C_1.0m_Jumpers 1.00m - 180 minutes
|
|
- C_1.10m_Jumpers 1.10m - 180 minutes
|
|
- C_1.20m_Jumpers 1.20m - 120 minutes
|
|
- C_1.30m_Jumpers 1.30m - 120 minutes
|
|
- C_1.40m_Jumpers 1.40m - 120 minutes
|
|
- C_1.20m_Derby 1.20m - 180 minutes
|
|
- C_1.35m_Derby 1.35m - 180 minutes
|
|
- C_1.45m_Derby 1.45m - 180 minutes
|
|
- C_1.40m_Open 1.40m - 120 minutes
|
|
- C_1.50m_Open 1.50m - 180 minutes
|
|
- C_1.60m_Grand_Prix 1.60m - 240 minutes
|
|
"""
|
|
|
|
import dataclasses
|
|
from absl import app
|
|
import numpy as np
|
|
from ortools.sat.python import cp_model
|
|
|
|
|
|
@dataclasses.dataclass(frozen=True)
|
|
class Arena:
|
|
"""Data for an arena."""
|
|
|
|
id: str
|
|
hours: str
|
|
|
|
|
|
@dataclasses.dataclass(frozen=True)
|
|
class Competition:
|
|
"""Data for a competition."""
|
|
|
|
id: str
|
|
height: float
|
|
duration: int
|
|
|
|
|
|
@dataclasses.dataclass(frozen=True)
|
|
class HorseJumpingShowData:
|
|
"""Horse Jumping Show Data."""
|
|
|
|
num_days: int
|
|
competitions: list[Competition]
|
|
arenas: list[Arena]
|
|
|
|
|
|
@dataclasses.dataclass(frozen=True)
|
|
class ScheduledCompetition:
|
|
"""Horse Jumping Show Schedule."""
|
|
|
|
completion: str
|
|
day: int
|
|
arena: str
|
|
start_time: str
|
|
end_time: str
|
|
|
|
|
|
def generate_horse_jumping_show_data() -> HorseJumpingShowData:
|
|
"""Generates the horse jumping show data."""
|
|
arenas = [
|
|
Arena(id="Main Stage", hours="9AM-9PM"),
|
|
Arena(id="Highlands", hours="9AM-5PM"),
|
|
Arena(id="Sawdust", hours="9AM-5PM"),
|
|
]
|
|
competitions = [
|
|
Competition(id="C_5_1.10m_Year_Olds", height=1.1, duration=60),
|
|
Competition(id="C_6_1.25m_Year_Olds", height=1.25, duration=90),
|
|
Competition(id="C_7_1.35m_Year_Olds", height=1.35, duration=120),
|
|
Competition(id="C_0.8m_Jumpers", height=0.8, duration=240),
|
|
Competition(id="C_1.0m_Jumpers", height=1.0, duration=180),
|
|
Competition(id="C_1.10m_Jumpers", height=1.10, duration=180),
|
|
Competition(id="C_1.20m_Jumpers", height=1.20, duration=120),
|
|
Competition(id="C_1.30m_Jumpers", height=1.30, duration=120),
|
|
Competition(id="C_1.40m_Jumpers", height=1.40, duration=120),
|
|
Competition(id="C_1.20m_Derby", height=1.20, duration=180),
|
|
Competition(id="C_1.35m_Derby", height=1.35, duration=180),
|
|
Competition(id="C_1.45m_Derby", height=1.45, duration=180),
|
|
Competition(id="C_1.40m_Open", height=1.40, duration=120),
|
|
Competition(id="C_1.50m_Open", height=1.50, duration=180),
|
|
Competition(id="C_1.60m_Grand_Prix", height=1.60, duration=240),
|
|
]
|
|
return HorseJumpingShowData(num_days=3, competitions=competitions, arenas=arenas)
|
|
|
|
|
|
def solve() -> list[ScheduledCompetition]:
|
|
"""Solves the horse jumping show problem."""
|
|
data = generate_horse_jumping_show_data()
|
|
num_days = data.num_days
|
|
competitions = data.competitions
|
|
arenas = data.arenas
|
|
day_index = list(range(num_days))
|
|
|
|
# Time parser.
|
|
def parse_time(t_str):
|
|
hour = int(t_str[:-2])
|
|
if "PM" in t_str and hour != 12:
|
|
hour += 12
|
|
if "AM" in t_str and hour == 12:
|
|
hour = 0
|
|
return hour * 60
|
|
|
|
# Schedule time intervals for each arena.
|
|
schedule_interval_by_arena = {}
|
|
for arena in arenas:
|
|
start_h_str, end_h_str = arena.hours.split("-")
|
|
start_time = parse_time(start_h_str)
|
|
end_time = parse_time(end_h_str)
|
|
schedule_interval_by_arena[arena.id] = (start_time, end_time)
|
|
|
|
# Map time to 30-minute intervals and back.
|
|
time_slot_size = 30
|
|
|
|
def time_to_slot(time_in_minutes: int):
|
|
return time_in_minutes // time_slot_size
|
|
|
|
def slot_to_time(slot_index: int):
|
|
return slot_index * time_slot_size
|
|
|
|
# --- Model Creation ---
|
|
model = cp_model.CpModel()
|
|
|
|
# --- Variables ---
|
|
# Competition scheduling variables per arena and day.
|
|
competition_assignments = np.empty(
|
|
(len(competitions), len(arenas), num_days), dtype=object
|
|
)
|
|
for c, comp in enumerate(competitions):
|
|
for a, arena in enumerate(arenas):
|
|
for d in day_index:
|
|
competition_assignments[c, a, d] = model.new_bool_var(
|
|
f"competition_scheduled_{comp.id}_{arena.id}_{d}"
|
|
)
|
|
# Time intervals and start times for each competition. We model time steps
|
|
# 0,1,2,... to represent the start times in 30 minutes intervals, as opposed
|
|
# to represent the start times in minutes.
|
|
competition_start_times = np.empty(
|
|
(len(competitions), len(arenas), num_days), dtype=object
|
|
)
|
|
competition_intervals = np.empty(
|
|
(len(competitions), len(arenas), num_days), dtype=object
|
|
)
|
|
for c, comp in enumerate(competitions):
|
|
for a, arena in enumerate(arenas):
|
|
earliest_start_time, latest_end_time = schedule_interval_by_arena[arena.id]
|
|
latest_start_time = latest_end_time - comp.duration
|
|
for d in day_index:
|
|
competition_start_times[c, a, d] = model.new_int_var(
|
|
time_to_slot(earliest_start_time),
|
|
time_to_slot(latest_start_time),
|
|
f"start_time_{comp.id}_{arena.id}_{d}",
|
|
)
|
|
competition_intervals[c, a, d] = (
|
|
model.new_optional_fixed_size_interval_var(
|
|
competition_start_times[c, a, d],
|
|
time_to_slot(comp.duration),
|
|
competition_assignments[c, a, d],
|
|
f"task_{comp.id}_{arena.id}_{d}",
|
|
)
|
|
)
|
|
|
|
# --- Constraints ---
|
|
# Every competition must be scheduled, enforcing that beginner competitions
|
|
# are on day 1, and advanced competitions are on day 3.
|
|
for c, comp in enumerate(competitions):
|
|
model.add(np.sum(competition_assignments[c, :, :]) == 1)
|
|
# Beginner competitions are on the first day.
|
|
if comp.height <= 1.10:
|
|
beginners_day = 0
|
|
model.add(np.sum(competition_assignments[c, :, beginners_day]) == 1)
|
|
# Advanced competitions are on the last day.
|
|
if comp.height >= 1.50:
|
|
advanced_day = num_days - 1
|
|
model.add(np.sum(competition_assignments[c, :, advanced_day]) == 1)
|
|
|
|
# Competitions scheduled on the same arena and on the same day can't overlap.
|
|
for a, _ in enumerate(arenas):
|
|
for day in range(num_days):
|
|
model.add_no_overlap(competition_intervals[:, a, day])
|
|
|
|
# Start times should be scattered across the day.
|
|
for a, _ in enumerate(arenas):
|
|
for day in day_index:
|
|
model.add_all_different(competition_start_times[:, a, day])
|
|
|
|
# --- Objective ---
|
|
model.maximize(np.sum(competition_start_times))
|
|
|
|
# --- Solve ---
|
|
solver = cp_model.CpSolver()
|
|
solver.parameters.max_time_in_seconds = 30.0
|
|
solver.parameters.log_search_progress = True
|
|
solver.parameters.num_workers = 16
|
|
status = solver.solve(model)
|
|
|
|
# --- Print Solution ---
|
|
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
|
|
schedule = []
|
|
for day in range(num_days):
|
|
for c, comp in enumerate(competitions):
|
|
for a, arena in enumerate(arenas):
|
|
if solver.value(competition_assignments[c, a, day]):
|
|
start_time_minutes = slot_to_time(
|
|
solver.value(competition_start_times[c, a, day])
|
|
)
|
|
start_h, start_m = divmod(start_time_minutes, 60)
|
|
end_h, end_m = divmod(start_time_minutes + comp.duration, 60)
|
|
schedule.append(
|
|
ScheduledCompetition(
|
|
completion=comp.id,
|
|
day=day + 1,
|
|
arena=arena.id,
|
|
start_time=f"{start_h:02d}:{start_m:02d}",
|
|
end_time=f"{end_h:02d}:{end_m:02d}",
|
|
)
|
|
)
|
|
# Sort and print schedule for readability.
|
|
schedule.sort(key=lambda x: (x.day, x.start_time))
|
|
print("Schedule:")
|
|
for item in schedule:
|
|
print(
|
|
f"Day {item.day}: {item.completion} in {item.arena} from"
|
|
f" {item.start_time} to {item.end_time}."
|
|
)
|
|
return schedule
|
|
elif status == cp_model.INFEASIBLE:
|
|
print("Problem is infeasible.")
|
|
else:
|
|
print("No solution found.")
|
|
# Return an empty schedule if no solution is found.
|
|
return []
|
|
|
|
|
|
def main(_):
|
|
solve()
|
|
|
|
|
|
if __name__ == "__main__":
|
|
app.run(main)
|