Project Title: Python-Based Optimization Software Library for the Office Space Allocation Problem   
Student: Arnav Saxena 
Course: MS in Computer Science (Artificial Intelligence)  

Abstract: 
The Office Space Allocation Problem in an academic setting refers to the 
assignment of a set of available spaces (such as office rooms or classrooms ) to a 
set of entities (such as employees, departments, or groups) in a way that reduces 
space wastage and satisfies additional imposed constraints. In the literature, both 
exact methods and heuristics have been applied to this problem and it is found 
that the latter provides competitive solutions in a very short time as compared to 
the former. This dissertation provides a software library implementation to tackle this 
problem. It includes baseline heuristics and procedures that read in test instances 
and provide an entity-room allocation as output. An analysis regarding the 
feasibility and infeasibility of the allocations produced by the constructive and 
exploration heuristics is provided. Furthermore, effects on these allocations by 
varying parameters like hard constraint penalty and initial allocation quality are
also documented in this work. The results reveal that a low hard constraint penalty 
value allows the exploration metaheuristics to venture out to find better solutions 
but at the same time the probability of converging and staying in the feasible 
region decreases. It was also found out that an initial allocation with very low hard 
constraint violation (feasible/almost feasible) is not a good starting choice for the 
exploration heuristic as it converges too quickly towards the feasible region and 
overlooks higher-quality solutions. Overall a balance has to be struck between 
exploring and converging. This dissertation aims to equip the readers with the 
knowledge of selecting the right set of heuristics and parameters to reach the 
globally optimal allocation in a reasonable amount of time.