⚡ Academic Scheduler | CSP Optimization Engine

Academic Scheduler is a high-performance Python engine designed to solve the University Timetabling Problem, a classic NP-Hard constraint satisfaction challenge. Unlike simple randomized scripts, this project implements a dual-engine architecture offering both an Exact Solver (guaranteed mathematical optimum) and a Heuristic Solver (rapid approximation).

The system models complex academic environments, managing hard constraints (physical room capacity, equipment requirements) and optimizing soft constraints (professor preferences, student schedule compactness).

---

📊 Optimization Results

The engine generates strictly validated schedules. Below is a comparison of the output perspectives:

Student View (Grid) Minimizes gaps and guarantees non-overlapping subjects per year.

Professor View (Detail) Respects individual time-slot preferences and availability.

---

🏗️ Algorithmic Architecture

This project demonstrates two different approaches to the Branch & Bound algorithm. While both engines traverse the search space tree using Depth-First Search (DFS), they differ fundamentally in their Pruning Strategy (how they decide to discard a branch).

1. The Exact Solver (Optimistic Bounding)

Located in ExactScheduler.py.

• Strategy: Look-ahead Pruning (calculate_optimistic_bound).
• Logic: Before exploring a branch, this solver calculates the Lower Bound of the cost. It adds the current accumulated cost PLUS the unavoidable future costs (e.g., a professor who still needs to teach 2 classes but has run out of preferred slots).
• Guarantee: It only prunes a branch when it is mathematically certain that the path cannot beat the current best record. This guarantees finding the Global Optimum.

2. The Heuristic Solver (Direct Pruning)

Located in HeuristicScheduler.py.

• Strategy: Aggressive Pruning based on Current State.
• Logic: It compares the current_cost directly against the best_cost_found. If the current partial schedule is already worse than or equal to the best complete schedule found so far, it cuts the branch immediately.
• Trade-off: It avoids the computational overhead of calculating future bounds. While theoretically less "prescient" than the Exact solver, in practice, it traverses the tree faster for complex datasets where a "good enough" solution is needed in real-time.

---

🚀 Key Features

• Constraint Modeling:
  • Hard Constraints: Room capacity, overlapping professors, lab equipment requirements (PC/Hardware), year-group collisions.
  • Soft Constraints: Professor time preferences, minimization of student idle hours (gaps), efficient day usage.
• Cost Function: A dynamic scoring system (0 = Perfect Schedule). The algorithms minimize penalties for gaps between classes and unmet professor preferences.
• Domain-Driven Design: Clean separation between entities (Subject, Professor, Classroom) and the solving logic, adhering to the Single Responsibility Principle.

---

💻 Usage & Execution

1. Clone the repository.
2. Select your desired engine in main.py (Uncomment ExactScheduler or HeuristicScheduler).
3. Run the script to start the optimization process.
4. Review Artifacts: The engine will generate two detailed reports in the root directory:
   • horario_alumnos.txt: Student-facing timetable grouped by academic year.
   • horario_profes.txt: Detailed faculty schedule including availability matches.