% =============================================================================
% PREAMBLE: Document Class and Packages
% =============================================================================
\documentclass[12pt,reqno]{amsart}
\boldmath

% % --- Page Layout ---
\setlength{\textheight}{22.4cm} 
\setlength{\textwidth}{15.4cm} 
\setlength{\oddsidemargin}{1.2cm} 
\setlength{\evensidemargin}{1.2cm} 
\topmargin = -0.3in





\usepackage{tikz}
\usetikzlibrary{arrows, snakes} %for arrowtips  
\usetikzlibrary{arrows.meta}
\usepackage[sc]{mathpazo}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage{graphicx}
\usetikzlibrary{positioning, calc}

\linespread{1.2}
\setlength{\parindent}{0pt}
\renewcommand{\baselinestretch}{1.1}
\usepackage{amsmath, amsthm, amscd, amsfonts, amssymb, graphicx, xcolor}
\hypersetup{
    colorlinks,
    linkcolor={red!80!black},
    citecolor={blue!80!black},
    urlcolor={blue!80!black}
}



% --- Essential Mathematics Packages ---
\usepackage{amsmath, amssymb} % AMS packages for math symbols and environments

% --- Optimization Problem Formatting ---
\usepackage{optidef} % For the 'mini' environment to format optimization problems
\usepackage[normalem]{ulem} % For the \st{} command (strikethrough) for subheadings. The [normalem] option keeps \emph as italic.

% --- Graphics, Tables, and Code ---
\usepackage{graphicx} % For including figures (e.g., charts)
\usepackage{booktabs} % For creating professional-looking tables
\usepackage{listings} % For formatting source code snippets
\usepackage{color}

% --- Hyperlinks and Referencing ---
\usepackage{hyperref} % Makes references and URLs clickable
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    urlcolor=blue,
    citecolor=red
}

% --- Custom Commands (Optional but useful) ---
% Example: A command for inline code
\newcommand{\code}[1]{\texttt{#1}}

% --- Python Code Style for the 'listings' package ---
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{pythonstyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{blue},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}
\lstset{style=pythonstyle}




% =============================================================================
% TITLE BLOCK: Title, Author, and Metadata

% ===================================================
\title[MIP-Based Optimization for University Timetabling]{MIP-Based Optimization for University Timetabling: Formulation and Implementation}

\author{Benjamin Kikwai}
\address{Department of Mathematics and Statistics - Machakos University, 
Kenya}
%90100-Machakos, 
\email{kikwaib@mksu.ac.ke}

\author{Jared Ongaro}
\address{Department of Mathematics - University of Nairobi,
00100-Nairobi, Kenya}
\email{ongaro@uonbi.ac.ke}

\date{\today}

\keywords{Mixed-Integer Programming, University Timetabling, Curriculum-based timetabling Course Scheduling, Combinatorial Optimisation, Open-Source Solvers, Python}
\subjclass[2010]{65K05, 90-08}



\begin{document}
%
%\begin{mintedbox}{python}
%if transactions: Transaction.create_transactions() # if transactions = "true"
%node.generate_emptyState() # empty state for all nodes
%S.initial_events() # initiate initial events to start with
%
%while not queue.isEmpty() and clock <= targetTime:
%      next_e = queue.get_next_event()
%      clock = next_e.time # move clock to the time of the event
%      Event.execute_event(next_e)
%      Queue.remove_event(next_e)
%
%print results
%\end{mintedbox}


% =============================================================================
% FRONT MATTER: Abstract and Title
% =============================================================================
    \begin{abstract}
 This paper presents a comprehensive solution to the University Course Timetabling Problem (UCTP) through the lens of a flexible Mixed-Integer Programming (MIP) model. The model is designed to generate conflict-free schedules by assigning courses to instructors, rooms, and time slots, while minimising a weighted penalty function that rigorously quantifies soft objectives related to student conflicts, inefficient room utilisation, and instructor preferences. A key contribution is the provision of a practical, end-to-end implementation guide using an entirely open-source Python stack (Pandas, PuLP, CBC). This demonstration outlines the complete workflow, from simple CSV data inputs to a verifiable, human-readable timetable. The full implementation code is made publicly available for reproducibility. We conclude by analysing the inherent computational scalability challenges of this exact MIP approach and propose hybrid solution methodologies as a promising direction for future research on large-scale, real-world instances.   
    
    
    
    
%        This paper investigates the University Course Timetabling Problem (UCTP) through the development and application of a Mixed-Integer Programming (MIP) model.
%        The study addresses the complex challenge of assigning courses to instructors, rooms, and time slots while satisfying a variety of hard operational constraints and balancing multiple competing soft objectives.
%        We present a detailed and flexible MIP formulation designed to minimize a weighted sum of penalties related to student course conflicts, inefficient room utilization, instructor scheduling inconvenience, and violations of teaching preferences.
%
%        A key contribution of this work is a practical guide for implementing this model using an accessible, open-source technology stack centred on Python, the Pandas library for data handling, and the PuLP modeling library with the CBC solver.
%        We outline a complete workflow, from structuring input data in simple CSV files to generating a final, human-readable timetable.
%        The full implementation is made available for reproducibility.
%        Finally, the paper discusses the inherent computational challenges and scalability limitations of the MIP-based approach, providing a critical perspective on its applicability to large-scale instances and suggesting avenues for future research, including the exploration of hybrid solution methodologies.
    \end{abstract}

    \maketitle


% =============================================================================
% BODY OF THE ARTICLE
% =============================================================================


    \section{Introduction}
    \label{sec:introduction}
    

The construction of a weekly timetable in any university constitutes a complex multi-criteria optimisation problem, governed by a multitude of variables, preferences, and operational constraints~\cite{Carter1997}.
Factors such as core curriculum sequence, faculty availability, room capacities, and diverse student  enrolment patterns must be concurrently satisfied.
While small institutions may manage this allocation manually, such methods become rapidly intractable and unsustainable as the scale and complexity of the academic programme grow.
Inconsistent, suboptimal schedules often result, failing to effectively meet the needs of the university community.
Consequently, automated approaches are not merely convenient but essential tools for generating effective timetables and minimising administrative overhead.\\

This challenge is formally recognised in academic literature as the University Course Timetabling Problem (UCTP), a well-studied combinatorial optimisation problem.
Researchers have applied a variety of sophisticated techniques to the UCTP, including metaheuristics (such as Tabu Search and Genetic Algorithms)~\cite{Blum2003, Lewis2008} and constraint programming~\cite{Tsang1993}.
Mixed-Integer Programming (MIP), however, offers a distinct and powerful advantage: the ability to model the problem with rigorous mathematical precision and find provably optimal solutions~\cite{Daskalaki2004}. To fully explore the practical strengths and intrinsic limitations of this formal method, this work concentrates exclusively on solving the UCTP as an integer program.\\

Our contributions in this paper are three-fold.
First, we present a detailed MIP formulation designed for real-world applicability. This model captures critical hard constraints (e.g., no resource conflicts) and effectively manages the trade-offs among soft objectives, such as minimising student timetable clashes and respecting staff teaching preferences, through a flexible weighted penalty system.
Second, we provide a practical, detailed roadmap for implementing this model using an accessible, open-source technology stack, thereby significantly lowering the barrier to entry for powerful optimisation techniques.
Third, we offer a critical assessment of the MIP methodology itself, with a particular focus on its computational scalability and performance limitations when applied to realistic problem sizes.\\

    
    
      
  
%    Finally, we critically evaluate the inherent limitations of the MIP approach, particularly concerning its computational scalability.
%
%%    The remainder of this paper is organised as follows.
%%    Section~\ref{sec:lit_review} provides a review of relevant literature on timetabling.
%%    Section~\ref{sec:model} details the mathematical components and the complete MIP formulation of the problem.
%%    Section~\ref{sec:implementation} describes the proposed implementation strategy using Python and open-source solvers.
%%    Section~\ref{sec:limitations} discusses the practical challenges and scalability issues of the MIP-based approach.
%%    Finally, Section~\ref{sec:conclusion} offers concluding remarks and suggests avenues for future research.
%

\section{Literature Review}
\label{sec:lit_review}

The university timetabling problem has been the subject of extensive research, yielding a diverse range of solution methodologies.
Pioneering work by \cite{Werra1985} and \cite{Carter1997} established the problem's foundational complexities, with comprehensive surveys by \cite{Schaerf1999} and later \cite{Lewis2008} providing structured overviews of the field.
Solution techniques can be broadly categorized into three paradigms: exact methods (such as Integer Programming), heuristic and metaheuristic methods (which employ approximation-based search strategies), and constraint programming (which focuses on satisfying a set of logical rules).

\subsection{Exact Methods: A Focus on Mixed-Integer Programming}
\label{subsec:exact-methods-for-uctp:-a-focus-on-mixed-integer-programming}
Integer Programming (IP) and Mixed-Integer Programming (MIP) are cornerstones of exact methods for the UCTP. These approaches uniquely offer the advantage of delivering a provably optimal solution, or at least a feasible solution with a quantifiable optimality gap.
The inherent computational difficulty of timetabling was established early on by \cite{Even1976}, who classified such problems as NP-complete, a challenge further examined by \cite{Cooper1996}.
Despite this complexity, researchers have successfully applied MIP to complex, real-world instances. \cite{Daskalaki2004}, for example, presented a detailed IP formulation for a Greek university, effectively managing hard constraints like resource conflicts and room capacities.
More recently, \cite{Phillips2017} developed an IP model to generate new timetables with minimal deviation from an existing schedule. The versatility of MIP has also been demonstrated in related domains, including patient admission scheduling~\cite{Bastos2019} and urban transport networks~\cite{Chu2018}.
Ultimately, the primary strength of MIP is its capacity to provide a rigorous, structured, and verifiable solution to a well-defined problem instance.

\subsection{Alternative Paradigms for Large-Scale Instances}
\label{subsec:alternative-solution-paradigms-for-large-scale-instances}
While powerful, MIP-based exact methods face significant scalability challenges. As the size and complexity of a timetabling problem increase, the time required to find an optimal solution can become computationally prohibitive.
In response, metaheuristic algorithms have emerged as a popular and effective alternative. These general-purpose search algorithms are designed to find high-quality, feasible solutions within a reasonable time frame, albeit without a guarantee of global optimality.
The surveys by \cite{Blum2003} and \cite{Lewis2008} offer an excellent overview of metaheuristics applied to timetabling, such as genetic algorithms, simulated annealing, and tabu search, which are adept at navigating vast, complex solution spaces.\\

Constraint Programming (CP), detailed by \cite{Tsang1993}, is another paradigm for tackling timetabling problems.
CP models a problem as a set of variables and logical constraints, employing specialised propagation techniques to prune the search space efficiently. It is particularly effective at handling problems defined by a large number of intricate or non-linear logical rules.
As no single method is universally superior, hybridisation has become a critical area of research.
For instance, \cite{Shaw1998} explored integrating CP with local search, combining the former's strength in rapid feasibility checking with the latter's solution-improving capabilities.
Similarly, hybrid approaches that use MIP to solve a core, simplified subproblem before applying metaheuristics for refinement represent a promising direction for large-scale, real-world timetabling.






%
%
%The university timetabling problem has been the subject of extensive research, leading to a diverse range of solution methodologies.
%Pioneering work by \cite{Werra1985} and \cite{Carter1997} established the problem's foundational complexities, with comprehensive surveys by \cite{Schaerf1999} and later \cite{Lewis2008} providing structured overviews of the field.
%Solution techniques can be broadly categorised into three paradigms: exact methods, such as Integer Programming; heuristic and metaheuristic methods, which employ approximation-based search strategies; and constraint programming, which focuses on satisfying a set of logical rules.
%
%\subsection{Exact Methods: A Focus on Mixed-Integer Programming}
%\label{subsec:exact-methods-for-uctp:-a-focus-on-mixed-integer-programming}
%Integer Programming (IP) and Mixed-Integer Programming (MIP) are cornerstones of exact methods for the UCTP. These approaches offer the distinct advantage of delivering a provably optimal solution, or at least a feasible solution with a quantifiable optimality gap.
%The inherent computational difficulty of timetabling was established by \cite{Even1976}, who classified such problems as NP-complete, a challenge further examined by \cite{Cooper1996}.
%Despite this complexity, researchers have successfully applied MIP to real-world instances. \cite{Daskalaki2004}, for example, presented a detailed IP formulation for a Greek university, effectively managing hard constraints like resource conflicts and room capacities.
%More recently, \cite{Phillips2017} developed an IP model to generate new timetables with minimal deviation from an existing schedule. The versatility of MIP has also been demonstrated in related domains, including patient admission scheduling~\cite{Bastos2019} and urban transport networks~\cite{Chu2018}.
%Ultimately, the primary strength of MIP lies in its capacity to provide a rigorous, structured, and verifiable solution to a well-defined problem.
%
%\subsection{Alternative Paradigms for Large-Scale Instances}
%\label{subsec:alternative-solution-paradigms-for-large-scale-instances}
%Although powerful, MIP-based exact methods face significant scalability challenges. As a timetabling problem grows in size and complexity, the time required to find an optimal solution can become computationally prohibitive.
%In response, metaheuristic algorithms have emerged as a popular and effective alternative. These general-purpose search algorithms are designed to find high-quality, feasible solutions within a reasonable timescale, albeit without a guarantee of optimality.
%The surveys by \cite{Blum2003} and \cite{Lewis2008} offer an excellent overview of metaheuristics applied to timetabling, such as genetic algorithms, simulated annealing, and tabu search, which are adept at navigating vast solution spaces.\\
%
%Constraint Programming (CP), detailed by \cite{Tsang1993}, is another powerful paradigm for tackling timetabling problems.
%CP models a problem as a set of variables and logical constraints, employing specialised propagation techniques to prune the search space efficiently. It is particularly adept at handling problems defined by a large number of intricate or non-linear rules.
%As no single method is universally superior, hybridisation has become a key area of research.
%For instance, \cite{Shaw1998} explored integrating CP with local search, combining the former's strength in feasibility checking with the latter's solution-improving capabilities.
%Similarly, hybrid approaches that use MIP to solve a core subproblem before applying metaheuristics for refinement represent a promising direction for large-scale, real-world timetabling.
%


    \section{Mathematical Model of the Timetabling Problem}
    \label{sec:model}

    \subsection{Problem Definition and Components}\label{subsec:problem-definition-and-components}

    University Course Timetabling Problem (UCTP) can be defined as a multi-dimensional assignment problem.
    The primary objective is to find an optimal mapping from the set of courses  $C$ to a Cartesian product of the sets of available time slots $P $, rooms $R $, and instructors $I$.
    This mapping must be \emph{feasible}, satisfying a collection of \emph{ hard constraints}, and optimal, minimising a cost function derived from a set of desirable \emph{soft constraints}.
    The core components that define the structure of the problem instance are as the following sets and indices conventions:

\begin{itemize}
  \item[ \textbf{Courses ($C$):}]   The set of distinct academic course units that must be scheduled within the semester.  Each course $c\in C$ is a fundamental unit of the assignment.  
        \item[ \textbf{  Instructors ($I$):}] The set of instructors available to facilitate the courses.
        We assume a pre-assignment where each course $c$ is linked to a specific instructor \( i  \in  I\).
        \item[\textbf{Rooms ($R$):}] The set of physical locations (e.g., lecture halls, labs) where courses can be held.
        Each room \( r \in  R\)  is characterised by its seating capacity, $Cap_r$.
        \item[\textbf{Time Slots ($P$):}] The set of discrete time intervals during which courses can be scheduled.
        This set is itself a Cartesian product of the set of working days, $D$, and the set of daily periods, $P$.
        Thus, a time slot \( p \in  P \)  is an ordered pair $(d, p)$, where $d \in D$.
        \item[\textbf{Students ($S$):}] To manage the complexity of student enrolments, we consider cohorts of students as single entities.
        A student group, or cohort, \( s  \in  S\), represents a collection of students with identical course enrolment patterns.
        This abstraction allows for the efficient management of student-related constraints.
\end{itemize}






    \begin{figure}[!ht]
    \centering
    \begin{tikzpicture}[
    every node/.style={align=center},
    font=\sffamily
]

% Manually place 4 top nodes evenly spaced
\node (rooms) at (0, 0) {\includegraphics[width=2cm]{rooms.png}};
\node[below=0.3cm of rooms] (roomsLabel) [draw, fill=black, text=white, rounded corners] {Rooms};

\node (instructors) at (4, 0) {\includegraphics[width=2cm]{lecturer.png}};
\node[below=0.3cm of instructors] (instructorsLabel) [draw, fill=black, text=white, rounded corners] {Instructors};

\node (students) at (8, 0) {\includegraphics[width=2cm]{student.png}};
\node[below=0.3cm of students] (studentsLabel) [draw, fill=black, text=white, rounded corners] {Students};

\node (time) at (12, 0) {\includegraphics[width=2cm]{time.png}};
\node[below=0.3cm of time] (timeLabel) [draw, fill=black, text=white, rounded corners] {Time Slots};

% Bottom node: Courses (centered below instructors/students)
\node (courses) at ($(instructorsLabel)!0.5!(studentsLabel)-(0,4.5)$) {\includegraphics[width=2cm]{course.jpg}};
\node[below=0.3cm of courses] (coursesLabel) [draw, fill=black, text=white, rounded corners] {Courses};

% Central connection point
\coordinate (center) at ($(instructorsLabel)!0.5!(studentsLabel)-(0,2.25)$) {};

% Connection lines
\draw[thick] (roomsLabel) |- (center);
\draw[thick] (instructorsLabel) |- (center);
\draw[thick] (studentsLabel) |- (center);
\draw[thick] (timeLabel) |- (center);
\draw[thick] (center) -- (courses);

\end{tikzpicture}
\label{fig:opts}
  \caption{Timetabling Optimization Problem.}
\end{figure}
    
    
    These entities and their associated properties form the basis of the mathematical model presented in the following subsection.

    \subsection{The Mixed-Integer Programming (MIP) Formulation}\label{subsec:the-mixed-integer-programming-(mip)-formulation}

    We now translate the problem definition into a formal Mixed-Integer Programming (MIP) model.
    An MIP model consists of decision variables, an objective function to be optimised, and a set of linear constraints that define the feasible solution space~\cite{Wolsey1998, Nemhauser1999}.
    The formulation is presented in four parts: the objective function, the hard constraints that define feasibility, the linking constraints for model logic, and the variable domain definitions.

    \paragraph{\textbf{ Sets and Indices}}
    The following sets and indices are used to formulate the model:
    \begin{itemize}
        \item $c \in C$: Index for courses.
        \item $i \in I$: Index for instructors.
        \item $r \in R$: Index for rooms.
        \item $s \in S$: Index for student groups.
        \item $d \in D$: Index for days.
        \item $p \in P$: Index for time slots within a day.
    \end{itemize}

    \paragraph{Parameters}
    These are the input data defining a specific problem instance:
    \begin{itemize}
        \item \texttt{Size$_{c}$}: The number of students enrolled in course $c$.
        \item \texttt{Size$_{s}$}: The total number of students in student group $s$.
        \item \texttt{Cap$_{r}$}: The seating capacity of room $r$.
        \item \texttt{Teaches$_{ic}$}: A binary parameter; 1 if instructor $i$ teaches course $c$, 0 otherwise.
        \item \texttt{Enrolled$_{sc}$}: A binary parameter; 1 if student group $s$ is enrolled in course $c$, 0 otherwise.
        \item \texttt{I$_{special} \subset I$}: A subset of instructors who prefer a compact teaching schedule.
        \item \texttt{PrefCost$_{idp}$}: A numerical penalty associated with assigning instructor $i$ to teach on day $d$ in period $p$.
        \item \texttt{W$_{capacity}$}, \texttt{W$_{days}$}, \texttt{W$_{clash}$}, \texttt{W$_{pref}$}: Positive weights to control the trade-offs in the objective function.
    \end{itemize}

    \paragraph{Decision Variables}
    These are the unknown values the solver will determine:
    \begin{itemize}
        \item \texttt{$X_{cdrp} \in \{0, 1\}$}: The primary binary variable, where $X_{cdrp} = 1$ if course $c$ is scheduled in room $r$ on day $d$ during period $p$, and 0 otherwise.
        \item \texttt{$Y_{id} \in \{0, 1\}$}: An auxiliary binary variable, where $Y_{id} = 1$ if instructor $i$ is required to teach on day $d$, and 0 otherwise.
        \item \texttt{$Clash_{sdp} \ge 0$}: A non-negative integer variable that counts the number of courses \textit{in excess of one} assigned to student group $s$ on day $d$ at period $p$.
    \end{itemize}

    \paragraph{The Objective Function}
    The objective of the model is to minimize a total penalty score, $Z$, which is a weighted sum of four components representing different institutional goals.
    Each term in the function quantifies a specific type of ``cost'' or undesirability associated with a potential timetable.
    \begin{equation}
        \label{eq:objective}
        \begin{aligned}
            \min Z = &~ W_{\text{capacity}} \sum_{c,d,r,p} X_{cdrp} (Cap_r - Size_c) && \text{\small (Wasted Capacity)} \\
            + &~ W_{\text{days}} \sum_{i \in I_{\text{special}}} \sum_{d \in D} Y_{id} && \text{\small (Instructor Days)} \\
            + &~ W_{\text{clash}} \sum_{s,d,p} Clash_{sdp} \cdot Size_s && \text{\small (Student Clashes)} \\
            + &~ W_{\text{pref}} \sum_{c,d,r,p} X_{cdrp} \left( \sum_{i \in I} Teaches_{ic} \cdot PrefCost_{idp} \right) \quad && \text{\small (Preference Violations)}
        \end{aligned}
    \end{equation}
    The first term penalises inefficient room usage by summing the ``wasted space''.
    The second penalises the total number of days that designated instructors must be on campus.
    The third term minimises the total number of students affected by scheduling conflicts.
    The final term penalises deviations from instructor preferences by summing the preference costs of each scheduled class.

    \paragraph{Hard Constraints}
    The model is governed by a set of hard constraints, which are inviolable rules that define a feasible timetable.
    These must be satisfied by any valid solution.
    \begin{align}
        \sum_{d,r,p} X_{cdrp} &= 1, && \forall c \in C \label{con:assign} \\
        \sum_{c} (Teaches_{ic} \cdot X_{cdrp}) &\le 1, && \forall i \in I, d \in D, p \in P \label{con:instr_clash} \\
        \sum_{c} X_{cdrp} &\le 1, && \forall r \in R, d \in D, p \in P \label{con:room_clash} \\
        X_{cdrp} \cdot Size_c &\le Cap_r, && \forall c \in C, d \in D, r \in R, p \in P \label{con:capacity}
    \end{align}
    Constraint~\eqref{con:assign} ensures every course is scheduled exactly once.
    Constraints~\eqref{con:instr_clash} and~\eqref{con:room_clash} are standard clash constraints, preventing an instructor or a room from being assigned to more than one course simultaneously.
    Constraint~\eqref{con:capacity} enforces room capacity limits.

    \paragraph{Linking Constraints}
    These are technical constraints that enforce logical relationships between decision variables, primarily to correctly calculate the soft penalty costs in the objective function.
    \begin{align}
        \sum_{c,r} (Enrolled_{sc} \cdot X_{cdrp}) - 1 &\le Clash_{sdp}, && \forall s \in S, d \in D, p \in P \label{con:clash_calc} \\
        \sum_{c,r,p} (Teaches_{ic} \cdot X_{cdrp}) &\le |P| \cdot Y_{id}, && \forall i \in I_{\text{special}}, d \in D \label{con:day_link}
    \end{align}
    Constraint~\eqref{con:clash_calc} defines the student clash variable; if a student group $s$ is assigned to $k$ courses at a given time, the summation equals $k$, and $Clash_{sdp}$ must be at least $k-1$.
    Constraint~\eqref{con:day_link} is a ``big-M'' constraint that links course assignments to instructor presence, where $|P|$ is the number of periods in a day, ensuring $Y_{id}$ is forced to 1 if instructor $i$ has any classes on day $d$.

    \paragraph{Variable Domains}
    Finally, the domains of the decision variables are defined as follows, restricting them to be binary or non-negative integers.
    \begin{align*}
        X_{cdrp} &\in \{0, 1\}, && \forall c \in C, d \in D, r \in R, p \in P \\
        Y_{id} &\in \{0, 1\}, && \forall i \in I, d \in D \\
        Clash_{sdp} &\ge 0 \text{ and Integer}, && \forall s \in S, d \in D, p \in P
    \end{align*}


    \section{Implementation with Open-Source Tools}\label{sec:implementation}

    While the mathematical formulation presented in Section~\ref{sec:model} provides a complete and abstract representation of the timetabling problem, its practical value depends on our ability to implement and solve it.
    This section provides a guide for translating the MIP model into a functional software tool using exclusively open-source technologies.
    The goal is to demonstrate that a powerful optimisation system can be built without relying on expensive commercial licenses, making it accessible to a wider range of institutions.
    We focus on a solution architecture based on a single, well-structured Python script, which is sufficient for solving the problem and can serve as a foundation for more complex applications.

    \subsection{The Proposed Technology Stack}\label{subsec:the-proposed-technology-stack}

    The cornerstone of our implementation is the Python programming language.
    Its simple syntax, extensive standard library, and a rich ecosystem of third-party packages make it an ideal choice for scientific computing and optimization.
    Specifically, we leverage the \code{Pandas} library for efficient data manipulation, which is essential for reading and preprocessing the input data files that define the timetabling instance.\\

    To formulate and solve the mathematical model, we utilize \code{PuLP}, a popular open-source Python library that acts as a modeler~\cite{PuLP2011}. \code{PuLP} allows a user to define decision variables, constraints, and an objective function using Python syntax that closely mirrors the mathematical notation.
    It then acts as an interface to an underlying MIP solver, which is the computational engine that performs the optimization.
    For this implementation, we propose using the COIN-OR Branch and Cut (CBC) solver, a robust and high-performance open-source MIP solver that is seamlessly integrated with \code{PuLP}.
    This combination of Python, Pandas, and PuLP with CBC provides a complete, powerful, and freely available toolchain for solving the UCTP.

    \subsection{Structuring Input Data}\label{subsec:structuring-input-data}

    A well-defined data structure is critical for the successful implementation of the MIP model.
    The parameters of the model must be provided in a clean, machine-readable format.
    We recommend using Comma-Separated Values (CSV) files, as they are simple, human-readable, and can be easily created and edited with standard spreadsheet software.
    This approach decouples the data from the model's logic, allowing administrators to update timetabling requirements without modifying the Python source code.
    The following five CSV files are proposed to represent all necessary input parameters for the model.

    \paragraph{1. courses.csv}
    This file is the master list of all courses to be scheduled.
    Each row represents a unique course.
    \begin{itemize}
        \item \code{CourseID}: A unique identifier for each course $c \in C$.
        \item \code{InstructorID}: The identifier for the instructor $i \in I$ who teaches this course.
        This column is used to establish the \texttt{Teaches$_{ic}$} parameter.
        \item \code{Size}: An integer representing the number of students enrolled in the course, corresponding to the \texttt{Size$_{c}$} parameter.
    \end{itemize}

    \paragraph{2. instructors.csv}
    This file provides details about the instructors.
    Each row corresponds to a unique instructor.
    \begin{itemize}
        \item \code{InstructorID}: A unique identifier for each instructor $i \in I$.
        \item \code{IsSpecial}: A binary value (1 or 0) indicating if the instructor belongs to the subset \texttt{I$_{special}$}, for whom a compact schedule is preferred.
    \end{itemize}

    \paragraph{3. rooms.csv}
    This file lists all available physical locations for scheduling classes.
    Each row represents a single room.
    \begin{itemize}
        \item \code{RoomID}: A unique identifier for each room $r \in R$.
        \item \code{Capacity}: An integer representing the seating capacity of the room, corresponding to the \texttt{Cap$_{r}$} parameter.
    \end{itemize}

    \paragraph{4. student\_groups.csv}
    This file defines the student cohorts and their sizes.
    Each row represents a unique group of students.
    \begin{itemize}
        \item \code{GroupID}: A unique identifier for each student group $s \in S$.
        \item \code{GroupSize}: An integer representing the total number of students in the group, corresponding to the \texttt{Size$_{s}$} parameter.
    \end{itemize}

    \paragraph{5. enrollments.csv}
    This file defines the many-to-many relationship between student groups and courses, establishing the \texttt{Enrolled$_{sc}$} parameter.
    Each row represents a single group's enrollment in a single course.
    \begin{itemize}
        \item \code{GroupID}: The identifier for the student group $s$.
        \item \code{CourseID}: The identifier for the course $c$ in which the group is enrolled.
    \end{itemize}

    \paragraph{6. preferences.csv}
    This file quantifies instructor preferences for teaching slots, defining the \texttt{PrefCost$_{idp}$} parameter.
    Each row specifies the cost for an instructor to teach in a particular time slot.
    The absence of an entry for a specific slot can be interpreted as a default high-cost penalty.
    \begin{itemize}
        \item \code{InstructorID}: The identifier for the instructor $i$.
        \item \code{Day}: The day of the week (e.g., `Monday', `Tuesday'), corresponding to an element $d \in D$.
        \item \code{TimeSlot}: The period of the day (e.g., `1' for 7-10am, `2' for 10-1pm), corresponding to an element $p \in P$.
        \item \code{Cost}: A numerical value representing the penalty cost for that assignment.
    \end{itemize}
    This modular file structure ensures that the data is organized logically, easy to manage, and can be loaded efficiently into Pandas DataFrames at the start of the solution process.

    \subsection{Solution Architecture and Workflow}\label{subsec:solution-architecture-and-workflow}

    The proposed solution architecture is designed for simplicity and reproducibility, centred around a single Python script.
    This approach avoids the complexity of setting up a larger application, making it straightforward for users with basic Python knowledge to run the optimisation.
    The workflow is executed sequentially within the script and can be broken down into four distinct phases: data ingestion, model formulation, solving, and results processing.

    \paragraph{Phase 1: Data Ingestion and Preprocessing}
    The process begins by loading the input data from the CSV files into Pandas DataFrames.
    This phase is critical for data validation and for transforming the raw data into Python data structures (primarily dictionaries and lists) that map directly to the MIP model's parameters.
    \begin{lstlisting}[caption={Loading CSV data and creating a parameter dictionary.},label={lst:data}]
import pandas as pd
# Load data from CSV files
courses_df = pd.read_csv('courses.csv')
rooms_df = pd.read_csv('rooms.csv')
# ... load other files ...

# Create a parameter dictionary for room capacities
# e.g., {'R101': 50, 'R102': 30}
cap_r = dict(zip(rooms_df['RoomID'], rooms_df['Capacity']))
    \end{lstlisting}

    \paragraph{Phase 2: MIP Model Formulation}
    With the data prepared, the script builds the MIP model programmatically using the \code{PuLP} library.
    This involves a direct translation of the mathematical formulation from Section~\ref{sec:model} into Python code.
    The decision variables are created first, as shown in Listing~\ref{lst:vars}.
    
% \begin{mintedbox}{python}
%if transactions: Transaction.create_transactions() # if transactions = "true"
%node.generate_emptyState() # empty state for all nodes
%S.initial_events() # initiate initial events to start with
%
%while not queue.isEmpty() and clock <= targetTime:
%      next_e = queue.get_next_event()
%      clock = next_e.time # move clock to the time of the event
%      Event.execute_event(next_e)
%      Queue.remove_event(next_e)
%
%print results
%\end{mintedbox}
 
 \begin{lstlisting}[caption={Defining decision variables in PuLP.},label={lst:vars}]
from pulp import LpProblem, LpMinimize, LpVariable, LpBinary

# Initialize the model
model = LpProblem("UCTP", LpMinimize)

# X_cdrp: 1 if course c is in room r on day d at period p
C = courses_df['CourseID'].tolist()
D = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri']
R = rooms_df['RoomID'].tolist()
P = [1, 2, 3, 4]

x = LpVariable.dicts("X", (C, D, R, P), cat=LpBinary)
    \end{lstlisting}
    Following variable creation, the objective function and all constraints from (\ref{con:assign}) to~\eqref{con:day_link} are added to the model object.
    For instance, the instructor clash constraint (\ref{con:instr_clash}) is implemented by iterating through each instructor and time slot and summing the relevant \code{x} variables, as shown in Listing~\ref{lst:constraint}.
    \begin{lstlisting}[caption={Adding an instructor clash constraint to the model.},label={lst:constraint}]
# Constraint (2): An instructor cannot teach more than one course at a time
for i in I:
    for d in D:
        for p in P:
            model += lpSum(x[c][d][r][p] * teaches_ic.get((i, c), 0)
                           for c in C for r in R) <= 1
    \end{lstlisting}

    \paragraph{Phase 3: Solving the Model}
    Once the model is fully formulated, a single command invokes the solver. \code{PuLP} passes the model to the underlying CBC solver, which employs optimization algorithms like branch-and-cut to find an optimal integer solution.
    \begin{lstlisting}[caption={Solving the formulated MIP model.},label={lst:solve}]
# Solve the problem (uses CBC by default)
model.solve()
# Check the status (1 means Optimal)
if model.status == 1:
    print("Optimal solution found!")
    \end{lstlisting}

    \paragraph{Phase 4: Results Processing}
    If an optimal solution is found, the final phase is to extract and interpret the results.
    The script iterates through the \code{x} variables and identifies which have a value of 1.
    Each such variable represents a successful assignment, which is then stored.

    \subsection{Code Repository and Accessibility}\label{subsec:code-repository-and-accessibility}

    To ensure full reproducibility and encourage collaboration, the complete Python script, along with a set of sample CSV data files, is made publicly available in a GitHub repository.
    This allows other researchers and practitioners to easily download, inspect, and run the model on their own systems.
    The repository can be accessed at:
    \begin{center}
        \url{https://github.com/kikwaib/uctp-mip.git}
    \end{center}

    \subsection{Generating the Final Timetable}\label{subsec:generating-the-final-timetable}

    The raw output from the solver is a set of variable assignments.
    The final step in the workflow is to transform this data into a human-readable format.
    The script collects all the successful assignments (where $X_{cdrp} = 1$) into a Pandas DataFrame.
    This structured format is ideal for analysis and can be easily exported.
    The primary output is a CSV file named \code{timetable\_solution.csv}, containing columns for \code{Day}, \code{TimeSlot}, \code{CourseID}, \code{InstructorID}, and \code{RoomID}.
    This format is universally accessible and can be imported into spreadsheet software for further filtering or formatting.
    For official dissemination, this CSV file can also be used as a data source to automatically generate a more polished PDF report using libraries like \code{ReportLab} or by converting it through a LaTeX template.


    \section{Discussion: Limitations of the MIP Approach}
    \label{sec:limitations}

    While the MIP model presented in this paper provides a powerful and rigorous framework for finding high-quality, provably optimal timetables, it is essential to acknowledge its inherent limitations.
    These challenges primarily relate to computational complexity and the practicalities of solving large-scale, real-world instances.
    Understanding these drawbacks is crucial for determining when the MIP approach is most suitable and when alternative solution strategies should be considered.

    \subsection{The Challenge of Computational Complexity and Scalability}\label{subsec:the-challenge-of-computational-complexity-and-scalability}

    The primary limitation of any MIP-based approach to the UCTP is its computational complexity.
    The problem belongs to the class of NP-hard problems, as established by early research in the field~\cite{Even1976, Cooper1996}.
    This means that the time required to find a guaranteed optimal solution can grow exponentially as the size of the problem increases.
    The scale of this challenge becomes apparent when considering the number of binary variables in our model.
    The main decision variable, \texttt{$X_{cdrp}$}, has a size of $|C| \times |D| \times |R| \times |P|$.
    For even a medium-sized department with 100 courses, 5 days, 4 time slots, and 15 rooms, the number of these binary variables would be $100 \times 5 \times 4 \times 15 = 30,000$.
    The theoretical search space is therefore on the order of $2^{30,000}$, a number of astronomical proportions.\\

    Although modern MIP solvers use sophisticated algorithms like the branch-and-cut method to intelligently prune this search space, the combinatorial explosion remains a fundamental barrier.
    For large universities or departments with highly flexible curricula, the model can become computationally intractable, meaning that a solver may be unable to find an optimal solution—or even a good feasible one—within a practical timeframe of several hours.
    This trade-off between solution quality (optimality) and computation time is the central challenge of using exact methods for the UCTP.

    \subsection{Practical Considerations for Large and Complex Problems}\label{subsec:practical-considerations-for-large-and-complex-problems}

    The scalability challenges of MIP necessitate a pragmatic approach for institutions dealing with very large problem instances or those requiring rapid, iterative planning.
    In such scenarios, the quest for a mathematically perfect solution may be less important than the ability to generate a high-quality, feasible timetable quickly.
    This is where alternative solution paradigms, particularly metaheuristics, become highly relevant.
    As surveyed by~\cite{Lewis2008} and~\cite{Blum2003}, methods like genetic algorithms, tabu search, and simulated annealing are designed to navigate vast solution spaces efficiently.
    They sacrifice the guarantee of optimality in exchange for speed and flexibility, making them well-suited for tactical ``what-if'' analyses or for finding an initial, good-enough solution that can be manually refined.

    Furthermore, the practical utility of a perfectly optimal solution depends on the quality of the input data.
    In a real-world university setting, data is rarely perfect; student enrolment numbers can fluctuate, and instructor preferences may be qualitative or subject to change~\cite{Wren1996}.
    An MIP model will produce a solution that is optimal only with respect to the given data.
    If the data is imperfect, the resulting ``optimal'' timetable may not be truly optimal in practice.
    Consequently, a fast heuristic that can quickly generate multiple good scenarios based on slightly different data inputs may be more valuable for decision-making than a slow, exact method tied to a single, rigid dataset.
    Therefore, the choice between MIP and other methods is not merely technical but strategic, depending on an institution's size, planning cycle, and tolerance for sub-optimality.


    \section{Conclusion}
    \label{sec:conclusion}

    \subsection{Summary of Work}\label{subsec:summary-of-work}

    This paper has presented a comprehensive treatment of the University Course Timetabling Problem (UCTP) through the lens of Mixed-Integer Programming.
    We began by formally defining the UCTP as a multi-dimensional assignment problem and proceeded to develop a flexible and detailed MIP model.
    A key contribution of this formulation is its ability to balance multiple, often competing, institutional objectives—including student conflict minimisation, instructor satisfaction, and efficient resource utilisation—through a weighted, single-objective function.
    This approach provides administrators with the ability to tune the model according to their specific priorities.\\

    Furthermore, we have demonstrated a practical and accessible implementation path for this model.
    By leveraging the Python programming language, along with open-source libraries such as Pandas and PuLP, we have outlined a complete workflow from data ingestion to final timetable generation.
    This implementation strategy, centred on a single, well-documented script and clearly structured data files, underscores that powerful optimisation techniques are not exclusively the domain of commercial software.
    We have shown that a robust, verifiable, and high-quality timetabling solution can be achieved with freely available tools, making this approach applicable to a wide range of academic institutions.

    \subsection{Avenues for Further Research}\label{subsec:avenues-for-further-research}

    Despite the strengths of the MIP approach, its inherent computational limitations open up several promising avenues for further research.
    One of the most practical directions is the development of hybrid solution methodologies.
    For instance, a two-stage approach could use a metaheuristic algorithm to quickly find an initial, high-quality feasible solution, which could then be used to warm-start an MIP solver, significantly reducing the search space and solution time.
    Alternatively, decomposition techniques, such as Benders or Dantzig-Wolfe decomposition, could be explored to break the large monolithic model into smaller, more manageable subproblems that can be solved more efficiently.\\

    Another area for future work lies in enhancing the model's fidelity to real-world complexities.
    The current model could be extended to include more nuanced constraints, such as minimising the travel time for students and instructors between consecutive classes, ensuring fairness in the allocation of ``prime'' teaching slots, or accommodating more complex pedagogical rules (e.g., linked lab and lecture sessions).
    Additionally, developing a user-friendly graphical interface, perhaps using a web framework like Streamlit or FastAPI, would make the tool accessible to non-technical administrators, allowing them to adjust parameters, run the model, and visualise results without interacting directly with the code.
    Finally, a comparative study benchmarking the performance of this MIP model against various state-of-the-art metaheuristics on a standardised set of UCTP instances would provide valuable insights into the trade-offs between solution quality and computational effort for different problem types.

    \bibliographystyle{alpha}
    \bibliography{references}

\end{document}