Combinatorial Optimization Course
Last semester I took the course “Combinatorial Optimization and Network Analysis” by Dr. Farnaz Hooshmand Khaligh. With my previous interest in the operation research field, and also having the course “Non-linear Optimization” by Dr. Ali Mirhassani in the same semester, I had the chance to deepen my understanding of advanced optimization concepts. This course focused on varied methods for modelling integer and mixed-integer programming problems, mostly the ones concerned with combinatorial ideas, such as graph-based problems.
The semester ended with our final project, which was an exhaustive overview and implementation of the paper “College admissions with ties and common quotas: Integer programming approach” by Kolos Csaba Ágoston, Péter Biró, Endre Kováts, and Zsuzsanna Jankó. Link to the paper: ScienceDirect
This research focused on a perceptible problem, assigning applicants with varied scores and preferences to different programs with quotas. The most basic form of this problem is solved in polynomial time with the deferred-acceptance algorithm, but as the authors have explained in the paper, the limitations and distinctive features of the Hungarian college admission system have made the problem NP-hard.
To overcome this new complex problem, they have developed multiple optimization model formulations to find the best assignment of the students. The paper first presents multiple equivalent formulations for the basic form of the problem, then by adding more constraints, grows the models to match the more limited conditions.
The conditions we talk about here are:
- Ties, when multiple students with the same score are competing for fewer available seats at the same program.
- Lower quotas, when programs have a minimum number of students.
For the project, I reviewed and implemented the formulations for ties and common quotas, including the Hungarian, Irish, and Chilean policies compared in the paper. I used Python and Pyomo package to execute the formulations in these sections, and I’ve written a comprehensive report on the mathematical details and implementation aspects of my project.
For the first time in a data-driven project, I avoided putting all my code in one single Jupyter Notebook. From the starting point, I used separate python files to create a scalable and readable program. I eventually used a notebook file to showcase the results, by calling the pre-defined functions and classes.
You can find the full version of my project in this GitHub repository (Including my full Persian report): GitHub
This course, its lectures and assignments, and remarkably its final project were a delight in the last semester, changing how I view the optimization domain and setting a prospect for my future academic path.
#Optimization #IntegerProgramming #OperationsResearch #CombinatorialOptimization #Pyomo #MIP #CollegeAdmissions
Cover Image: Cover of the book “Combinatorial Optimization” by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver
