Add timetable optimisation feature

[thejus03]

TimetableAI

TimetableAI allows users to automatically generate optimised timetables based on their module selection, preferred semester, and free-day preferences.

Key Features

• Maximising Free Days: The algorithm prioritises creating schedules that align with users' preferences for free days
• Minimising Travel Time: It considers the physical distances between classrooms to reduce travel time between classes
• Lunch Time: Prioritises to give at least 1 hour for lunch between 12-2pm
• Clash-Free scheduling: Ensures all classes are conflict-free.

High level integration

• We use the NUSMods API to preprocess venues data to clump different rooms in the same building together to get the average x and y coordinate of the building.
• From the user-selected modules, we use the NUSMods API to get all the slots for each module the user selected. We then remove all non-lecture slots that are on the free days the user selected. Then merge slots between the same modules based on those that are at the same timing, day and building location.
• Now that we have all the slots, we construct a graph where we make edges between slots that clash.
• Then we use backtracking to create all possible timetables that do not clash, using the graph to prune immediately when there is a clash.
• Now that we have all the possible timetables, we score the timetables based on a scoring system that we elaborate on below. The top 5 ranking timetables are returned to the frontend.

Scoring system

This system is an award-punish scoring system:

• Awards for having at least an hour of time for lunch
• Punish timetables with lessons outside of the user-selected favourable timings
• Punish long distances travelled between lesson locations.

[ravern]

This sounds cool!

Seems like you already have a working implementation of this algorithm at https://github.com/thejus03/hacknroll. Would this request be to integrate your existing work with the NUSMods website?

[thejus03]

Thanks Ravern!

Yup, we’re hoping to integrate TimetableAI as a feature within NUSMods so that it can benefit all NUS students by saving them several hours during timetable planning each semester.

TimetableAI requires intensive computing to calculate and score millions of timetables for every student who uses it. So there is a need for a backend capable of handling this load. Currently, I believe that NUSMods does not have a backend and instead use serverless functions to handle this. Perhaps it is possible to integrate TimetableAI using a similar serverless approach?

Do let us know what you think.

[ravern]

Agreed that adding timetable planning and optimisation as a feature will benefit NUS students!

There has actually been a past attempt to build and integrate a timetable solver at #3294 (currently standalone hosted at https://nus-optimizer.com), with a PR #3296 already in significant progress. It avoids the computational load issue by running the computation on the client-side instead. However, it was last updated in 2021.

Would you prefer to pick up from where #3296 left off, or integrate your own solution from scratch (including the UI, which should use existing NUSMods components/styling)?

To give more context, our current export service currently runs on Vercel on the (free) Hobby tier. This is the serverless function(s) that run when you click "Download" on your timetable. I believe it is possible to port your current Go code over to Vercel using the Go runtime (but which is currently in beta).

However, I am concerned that we will exceed the Vercel Hobby tier, especially since it appears your optimiser is computationally intensive, thus making it financially unsustainable. If we choose to proceed with the server-side solution, we would have to observe usage and take it down if it starts to exceed the Hobby tier.

We could potentially approach NUS to fund Vercel costs (in addition to our existing server costs), but I'm unsure if that will go through either (but we can try).

[thejus03]

Thanks, Ravern! There are a couple of points I want to raise:

TimetableAI vs. NUS Optimizer

From my understanding, there's a significant fundamental difference between the tasks we address.

NUS Optimizer considers free days, earliest and latest lesson timings, and lunch breaks. It solves for a SINGLE random valid timetable that meets these criteria and sends it back to the client. As a result, it runs fast, taking an average of just 10 seconds.

On the other hand, TimetableAI builds upon the functionality of NUS Optimizer by additionally optimising for an important aspect - travel distance. To achieve this, TimetableAI needs to generate and evaluate ALL valid timetables (~ several tens of millions) and scores each one based on multiple factors, including location and travel distances. Consequently, TimetableAI truly returns the MOST optimised timetable for the client. As a result, this is a slow process and can minutes depending on the CPU power.

If we decide not to consider travel distances (which requires scoring and comparing timetables against each other) and only return a single valid timetable based on the remaining criteria, TimetableAI would similarly only take a couple of seconds.

Using WebAssembly (WASM) and WebWorkers (as in NUS Optimizer) for TimetableAI

NUS Optimizer employs WebAssembly to run its solver entirely client-side. Currently, TimetableAI is written in Go, and it is possible to port it to WebAssembly using Go WASM. However, some reports indicate that Go WASM can be 10-13 times slower than native Go, further extending the already slow computation time. Additionally, Go WASM operates on a single thread, whereas TimetableAI currently leverages multi-core processors through goroutines and channels, significantly reducing computation time. Technically, to use multiple CPU cores on the client-side, we might spawn multiple WebWorkers and partition tasks accordingly, although I'm uncertain how exactly to achieve this.

Converting our codebase to Rust and leveraging Rust's WebAssembly might be slightly better, as Rust WASM reportedly runs only about 5 times slower than native Rust and supports WASM threads (via wasm32-threads). However, among other technical challenges, Sam and I lack experience in Rust, although we're still open to exploring this option.

There are also doubts that running such CPU-intensive task can affect UI performance. Furthermore, performance is purely dependant on client's device.

Running as a Serverless Function on Vercel

From the Vercel Docs, it appears that functions under the Free Hobby Tier have a maximum duration of 60 seconds. Given TimetableAI’s current computational needs, this limitation isn't sufficient. Furthermore, in terms of CPU power, I am not sure how "good" it is but I believe we cannot allocate vCPU as needed for Hobby Tier.

