[RFC] Design Discussion for integrating NUS Timetable Optimizer

[frizensami]

This is a fairly long issue - my apologies! I hope it will provide a good base for discussion.

---

Is your feature request related to a problem? Please describe.

Students have many possibilities each semester when choosing lessons and modules for their timetable. This is especially difficult and time-consuming in earlier academic years.

• Introductory modules (e.g., for CS, CS1101S, CS1231S) may have tens of choices for their lessons, some of which may conflict with other modules.
• Senior students (with fewer lesson choices) may benefit from a way to choose a subset of modules instead.
• Generally, students also may prefer to start their lessons no earlier than a certain time, have more free days, allow some time for lunch, etc.

Therefore, a feature that automatically optimizes a student's NUSMods timetable subject to their preferences might be very useful.

---

MVP Solution Implementation (NUS Timetable Optimizer)

Description

NUS Timetable Optimizer (GitHub link) is a standalone MVP implementation of this proposed feature. It takes as input a list of modules and a set of user-supplied constraints (e.g., free day / lunch hours / lesson start-end requirements), and outputs a timetable that meets the constraints. If optimization constraints are specified (e.g., compact the timetable as much as possible), the output timetable attempts to maximize/minimize the stated constraints. The list of possible new features are at the project's Issues page, with more to be added.

This issue aims to discuss the possibility of merging its functionality into NUSMods, and if so, to discuss the design considerations around its implementation.

Some results from MVP implementation

• 3,233 unique users since June 1st
• No timetable-generation-related errors reported
• Mean of 2 - 4 minutes spent optimizing on the site

Prior work

#390 describes a previous attempt to solve this issue, which inspired the current approach. Notable similarities are:

• We use a SMT solver/optimizer to compute matching timetables
• We treat each half-hour slot as an integer-valued variable
• Some similarities in encoding lessons as integer values

However, we also build upon #390. This is a short description of some of the improvements:

• We do not require any server-side computation. The constraints are converted to the SMTLIB2 format on the client
• The SMT solver is a WebAssembly-compiled version of the Microsoft Z3 SMT solver, instead of BoolectorJS. This solves timetables at near-native speeds (~1 second after removing outliers)
  
• We can support optimization ("soft") constraints instead of only hard constraints
• The problem encoding is somewhat more complicated for performance reasons.
• We handle cases more complex than modules held on odd-even weeks. We actually run the solver twice. The first run aims to compute the minimum set of weeks to simulate across all modules, and the second run actually computes the final timetable.
• Further details are deferred for a future writeup

---

---

---

Integration into NUSMods

This section aims to discuss the following design points that I can think of. I can check these off and insert the conclusions as this discussion progresses:

• Should / can this be integrated into NUSMods?
• Ethical considerations
• Infrastructure requirements
• Where should the optimizer go?
• UX flow

---

Should / can this be integrated into NUSMods?

• I think the MVP implementation and the previous deployment of Optimal Timetable Planning using constraint solving [1324] #390 indicates a good demand for this feature.
• NUSMods has already solved a lot of the issues around enjoyable timetabling UI/UX, and the specifics of the NUS timetable system, so it would be ideal to build off that.
• I won't be graduating for a couple of years at least, so I can feasibly see this deployment through :)

---

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.

---

Current infrastructure requirements

These are the two things the optimizer requires that might present deployment challenges.

1. WebAssembly Binary and Initialization
   z3w.wasm is the WebAssembly binary that is downloaded by each client to run the optimizer locally. A fully uncached download takes 4.3 MB over the network, uncompressing to 18.3 MB. However, this is a one-time cost. The file is cached after this.

This + Initializing the solver takes around 10 seconds on average.

However, I think this is the best implementation I can think of. Most serverless platforms (Cloudflare, Vercel, Netlify, AWS) have restrictions on solver runtime, so the 1 - 5 second runtime (which can be more for complex optimizations) is too much. Modern mobile and desktop devices are more than capable of running this computation, so I doubt the UX benefit of running the solver on a dedicated server platform is worth it. That option might also be prohibitively expensive.

Currently, this is deployed on a free Netlify instance, taking advantage of of the 100 GB free egress bandwidth. The app is just a statically served React bundle there.

2. Web Worker Usage
   I don't think this will be an issue due to the widespread use of Web Workers, but due to the CPU-intensiveness of computation, the optimizer runs on a web worker and communicates results through message-passing.

---

Where should the optimizer go?

I think the most natural place is on the main timetable page, but hidden behind the beta flag. For instance:

Showing the optimizer could mean showing constraints below the existing module list (Not a front-end person, please ignore the terrible styling!):

Every time the user runs the optimizer (say it's a button above the Constraints header), the timetable is arranged. Could add a button to restore the original timetable.

Other options?:

• Separate tab: could optimize the timetable there, and then swap the optimizer and main timetable.

---

UX Flow

What i'm envisioning:

1. User selects their modules and lessons as per the normal user flow
2. User clicks on the Show Optimizer button
3. If it's their first time, they have to click on an "Initialize Optimizer" button or something similar. This could provide a warning about the download size and init time if that's a concern.
4. After this, the user can repeatedly change their constraints and run the optimizer. Successful runs will shift their modules around in their main timetable.
5. We add a button to restore their original timetable, similar to the current import-through-share-link header.

Conclusion

I hope this issue acts as a base for discussing whether this feature is wanted, and how to implement it if so :)

[li-kai]

On the matters of bundle size and performance, I don't think it is a concern. NUS students tend to use modern browsers and relatively fast mobile phones (compared to the avg pop). What does matter, is the UX and how we teach people how to use the constraint solver. As I understand, we have someone working on UX, so I'll defer to them on this.

[frizensami]

Sounds good! I added a WIP PR so that we can prototype quickly.

Probably the two important things out of the lot above are:

• Whether this approach of downloading the solver binary is OK, and when to do it
• The UI/UX discussion

[frizensami]

Updated the PR with the current method i have of initializing the solver in z3w.wasm. A subset of changes:

Note: filenames are outdated, this has been simplified a bit

• The site now hosts two new static files: z3w.wasm (Z3 Solver binary) and z3w.js (emscripten wrapper for the wasm file)
• src/workers/z3Worker.ts is a WebWorker that uses importScripts to include z3w.js (this is how it's used in the z3.wasm GitHub project). It is responsible for starting and running Z3, which are CPU intensive operations. It hooks onto the solver's stdout/stderr and reports those values to src/utils/z3Manager.ts through callbacks
• src/utils/z3Manager.ts is the main utility for components to initialize and call the Z3 solver. While mostly commented out for now (just has the init workflow), it receives the timetable + constraints and handles the two-stage call procedure to the Z3 solver.
• Just added a basic button to the optimizer area to initialize the solver as a demo
• Added the worker-loader library to import WebWorkers

TLDR: usage of Z3 is controlled by
z3Manager --> [[ Webworker boundary ]] --> z3Worker (importing the wrapper z3w.js) --> z3w.wasm

[frizensami]

Just an update on this: slowly working on maximizing test coverage on all non-UI code. I just have converter.ts to go for utils. That will hopefully make it easier to iterate on the UI side without worrying about breakages.