Carpeta

2024-11-15

Back
During my last year of university in Bogotá, I took a course on Modeling, Simulation and Optimization. The course intended to teach about how to turn real world problems into mathematical models, and how to solve them using optimization techniques. Many times in my life i had crossed paths with problems where I had a set of constraints and a set of variables, and I had to find the best solution. Naively I always tried to solve it by using my own algorithms, always trying to find a faster algorithm and reducing the complecity of the problem, the search space. But I never thought about the fact that these kinds of problems were already widely studied and solved. I was always trying to reinvent the wheel, and I never thought about the fact that there were people who had already done the hard work of finding the best solution. Suddenly these kind of problems started to appear everywhere, in problems I had tried to solve in the past and problems I was suddenly seing clearly in my day to day. That same year I ended up writing my thesis about a platform I intended to develop with the director of my major (Computer Engineering). The idea was to create a platform that allowed students and directives to check a students progress in their majors and minors. The main issue was that the current platform included in the university's management platform was to complex to program for directives and to slow and inacurate for students to realiably check their progress. The first big problem to solve was how to create a broad enough abstraction of the rules for someone to graduate from a certain program that was scalable to any single condition or constrain that a degree could have. After many discussion and planing with my professor numerous approaches started to appear each with a fatal flaw that would take us back to the drawing board victim of a obscure requirement that was simply not possible to implement. Till one day, the solution appeared, checking how far a student was in its degree was equivalent to optimizing the number of credits a student had to take in order to graduate. Following the rules that made that credits count of course. Optimization, variables and constraints. The aprocahed ended up being to create rules that try to encapsualte a "kind" of requirement, thinking first and most on the directive that would have to create the requirement in the patform. But defining then strictly behind the scenes. Then the platform would translate this into a formal constraint and the ILP solver would take care of the rest. After some discussion, my professor suggested we used Prolog, a logic programming language that allows to define rules and constraints in a very natural way. But lacked in two ways, it's integration with a web platform would require the design and implementation of an API that would carry the load of the optimization ,the former being the second problem. Due to prologs design backtracking was the solution searching algorthm that prolog would implemnt, and just by ruinning some tests this turned too slow to be a viable solution. After some research I found out about glpk, the GNU Linear Programming Kit. this is the standard for linear programming solvers and soon enough I found YALPS (Yet Another Linear Programming Solver), an implementation og glpk in javascript that was way lighter and faster than any other js solver I could find. It solved both prologs problems. It was way faster and was light enough to be integrated in the web platform so we could use the devices processing power to solve the optimization intead of reliying in an API that could be slow and expensive. So the work began. The first couple weeks were spent creating the optimization rules and constraints. Just one js file that would take a sample program requirments and a set of courses taken to output the best possible solution. all in JSON format. when I finally had a working version of the optimization algorithm, I started to work on the web platform. Using tailwind, svelte and ShadCN components I started to create the platform.

CC BY-NC 4.0 2024 © ma-r-s

?