Other providers, such as AWS Lambda and Google Cloud Run, offer free tiers that allow functions to run for over 15 minutes and enable vCPU allocation.

However, returning to my initial point, if we decide to no longer factor in travel times, it might be possible to effectively use Vercel's Free Hobby Tier.

We are open to considering any of the above or other feasible solution that works so that we can deliver TimetableAI to students!

[samthambad]

Hi @ravern, another approach could be creating a downloadable app that works alongside the NUSMods website. While fewer users might try it since they'd need to download something, it would be essentially free to run, both for users and for NUSMods servers, because all the computation would happen on the user's own computer.

Regarding the nus-optimizer.com functionality mentioned by @thejus03, we've found that when testing with realistic student requirements, nus-optimizer sometimes struggles to generate viable timetables, while our solution is able to provide results within a few minutes. Given these differences in approach and performance, we believe developing our own solution would be more effective than building upon the existing solution.

[ravern]

Thank you for providing your reasoning @samthambad @thejus03!

On the other hand, TimetableAI builds upon the functionality of NUS Optimizer by additionally optimising for an important aspect - travel distance.

This makes sense, sorry if I missed this point earlier. I think the ability to optimise by travel distance (in addition to everything else) is indeed quite a cool feature.

---

I see a few approaches suggested so far (correct me if I missed something out):

1. Using AWS Lambda or Google Cloud Run, for full set of features, running in the cloud
2. Integrate with existing Vercel serverless, without travel distance feature, running in the cloud
3. Compile Go code to WASM for reduced performance, for full set of features, running client-side
4. Rewrite into Rust and compile to WASM for better performance (it remains to be seen though), for full set of features, running client-side
5. Create a downloadable app

---

Unfortunately, I don't think we are open to adding new infrastructure to the NUSMods as of now, due to increased surface for security concerns (the school audits us), and the added complexity of AWS or Google Cloud (as compared to the simplicity of Vercel). So Approach 1 would not be possible at this time.

I'm open to taking Approaches 2, 3 and 4. You've probably thought about this already, but we could make travel distance optional, allowing users to quickly generate a timetable without considering travel distance, or wait longer to do one with the travel distance optimisation.

For Approach 5, if you would still like to pursue it, could you elaborate more about what kind of app this would be, and how it would "work alongside NUSMods"?

---

Feel free to choose either Approach 2, 3 or 4 (or suggest another approach). Please do let me know here, and we can move this feature towards being taken and implemented!

We should also discuss the UI changes that will need to be made for this.

[ravern]

Just as a side note, in the prior work, there was an interesting ethical discussion about everyone having access to the most optimised timetables. I'll just quote it directly here:

Ethical considerations

I and others were concerned that computing optimal timetables would upset the demand-and-supply characteristics of the module registration system. There might be excessive demand for "ideal" lesson configurations, resulting in more students ending up without classes. My thoughts:

• I designed the system from the start to randomize the timetable output each time. Students can also click the Run Optimizer button multiple times to get a different timetable at random. Therefore, if there are multiple possibilities, students are unlikely to get identical timetables
• However, it is possible that there are only a few "really good" lesson configurations (e.g., with free days, classes after 10am, etc).
• If so, I believe that our module registration system shouldn't fundamentally rely on an information / effort asymmetry between students to work. Imo, the optimizer is basically uniformly reducing this barrier for all students, so it's okay.

[thejus03]

Thanks @ravern for the feedback!

Amongst approach 2, 3, 4 and 5, personally we feel that 2 and 5 are the more feasible options since performance would not be greatly affected.

Since it’s clear that finding the very BEST timetable is going to require significant CPU resources and longer runtimes—and is therefore not feasible for serving thousands of NUS students within our current resource limits—we believe it’s important to find a balance between runtime and optimisation quality.

This leads me to my next point. After some research looking at other algorithms for this solver, we would like to suggest an alternative approach using Beam Search.

Beam Search is a heuristic search algorithm that navigates a graph by systematically expanding the most promising nodes within a constrained set.

It is particularly well-suited to problems like ours, where the search space is vast and we care more about finding a very good solution quickly, rather than the absolute best one.

Using Beam search, I believe we can find a valid timetable that meets all criteria and achieve strong minimisation of travel distance, while significantly reducing runtime. However, success depends on designing a good heuristic that can score partially constructed timetables for their potential. Furthermore, we need to try and test out our Beam Search by enumerating the Width of the Beam and Branching factor to find the "sweet spot".

In theory, I believe that this is a better approach to option 2 (though this remains to be seen). During my research, I also came across another technique using constraint solvers (like SAT solvers). I haven’t explored this in depth yet, but it might be another viable option if Beam Search doesn’t perform well enough.

@samthambad will elaborate more on approach 5.

[ravern]

In theory, I believe that this is a better approach to option 2 (though this remains to be seen). During my research, I also came across another technique using constraint solvers (like SAT solvers). I haven’t explored this in depth yet, but it might be another viable option if Beam Search doesn’t perform well enough.

I believe that's what the previous implementor used for his approach, by using z3.

---

For approach 2, I think we should be adding a new Vercel project at the root of the repo, perhaps called optimizer. It should look similar to the current export project. For development and testing on your end, you should be able to create a Vercel project for yourself with the free Hobby tier.

Once your PR is created, I can help to create the official Vercel project for us to test on and eventually use in production!

---

That being said, if traffic proves to be too heavy and incurs costs, or we exceed the limits and cause the feature to be broken due to edge functions dropping requests, we might have to suspend and re-evaluate the approach.

---

Please also think (and perhaps even design) the UI that will go along with this feature! It should make use of components that fit into the current NUSMods theme.