\documentclass{crorr}
%%%%% journal  info -- DO NOT CHANGE %%%%%%%%%
\setcounter{page}{1}
\renewcommand\thisnumber{x}
\renewcommand\thisyear {201x}
\renewcommand\thisvolume{x}
\renewcommand\datereceived{xx xx, 201x}
\renewcommand\dateaccepted{yy yy, 201x}
\renewcommand\dateavailable{zz zz, 201x}
%%%%%%%%   end journal info   %%%%%%%%%%%%%


%%%%% author macros %%%%%%%%%
% place your own macros HERE
\usepackage{algorithmic}
%\renewcommand{\algorithmicrequire}{\textbf{Ulaz:}}
%\renewcommand{\algorithmicensure}{\textbf{Izlaz:}}
\renewcommand{\algorithmiccomment}[1]{// {\sf  #1}}
%\newcommand{\eqref}[1]{(\ref{#1})}
%%%%% end %%%%%%%%%

%%%%%%%%%    already loaded packages -- DO NOT RELOAD  %%%%%
% \usepackage{amssymb}
% \usepackage{amsmath,amsthm}
% \usepackage{latexsym}
% \usepackage{amsfonts}
% \usepackage{amsbsyt}
% \usepackage{graphicx}
%%%%%%    end   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\markboth{An Integer Programming Model for Assigning Students to Elective Courses}{An Integer Programming Model for Assigning Students to Elective Courses}

\title{An Integer Programming Model for Assigning Students to Elective Courses}


%%%%% Begin Abstract %%%%%%%%%%%
\begin{abstract}
This paper deals with the problem of assigning students to elective courses according to their preferences. In the process of assigning students to the elective courses according to their preferences, academic institutions commonly deal with many obstacles, the most typical being a limited number of students who can be assigned to any particular class. Also, due to financial or technical reasons, it is possible that the maximum number of the elective courses is determined in advance, so that the institution has to make the decision which courses to carry out. Therefore, it is not realistic to expect that all the students will be assigned to the courses which are their first choices (perfect satisfaction). 

This paper presents an integer programming model which maximizes total student satisfaction subject to the number of different constraints. The measure of the student satisfaction is based on students' order of preference according to the principle:{\em the higher choice met – the higher satisfaction obtained}. Following the basic model, several versions of the models are generated for covering possible real-life situations, taking into consideration the way the student satisfaction is measured, as well as the academic institution's preferences within the possible technical and financial constraints.  The main contribution of the paper is introducing the concept of the minimal student satisfaction level which will reduce the number of students who are dissatisfied  with the  courses they were assigned to. 
\end{abstract}
%%%%% end %%%%%%%%%%%

%%%%% Keywords %%%%%%%%%%%
\keywords{Integer Programming, Multi-unit assignment, Elective Courses}

%%%% maketitle %%%%%

\maketitle

%%%% Start %%%%%%
\bigskip 
\noindent

%TODO zamijenjeni uvjeti u2 i u3 u odnosu na original
\section{Introduction}

This paper deals with the problem of assigning students to elective courses at an academic institution in Croatia with the following characteristics: 
\begin{itemize}
\item	The institution offers a wide range of elective courses which are divided into modules which consist of equal number of courses (one course can be part of only one module). In the remaining text we will use term course instead of module.  
\item	Every student has to be enrolled in the $K$  courses.
\item	The timetable is devised after the assignment process.
\item	The number of students is relatively small ($<200$).
\end{itemize}

Due to the needs and requirements of business, it is not possible to carry out all the potential courses. In resolving the question so as to which of them will be cancelled, we have to define the appropriate electoral system. Previously, the standard two-round system was used:  
\begin{itemize}
\item	Student selects $K$ courses. 
\item	Upon completion of the selecting process, the data are collected. The courses are divided into the two sets: $C_I$ - courses with insufficient number of interested students and $C_S$ - courses with sufficient number of interested students. All the courses from set $C_I$ are omitted from further process. 
\item	All the students who selected any of the courses from $C_I$, now have to replace previously selected courses from $C_I$ with the courses from $C_S$.
\end{itemize}
Presented system has many obstacles: it is time-consuming, number of students enrolled in the courses they did not select in the first round is relatively high, and students tend to select the popular instead of the desired courses which causes restriction in the offer of elective courses.
 
The new system consists of the following steps:
\begin{itemize}
	\item	Student selects and ranks $L$ preferable courses ($L > K$). 
	\item	Upon completion of the selecting process, the data are summarised. According to the solution of the integer programming model, students are assigned to the courses from the list of their preferable courses. 
	\item	All the students who are not assigned to the $K$ of their preferable courses choose remaining courses in agreement with the faculty administration.
\end{itemize}
In the new system, a student can select more courses in which they are interested and the probability that a student is enrolled in less than $K$ preferable course is reduced.  Integer programming models are constructed with regard to the student’s choices and business needs and demands. The solution of the model is obtained by maximizing total student satisfaction which depends on the courses student is enrolled in. In general, greater student satisfaction is achieved when the students are enrolled in the courses which are their first choices. Important constraint in the models is minimal student satisfaction which guarantee, if it is possible, that student is assigned to the courses that are higher on the list of preferable courses.

The techniques of integer programming \cite{chen_applied_2010,hillier_introduction_2001,kaufmann_integer_1977,albright_data_2011} (for other techniques see surveys \cite{schaerf_survey_1999,carter_recent_1997}) are used to develop the models presented in this paper because the problem is relatively small (number of variables in the model is smaller then 1000). There are many papers that use integer programming to generate efficient solutions for a wide range of university timetable problems  \cite{daskalaki_integer_2004,kristiansen_elective_2011,muhlenthaler_fairness_2014,rudova_university_2003,badri_multi-objective_1998}, but they are primarily concerned with maximizing students' satisfaction with the timetable of elective courses already enrolled. Instead, we have developed models which don't take care about timetable but  assign students to the elective courses with respect to their choices and  business needs and requirements.  A problem, very similar to the problem observed in this paper, is described in \cite{sampson_class_1995}. In \cite{sampson_class_1995}, authors deal with the problem of assigning elective courses taking into consideration both, student preferences and timetable constraints imposed by the faculty administration. The solution of the problem is given by using heuristic approach because the developed integer programming model is impractical. In comparison to the  model presented in \cite{sampson_class_1995}, our models have not timetable constraints, but  the constraints on minimal student satisfaction are included. 
 
 

\section{Assigning Students to Elective Courses}

In the previous section one-round electoral system was described. In the next two subsections two types of models which support electoral system are described. The first type includes the models which presume that all the courses are enrolled by only one group of students. The second type includes the models which allow additional constraints, i.e. the courses can either be enrolled by one or more groups of students or minimal level of student satisfaction has to be achieved.  Finally, in section 3 an algorithm for assigning students that can be used if the models presented in section 2 have no solution is presented.  

\subsection{The basic model}

We observe the problem of assigning students to elective courses which arise when students have to enrol in several elective courses. The assigning process has to satisfy conditions which arise from both academic and business requirements:  
\begin{itemize}
	\item[U1] - Student can select $L$ courses. The courses are referenced as \textit{preferable courses}.
	%
	\item[U2] - Student has to rank preferable courses. After the ranking, maximum weight $L$ is given  to the first course, weight $L-1$ is given to the second one, and so on. The weights are referenced as {\em coefficient of satisfaction}.  
	%
	\item[U3] - Student will be assigned to $K$ courses from the list of $L$ preferable courses, where  $K<L$.  The sum of student's coefficients of satisfaction on the assigned courses is named {\em student's satisfaction}. 
	%
	\item[U4] - For every course there is maximum number of students that can be enrolled. 
	%
	\item[U5] - For every course there is also minimum number of students that have to be enrolled. %This condition is primarily from business reason.
\end{itemize}

The measure for goodness of particular assignment is total sum of students' satisfaction.  

For the sake of simplicity, we observe only the case when all the students have to be enrolled in the same number of elective courses and can choose the same number of preferable courses. 

To describe a mathematical model which satisfies conditions U1--U5, we define parameters and variables presented in the model.
\begin{definition} \label{def:01} The parameters  in the mathematical model for assigning students are
\begin{itemize}
	\item $K$ is a number of courses that student has to be enrolled in.
	\item $L$ is a number of preferable courses student can select.  
	\item Set $S=\{S_1, S_2, \ldots, S_M\}$ is set of all students. Set $S$ has total of  $M$ elements. 
	%
	\item Set $P=\{P_1, P_2, \ldots, P_N\}$ is set of all offered courses. Set $P$ has total of $N$ elements.
	%
	\item For every course $P_j$, $j=1,\ldots,N$, $\mathit{M\!\!P}_j$ denotes maximal number of the students that can be enrolled in $P_j$. Similarly, $\mathit{m\!P}_j$ denotes minimal number of the students that can be enrolled in $P_j$.
	%
	\item Parameters $a_{ij}$ are indicators of the preferable courses. If the student $S_i$ prefer course $P_j$ then  $a_{ij}=1$, otherwise $a_{ij}=0$. Definition of  $a_{ij}$ ensure that condition U1 is satisfied. 
	%
	\item Parameters $c_{ij}$ are coefficient of satisfaction and denotes which value student $S_i$ gives to course $P_j$.  If the course $P_j$ is not between preferable courses of student $S_i$, then $c_{ij}=0$. Definition of  $c_{ij}$ ensure that condition U2 is satisfied. 
	%
\end{itemize}
Variables in the model are binary variables $x_{ij}$, $i=1,\ldots,M$, $j=1,\ldots,N$,  which denotes is the student $S_i$ is assigned to the course $P_j$ ($x_{ij}=1$) or not ($x_{ij}=0$).

\end{definition}   
	
All parameters from Definition \ref{def:01} are known before students selection of preferable courses ($K$, $L$, $S$, $P$) or immediately after ($a_{ij}$, $c_{ij}$). 

%\end{itemize}
%
The next proposition will be used to explain how conditions U3--U5 are mathematically expressed.
\begin{proposition} \label{prop:01} For the parameters and variables from Definition \ref{def:01}, following statements are valid:
	\begin{enumerate}
		\item Number of courses where student $S_i$ is assigned: $\displaystyle \sum_{j=1}^N a_{ij} x_{ij}$.
		\item Student's satisfaction for student $S_i$:  $\displaystyle \sum_{j=1}^N c_{ij} x_{ij}$.
		\item Number of students who prefer course $P_j$: $\displaystyle \sum_{i=1}^M a_{ij}$.
		\item Number of students assigned to the course $P_j$:  $\displaystyle \sum_{i=1}^M a_{ij} x_{ij}$.
		\item Sum of coefficients of student's satisfaction for all students assigned to the course $P_j$: $\displaystyle \sum_{i=1}^M c_{ij} x_{ij}$.
	\end{enumerate}
\end{proposition}
\begin{proof}
We will prove only the first statement. From the definition of the variables $x_{ij}$ it is obvious that number of courses the student $S_i$ is assigned to is defined by $ \sum_{j=1}^N x_{ij}$. But, $S_i$ can be assigned only to preferable courses, i.e. $x_{ij}$ can be $1$ only when $a_{ij}$ is also equal to 1, so we obtain
\[
\sum_{j=1}^N x_{ij}=\sum_{j=1, a_{ij}=1}^N x_{ij}=\sum_{j=1}^N a_{ij} x_{ij}.
\]  
\end{proof}

From Proposition \ref{prop:01},  the condition U3 can be expressed as 
\begin{equation} 
\sum_{j=1}^N  a_{ij} x_{ij}=K, \quad i=1,\ldots,M.  \label{uvjet:studenti22}
\end{equation}
Unfortunately, condition U3 in real situation can be impracticable because there is a possibility that a student chooses at least $L-K+1$ courses where number of interested students is smaller than minimal number of students that have to be enrolled in the course.% $\mathit{m\!P}_j$. 
Hence, condition U3 is replaced by  
 \begin{itemize}
 	\item[U3'] - Student will be assigned to at most $K$ courses from the list of preferable courses,
 \end{itemize}
that can be expressed as
\begin{equation}
\sum_{j=1}^N  a_{ij} x_{ij}\leq K, \quad i=1,\ldots,M.  \label{uvjet:studenti}
\end{equation}
 In practice it means that students who are not assigned to $K$ courses from list of preferable courses will be assigned to another course after the meeting with faculty administration. 

Similarly, we realize conditions U4 and U5. From Proposition \ref{prop:01} it follows that condition U4 is given by
\begin{equation}
\sum_{i=1}^M  a_{ij} x_{ij}\leq M\!\!P_j, \quad j=1,\ldots,N  \label{uvjet:predmetiMax}, 
\end{equation}
and the condition U5 is given by
\begin{equation}
\sum_{i=1}^M  a_{ij} x_{ij}\geq m\!P_j, \quad j=1,\ldots,N.  \label{uvjet:predmetiMin} 
\end{equation}

The goal function is maximization of the total sum of students' satisfaction. According to Proposition \ref{prop:01}, that sum is given by

\begin{equation}
	\sum_{i=1}^M \sum_{j=1}^N c_{ij}x_{ij}
\end{equation} 

Now we can formulate basic model for assigning students to elective courses as a problem of integer programming where total sum of students' satisfaction is maximized subject to (\ref{uvjet:studenti}--\ref{uvjet:predmetiMin}):

\[
(P\!R) \quad
\left\{ \quad
\begin{array}{l}
\displaystyle \sum_{i=1}^M \sum_{j=1}^N c_{ij}x_{ij} \to \max \\
\displaystyle \sum_{j=1}^N a_{ij}x_{ij} \leq K, \quad i=1, \ldots, M; \\
\displaystyle \sum_{i=1}^M a_{ij}x_{ij} \leq \mathit{M\!\!P}_j, \quad j=1, \ldots, N; \\ 
\displaystyle \sum_{i=1}^M a_{ij}x_{ij} \geq \mathit{m\!P}_j, \quad j=1, \ldots, N; \\ 
\displaystyle x_{ij}=0\hbox{ or }1, \ i=1,\ldots,M,\ j=1,\ldots,N. \label{uvjet:binarno}
\end{array}
\right.
\]
For the sake of simplicity, the formulation of problem (PR) is given as a problem with  $M \cdot N$ variables, but number of variables in the problem is only $M \cdot L$. 

\subsection{The models with additional conditions}

Model (PR) is a basic model for assigning students to the elective courses. It is the appropriate model in the case when every course enrols only one group of students, but if there are courses which can enrol more than one group we have to expand the model with additional conditions. Actually, we observe three types of conditions:

\begin{itemize} 
    \item[U6] - Number of groups is limited. The students enrolled in particular course can be divided  in one or more groups.
	%
	\item[U7] - Student's satisfaction has to be higher than any arbitrary constant. We refer to this condition as a \textit{minimal satisfaction condition}. 
	The term \textit{dissatisfied student} means that minimal satisfaction condition is not met for the student.
	%
	\item[U8] - Average satisfaction of students assigned to the course has to be higher than any arbitrary constant.	
\end{itemize}

From the business point of view, the group is the basic unit of costs. The group requires a classroom (with limited capacity) and a teacher, so it is necessary to restrict number of classes in order to cut expenses. A typical problem with groups is the case when number of enrolled students is slightly higher than maximal number of students that can be in one group so faculty administration have to make a decision on having one or two groups for the course. For example: maximum number of students in one group is 20 and 24 students are enrolled in the course. Is it better to form two small groups or to  transfer four students to other courses?


Before further analysis of previously mentioned conditions, we define additional parameters and variables.
\begin{definition} \label{def:02}The parameters required for analysis conditions U6--U8 are:
\begin{itemize}
\item $r_j$ - maximal number of groups in which the course $P_j$ can be taught. $r_j$ can be zero.
\item $g_j$ - upper bound for number of students enrolled in one group for the course $P_j$. For $k$ groups, upper bound is $m\!P_j^k=k\cdot g_j$.
\item $ m\!P_j^k$ - lower bound for number of  students enrolled in course $P_j$ required to taught  $P_j$ into $k$ groups. Note that $m\!P_j^1=m\!P_j$.
\item $G$ - maximal total number of groups.
\item  $B^S$ -  minimal students satisfaction.
\item $B^C$ - minimal average satisfaction on the courses.
\end{itemize}
Binary variables $y_{jk}$, $j=1,\ldots, N$, $k=1,\ldots,r_j$, are used to describe number of groups for the specific course. If the course $P_j$ is taught in to $k$ groups, then $y_{jk}=1$, otherwise $y_{jk}=0$. 
\end{definition}

From the Definition \ref{def:02} is easy to see that 
\begin{equation}
y_{j1}+y_{j2}+\cdots + y_{j k_j} \leq 1,\ j=1,\ldots,N. \label{uvjet:GrupaPredmet}
\end{equation}
If $y_{j1}+y_{j2}+\cdots + y_{j k_j}=0$, then all variables $y_{j1},y_{j2},\ldots, y_{j k_j}$ are zero and there is no students assigned to the course $P_j$.

\begin{proposition} \label{prop:02}
	The course $P_j$ is taught into $k$ groups if and only if $\sum_{l=1}^{r_j} l\, y_{jl} = k$
\end{proposition}
\begin{proof}
	If the course $P_j$ is taught into $k$ groups, then $y_{jk}=1$, and other $y_{jl}$ are zero and therefore is $\sum_{l=1}^{r_j} l\, y_{jl} = k y_{jk}=k$. On the other hand, if
	$\sum_{l=1}^{r_j} l\, y_{jl} = k$, from \eqref{uvjet:GrupaPredmet} follows that only $y_{jk}$ can be one, so the course $P_j$ is taught into $k$ groups.
\end{proof}

In the model (PR) conditions U4 and U5 are given by (\ref{uvjet:predmetiMax}) and (\ref{uvjet:predmetiMin}), but that conditions are not suitable for the situation where course can be taught in  more than one group, so we have to replace (\ref{uvjet:predmetiMax}) and (\ref{uvjet:predmetiMin}) with more appropriate conditions.
 
If the number of students enrolled in the course $P_j$ is suitable for $k$ groups then that number has to be between corresponding lower and upper bounds:
\begin{equation}
	 m\!P_j^k \leq \sum_{i=1}^M  a_{ij} x_{ij}   \leq k\,g_j. \label{uvjet:grupeIzmedju}
\end{equation}  
Using definition of $y_{jk}$ and Proposition \ref{prop:02}, \eqref{uvjet:grupeIzmedju} can be written as
\begin{equation}
	\sum_{l=1}^{r_j} y_{jl} m\!P_j^l \leq \sum_{i=1}^M  a_{ij} x_{ij} \leq \sum_{l=1}^{r_j}  l\, y_{jl} \,g_j \label{uvjet:grupeIzmedju2},
\end{equation} 
and we can replace (\ref{uvjet:predmetiMax}) with
\begin{equation} \label{uvjet:GrupeMaxB}
	\sum_{i=1}^M  a_{ij} x_{ij} - \sum_{l=1}^{r_j}  l\, y_{jl} \,g_j \leq 0,\quad j=1,\ldots, N,
\end{equation}
and (\ref{uvjet:predmetiMin})
\begin{equation} \label{uvjeti:GrupeMinB}
	\sum_{i=1}^M  a_{ij} x_{ij}-\sum_{l=1}^{r_j} y_{jl} m\!P_j^l \geq 0, \quad j=1,\ldots, N.
\end{equation}

According to Proposition \ref{prop:02},  total number of groups is $\sum_{j=1}^N \sum_{l=1}^{r_j} l\, y_{jl}$, so the condition U6 is given by
\begin{equation} \label{uvjet:brojGrupa}
\sum_{j=1}^N \sum_{l=1}^{r_j} l\, y_{jl} \leq G.
\end{equation}

Finally, we define model (PRG) as a model for assigning students to a limited number of groups that satisfy conditions U1--U6. 
\begin{eqnarray*}
(P\!RG) 
\left\{
\begin{array}{l}
\displaystyle \sum_{i=1}^M \sum_{j=1}^N c_{ij}x_{ij} \to \max \\
\displaystyle \sum_{j=1}^N a_{ij}x_{ij} \leq K, \quad i=1, \ldots, M; \\
\displaystyle \sum_{i=1}^M a_{ij} x_{ij} - \sum_{l=1}^{r_j} l y_{jl} g_j\leq 0, \ j=1,\ldots,N, \\
\displaystyle \sum_{i=1}^M a_{ij} x_{ij} - \sum_{l=1}^{r_j}  y_{jl} m\!P_j^l\geq 0, \ j=1,\ldots,N, \\
\displaystyle \sum_{j=1}^N  \sum_{l=1}^{r_j} l\, y_{jl} \leq G, \\
\displaystyle \sum_{l=1}^{r_j} y_{jl} \leq 1,  \ j=1,\ldots,N, \\
\displaystyle x_{ij}=0\hbox{ or }1, \ i=1,\ldots,M,\ j=1,\ldots,N, \\
\displaystyle y_{jk}=0 \hbox{ or }1, \quad j=1,\ldots,N, \ k=0,\ldots,r_j. 
\end{array}
\right.
\end{eqnarray*}

Models (PR) and (PRG) allow students to be assigned to courses which are their last choices, although the courses, which are their first choices, are available. To avoid that case, additional condition U7 is added to the models (PR) and (PRG). Condition U7 ensures that student's satisfaction for every student is at least $B^S$, and is given by
\begin{equation}\label{uvjet:minimalno_zadovoljstvo}
\sum_{j=1}^N  c_{ij} x_{ij}\geq B^{S}, \quad i=1,\ldots,M,
\end{equation}
Choice of $B^S$ is arbitrary, but for large $B^S$, there is a high probability that model for assigning students has no solution. 

Condition U8 is introduced to ensure that all the courses are enrolled by equally motivated students.  The basic idea is: if the coefficients of satisfaction are higher, students are more motivated and teaching results are better. For the course $P_j$, we define average satisfaction of students by
\[
\frac{\sum_{i=1}^M  c_{ij} x_{ij}}{\sum_{i=1}^M  a_{ij} x_{ij}} , 
\]
where denominator is number of students who are enrolled in the $P_j$, and nominator is sum of coefficient of satisfaction for those students. From
\[
	\frac{\sum_{i=1}^M  c_{ij} x_{ij}}{\sum_{i=1}^M  a_{ij} x_{ij}} \geq B^{C} \Leftrightarrow
	\sum_{i=1}^M  c_{ij} x_{ij} \geq B^{C} \sum_{i=1}^M  a_{ij} x_{ij}    
\]     
it follows that condition U8 is given by
\begin{equation} \label{uvjet:minimalno_predmet}
\sum_{i=1}^M  \big(c_{ij}-B^{P}a_{ij} \big) x_{ij}\geq 0,\quad j=1,\ldots,N.
\end{equation}

Conditions U7 and U8 can be combined with both models (PR) and (PRG). The names of models with different additional conditions are given in the Table \ref{tab:imena}. 

\begin{table}
	\begin{center}
\begin{tabular}{|c|ccc|}
	\hline  &\multicolumn{3}{c|}{\textbf{Additional conditions}}   \\ 
	\hline\textbf{ Basic models} & \textbf{U7} &\textbf{ U8} & \textbf{U7 and U8} \\ 
	\hline (PR)                  & (PR*)       & (PR1)       & (PR1*) \\ 
	       (PRG)                 & (PRG*)      & (PRG1)      & (PRG1*) \\ 
	\hline 
	\end{tabular} 
	\caption{The names of assigning models with different additional conditions.
		\label{tab:imena}}
	\end{center}
\end{table}


Because all the variables in the aforementioned models can have only values 0 or 1, the goal function is obviously upper bounded and if we can find feasible solution the existence of the solution is proven. Unfortunately, we are only able to give some necessary conditions for existence of solution, but sufficient conditions are not known.

From the nature of problem it is easy to see that solution is not unique. 


\section{Application of the models}

In this section we present application of the assigning models to the real-life problem. The main parameters of the observed problem are
\begin{itemize}
	\item Number of students is $M=166$, number of elective courses is $N=21$.
	%
	\item Every student has to choose and order $L=4$ preferable courses and is assigned to the $K=2$ courses.
	%
	\item Coefficients of satisfaction are four for the course which is first choice, three for the second one, two for third choice and one for the last choice. 
	%
	\item All students enrolled in the course $P_j$, can be divided into at most two groups, i.e. $r_j=2$ for $j=1,\ldots,N$. 
	\item The lower and upper bounds for number of students in the $k$ groups and maximal number of students in the one group are the same for all courses:
	\begin{equation*}
	   g_j=28, \ M\!P_j^1=g_j,   \ M\!P_j^2=2g_j,
		 \ m\!P_j^1=m\!P^1,\ m\!P_j^2=m\!P^1+g_j, j=1,\ldots,N. 
	\end{equation*}
	The lower bound for the number of students in the one group, $m\!P^1$, can have values 10, 11 and 12.
	%
	\item The maximum number of groups is $G=16$.
	%
\end{itemize}


In the Table \ref{tab:prikupljeniPodaci} are presented data about students preferences. For each course number of interested students and their average coefficient of satisfaction are given.                                            

\begin{table}
	\begin{center} %\setlength{\extrarowheight}{1pt}                                   
		\begin{tabular}{|c|ccccccccccc|}\hline                                        
			Course & $P_1$ & $P_2$ & $P_3$ & $P_4$ & $P_5$ & $P_6$ & $P_7$ & $P_8$ & $P_9$ & $P_{10}$ & $P_{11}$ \\ \hline       
			A & 9 & 10 & 73 & 28 & 67 & 3 & 86 & 41 & 21 & 34 & 89  \\                                          
			B & 2,33 & 2,70 & 2,77 & 1,96 & 2,16 & 1,33 & 2,76 & 2,44 & 2,10 & 2,32 & 2,83 \\                          
			\hline                                                                     
			\hline                                                                     
			Course  & $P_{12}$ & $P_{13}$ & $P_{14}$ & $P_{15}$ & $P_{16}$ & $P_{17}$ & $P_{18}$ & $P_{19}$ & $P_{20}$ & $P_{21}$ &  \\  \hline
			A & 10 & 14 & 48 & 9 & 14 & 26 & 19 & 36 & 12 & 15 & \\                                        
			B  & 2,20 & 2,36 & 2,67 & 2,11 & 2,29 & 1,88 & 1,84 & 2,78 & 2,50 & 3,07 & \\
			\hline
		\end{tabular}
		\caption{ \label{tab:prikupljeniPodaci}The collected data about students interest in particular course. 	A - Number of students interested in course, B - average coefficients of satisfaction of students interested in course. }
	\end{center}
\end{table}

Although minimal student satisfaction $B^S$ is not listed as a original parameter of the problem, the number of dissatisfied students is smaller when the condition of minimal student satisfaction is included. We set $B^S=5$. 

The problem is solved by use of models (PRG), (PRG1) and (APRG$^{\ast}$), which is an adapted version of model (PRG$^{\ast}$). Model (PRG$^{\ast}$), for the number of groups $G=16$ and $B^S=5$, has no solution if the $m\!P^1\geq 10$, so we develop adapted model (APRG$^{\ast}$). The first step in the model (APRG$^{\ast}$) is to find solution of the model (PRG$^{\ast}$)  for the smallest possible number of groups $G^{\ast}$ and let $P^{\ast}$ is set of the all included courses. Let $g$ be difference between $G^{\ast}$ and $G$. After that, for all subsets of the $P^{\ast}$ with $g$ elements, we solve model (PRG$^{\ast}$) with further limitations:
\begin{itemize}
	\item Only the courses from $P^{\ast} \setminus T$ are allowed, where $T$ is any subset of $P^{\ast}$ with $g$ elements. 
	\item If the student $S_i$ can not achieve minimal satisfaction through the courses from $P^{\ast} \setminus T$, do not apply minimal satisfaction condition for $S_i$.
\end{itemize} 
Let $R_T$ is solution of (PRG$^{\ast}$) for particular $T\subset P^{\ast}$. Then the solution od (APRG$^{\ast}$) is the best of the solutions $R_T$. The details of model (APRG$^{\ast}$) are shown in the Figure \ref{alg:APRG}.  

  


\begin{figure}  
	 \hrule \smallskip
	\begin{algorithmic}[1]
		\STATE Solve the model (PRG$^{\ast}$) for the smallest possible number of groups $G^{\ast}$. Let $P^{\ast}=\{ P_{j_1}, \ldots, P_{j_{G^{\ast}}} \}$ is the set of all courses included in the solution, and let  $P_E^{\ast}=P\setminus P^{\ast}$ is the set of omitted courses.
		\STATE $g \leftarrow G^{\ast} - G$. \COMMENT{number of groups to discard}
		\STATE $T_g=$  set of the all subsets of $P^{\ast}$ with  $g$ elements.   
		\STATE $i\leftarrow 0$
		\FORALL{$T \in T_g$}
		\STATE Let $S_E$ represents set of all students where minimal satisfaction condition can not be achieved when courses  $P_E=P_E^{\ast} \cup T$ are omitted.
		\FORALL{$P_{s} \in P_E$}
		\STATE $m\!P_s \leftarrow 0$ \COMMENT{exclude $P_s$ from solution}
		\STATE $M\!P_s \leftarrow 0$
		\ENDFOR 
		\FORALL{$S_{r} \in S_E$}
		\STATE $B_r^S \leftarrow 0$ \COMMENT{for student $S_r$ do not apply minimal satisfaction condition}
		\ENDFOR
		\STATE $i \leftarrow i+1$
		\STATE $R_i$ is solution of the model (PRG$^{\ast})$, but without courses from  $P_E$, and without condition of minimal satisfaction for all students from $S_E$.
		\ENDFOR
		\STATE Final solution is the best of the solutions $R_i$.
	\end{algorithmic}
	\smallskip \hrule
	\medskip 
	\caption{\label{alg:APRG} Algorithm for the model (APRG$^{\ast}$).}
\end{figure}


The solution of the problem for the various parameter $m\!P^1$ and the various models  are given in the Table \ref{tab:rjesenja1}. In the Table \ref{tab:rjesenja2} is given the structure of solutions, i.e. which courses are included in the particular solution. In the all solutions, except solutions 6 and 7, the students are assigned in to 16 groups. Also, in all solutions, the students enrolled in the courses $P_3$, $P_7$ and $P_{11}$  are divided in the two groups, but other courses included in the solutions have only one group. For all models, higher $m\!P^1$ increases number of students with student's satisfaction less than $B^S$.  

Model (PRG) is the basic model for the case when students can be enrolled in the one or more groups, so its solutions have the highest value of goal function compared to models (PRG1), (PRG$^{\ast}$) and (APRG$^{\ast}$) for the same parameters. The presented solutions have only one student who is assigned to the one course and the number of students with student's satisfaction smaller than $B^S$ is also small. 


\begin{table}
	\begin{center}
		\begin{tabular}{|c|ccccccc|}\hline
			\bf A &\bf  B & \bf C &\bf  D &\bf  E &\bf  F &\bf  G &\bf  H  \\ \hline
			1 & PRG & 10 & 1096 & 165 & 1 & 4 & 2,70\\
			2 & PRG & 11 & 1095 & 165 & 1 & 4 & 2,64\\
			3 & PRG & 12 & 1089 & 165 & 1 & 5 & 2,50\\ \hline 
			4 & PRG1 & 10 & 1096 & 166 & 0 & 3 & 2,80\\
			5 & PRG1 & 11 & 1095 & 166 & 0 & 3 & 2,64\\
			6 & PRG1 & 12 & 1077 & 161 & 5 & 8 & 2,75\\
			7 & PRG1 & 12 & 1060 & 159 & 7 & 11 & 2,83\\ \hline
			8 & APRG$^{\ast}$ & 10 & 1091 & 165 & 1 & 2 & 2,70\\
			9 & APRG$^{\ast}$ & 10 & 1089 & 166 & 0 & 2 & 2,64\\
			10 & APRG$^{\ast}$ & 11 & 1088 & 165 & 1 & 2 & 2,55\\
			11 & APRG$^{\ast}$ & 11 & 1085 & 166 & 0 & 2 & 2,36\\
			12 & APRG$^{\ast}$ & 12 & 1084 & 165 & 1 & 2 & 2,50\\
			13 & APRG$^{\ast}$ & 12 & 1080 & 166 & 0 & 2 & 2,25\\
			14 & APRG$^{\ast}$ & 12 & 1057 & 166 & 0 & 1 & 2,25\\ \hline
		\end{tabular}
		
		\caption{\label{tab:rjesenja1} Solutions of the problem. Description of the columns: A - Solution number, B - Model, C - $m\!P^1$,  D - The value of goal function, E - Number of the students assigned to the two courses, F - Number of the students assigned to the one course, G - The number of the students with student's satisfaction less than $B^S$, H - The minimal average satisfaction for any course included in the solution.} 
	\end{center}
\end{table}

Using of the model (PRG1) is somehow complicated because minimal average satisfaction $B^C$ have to be chosen carefully, but there is no obvious choice as for minimal student's satisfaction $B^S$ and the best approach is experimenting with different $B^C$.  In this problem, for the solutions 4 and 7, $B^C$ is set to $2.80$, for the solution 5, $B^C$ is $2.60$, and for the solution 6, $B^C$ is $2.75$.     It is interesting to compare solutions of the models (PRG) and (PRG1) for $m\!P^1=10$ (solutions 1 and 4) and $m\!P^1=11$ (solutions 2 and 3). In the case when $m\!P^1=10$, both solutions have same value of goal function, but the solution of model (PRG1) looks better because there are no students assigned to only one course and there are also fewer students which student's satisfaction is smaller than $B^S$. In the case when $m\!P^2=11$, solutions have similar behaviour as in the case $m\!P^1=10$. For the case $m\!P^1=12$, two solutions are presented which differ in the choice of $B^C$. When $B^C=2.60$ (solution 6), the solution include 15 groups, but when $B^C=2.80$ (solution 7), the solution include only 14 groups. As expected, decreasing the number of groups is the cause of the increasing number of dissatisfied students. 

From definition of the model (APRG$^{\ast}$) it can be seen that the solution of model is one of the solution of many auxiliary problems, specifically the one which has the greatest value of goal function. On the other hand,  we can observe other measures like the number of students assigned to the two courses or the number of dissatisfied students. Therefore in the Table \ref{tab:rjesenja1} are presented two or more solutions of the model (APRG$^{\ast}$) for the same parameters - the solution with maximal value of goal function and the solution where all students are assigned to the two courses (if there are more such solutions, the solution with maximal goal function is chosen). Generally, solutions of the model (APRG$^{\ast}$) has smaller value of goal function  than solution of the model (PRG) for the same $m\!P^1$, but the number of dissatisfied students is smaller. The last presented solution is interesting because the number of dissatisfied students is only one, but there is significant difference in the value of goal function between that solution and solution 13, where the number of dissatisfied students is two. We can conclude that the attempt to decrease number of dissatisfied students results in increasing number of students which satisfaction is not maximal possible.
 

\begin{table}
	\begin{center} %
		\begin{tabular}{|c|ccc|cccc|ccccccc|}\hline
			& \multicolumn{14}{c|}{\bf Solutions} \\ \hline
	\textbf{Course}		& 	1 & 2	 & 3 & 4 &	5 & 6	 & 7 & 8 &	9 & 10 & 11 & 12 & 13 & 14 \\ \hline 
			$P_2$	 & & & & & & & & & $+$ & & & & & \\
			$P_3$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_4$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & & & & & \\
			$P_5$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_7$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_8$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_9$	 & & & & & & $+$ & & $+$ & & $+$ & $+$ & $+$ & $+$ & \\
			$P_{10}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{11}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{13}$	 & $+$ & & $+$ & & & & & & & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{14}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{16}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & & & $+$ & $+$ & $+$ & & $+$ & & $+$ \\
			$P_{17}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & & & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{18}$	 & & & & & & & & & & & $+$ & & $+$ & $+$  \\
			$P_{19}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\
			$P_{20}$	 & & $+$ & & $+$ & $+$ & & & $+$ & $+$ & & & & & \\
			$P_{21}$	 & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\  \hline
		\end{tabular}
		\caption{ 	\label{tab:rjesenja2} The structure of solution. The vertical lines divide solutions from the various models.}
	\end{center}
\end{table}

All calculations were done by software program \textit{Mathematica} and its solver \verb|LinearProgramming|, which can solve integer programming problems. Time to find the solution of the model (for particular choice of the parameters) is between 20 seconds and 4 minutes, so it seems that there is no reason to develop an special algorithm for solving.

\section{Conclusion}
The problem of assigning students to elective courses on academic institution is observed. Because the timetable is devised after the assignment process, this problem is less demanding then classical course scheduling problem, so we pay attention to maximization of student satisfaction. In the standard two-round system  the main problem is that all the students can not be assigned to desired courses because of the physical (too many students) or financial (insufficient number of students) reasons. In the new system, we allow students to enter more desired courses with preference rankings. Integer programming based model is built according to the business demands and the student preferences are built into the objective function of the model and into the additional constraints (minimal student satisfaction) that assure better choice of the courses if it is possible.
The former two-round system is now replaced with one round system where the time span is shortened and students can be enrolled in the courses they prefer. 
The models are not tested in the situation with large number of variables.
 
Additionally, the models can be easily extended to satisfy the demands so as to "better students have priority" or "some courses are important and have to be included in the solution" by modification of the goal function, coefficients of satisfaction and existing constraints. The main contribution of the new model is introducing the concept of minimal student satisfaction which reduce the number of students unsatisfied  with their assigned courses.  


\bibliographystyle{ieeetr}
%\bibliography{koi2014}{}
\begin{thebibliography}{10}
	
	\bibitem{chen_applied_2010}
	D.-S. Chen, R.~G. Batson, and Y.~Dang, {\em Applied integer programming:
		modeling and solution}.
	\newblock Hoboken, N.J: John Wiley \& Sons, 2010.
	
	\bibitem{hillier_introduction_2001}
	F.~S. Hillier and G.~J. Lieberman, {\em Introduction to operations research}.
	\newblock Boston: {McGraw}-Hill, 7th ed~ed., 2001.
	
	\bibitem{kaufmann_integer_1977}
	A.~Kaufmann and A.~Henry-Labordère, {\em Integer and mixed programming:
		theory and applications}.
	\newblock No.~v. 137 in Mathematics in science and engineering, New York:
	Academic Press, 1977.
	
	\bibitem{albright_data_2011}
	S.~C. Albright, W.~L. Winston, and C.~J. Zappe, {\em Data analysis and decision
		making}.
	\newblock Mason, Ohio: South-Western/Cengage Learning, 4th ed~ed., 2011.
	
	\bibitem{schaerf_survey_1999}
	A.~Schaerf, ``A {Survey} of {Automated} {Timetabling},'' {\em Artificial
		Intelligence Review}, vol.~13, pp.~87--127, Apr. 1999.
	
	\bibitem{carter_recent_1997}
	M.~W. Carter and G.~Laporte, ``Recent developments in practical course
	timetabling,'' in {\em Practice and {Theory} of {Automated} {Timetabling}
		{II}} (E.~Burke and M.~Carter, eds.), no.~1408 in Lecture {Notes} in
	{Computer} {Science}, pp.~3--19, Springer Berlin Heidelberg, Aug. 1997.
	
	\bibitem{daskalaki_integer_2004}
	S.~Daskalaki, T.~Birbas, and E.~Housos, ``An integer programming formulation
	for a case study in university timetabling,'' {\em European Journal of
		Operational Research}, vol.~153, pp.~117--135, Feb. 2004.
	
	\bibitem{kristiansen_elective_2011}
	S.~Kristiansen, M.~Sørensen, and T.~R. Stidsen, ``Elective course planning,''
	{\em European Journal of Operational Research}, vol.~215, pp.~713--720, Dec.
	2011.
	
	\bibitem{muhlenthaler_fairness_2014}
	M.~Mühlenthaler and R.~Wanka, ``Fairness in academic course timetabling,''
	{\em Ann Oper Res}, pp.~1--18, Feb. 2014.
	
	\bibitem{rudova_university_2003}
	H.~Rudová and K.~Murray, ``University course timetabling with soft
	constraints,'' in {\em Practice and Theory of Automated Timetabling {IV}}
	(E.~Burke and P.~D. Causmaecker, eds.), no.~2740 in Lecture Notes in Computer
	Science, pp.~310--328, Springer Berlin Heidelberg, Jan. 2003.
	
	\bibitem{sampson_class_1995}
	S.~E. Sampson, J.~R. Freeland, and E.~N. Weiss, ``Class scheduling to maximize
	participant satisfaction,'' {\em Interfaces}, vol.~25, pp.~30--41, June 1995.
	
	\bibitem{badri_multi-objective_1998}
	M.~A. Badri, D.~L. Davis, D.~F. Davis, and J.~Hollingsworth, ``A
	multi-objective course scheduling model: {Combining} faculty preferences for
	courses and times,'' {\em Computers \& Operations Research}, vol.~25,
	pp.~303--316, Apr. 1998.
	
\end{thebibliography}

\end{document}