Capstone Design Project

The Capstone Design Project, also known as the fourth-year design project (FYDP), is a mandatory three-course sequence in the software engineering program at the University of Waterloo. It spans twenty months, and is to be completed in groups of four undergraduate students.

My group, “Team Amalgam” (Joseph Hong, Chris Kleynhans, Atulan Zaman, and myself) worked under the supervision of Professor Derek Rayside, from approximately September 2012 to April 2014. Our project was to optimize the guided improvement algorithm, which is used to solve exact, discrete, multi-objective optimization problems.

On March 21 2014, a public symposium was held for all the projects done by the software engineering class of 2014. Each group had a booth with a poster and a demo, and gave a twenty-minute presentation about their project.

The sponsor selected our group, Team Amalgam, for first place.

I have a series of blog posts explaining the background for our project, as well as describing the work we have been doing.

• Introduction, Definition, and Applications
• A More Formal Definition
• The Guided Improvement Algorithm
• The Overlapping Guided Improvement Algorithm
• Attempting the Partitioned Guided Improvement Algorithm
• Fixing the Partitioned Guided Improvement Algorithm

Documents

As the fourth-year design project is a three-course sequence, we have had to prepare documents and presentations. I have consolidated the download links for all of our documents and slides.

SE 390

• Research plan
• Requirements specification
• Test plan
• Presentation (Google Docs)

SE 490

• Initial presentation (Google Docs)
• In-class presentation (Google Docs)
• Final presentation (Google Docs)

SE 491

• Symposium poster
• Symposium slides

Publications

• E. Zulkoski, C. Kleynhans, M.-H. Yee, D. Rayside, K. Czarnecki, Optimizing Alloy for Multi-objective Software Product Line Configuration, ABZ 2014, June 2014. (Link at Springer)
• M. Safa, M.-H. Yee, D. Rayside, C. T. Haas, Optimizing Contractor Selection for Construction Packages in Capital Projects, ASCE Journal of Computing in Civil Engineering, January 2016.

Test Infrastructure

We have unit tests running on Travis CI.

However, many of our tests take a long time to run, and besides correctness, we are interested in seeing how long it takes for our tests to run. We also want to track our progress in making the algorithms run faster.

This is why we designed and built custom infrastructure: the dashboard. It is built with Sinatra and runs on Heroku.

From the dashboard, we can upload test models to Amazon S3, request test runs via Amazon SQS, view our test results, and view the status of our workers. (Actually, we find it easier to request tests from the console instead of the web interface.)

Our workers, written in Ruby, run on the undergraduate computer science servers. When a job is received from SQS, they download the test model from S3 and the code from GitHub, build the project, and then run the tests. The workers will make POST requests to the dashboard, with events such as registrations and unregistrations, start and completion of tests, and heartbeats.

Finally, the dashboard is integrated with GitHub and HipChat. When we commit to the master branch of the moolloy repository, the dashboard is notified and initiates a number of short-running tests, as part of our continuous integration. The dashboard also sends messages to HipChat, so we get notifications of events.

Code Repositories

Most of our code can be found on GitHub.

Moolloy is our implementation. The repository is simply a “parent project” which uses Git submodules to keep the “child projects” in sync. The child projects are modified versions of Alloy and Kodkod. We do not own the Alloy code base and it is not publicly available, which is why we do not have it on GitHub.

Essentially, Alloy is the “front-end” and Kodkod is the “back-end” where the algorithms are actually implemented. Our version of Alloy takes in multi-objective optimization problems expressed in modified Alloy syntax, compiles it down to Kodkod, which then solves it by calling into a SAT solver. We’re currently using MiniSat.

The dashboard, worker, and test-models repositories collectively form our test infrastructure.

The documents repository is self-explanatory.

The results repository contains the raw experimental data we collected for the ABZ publication.

The demo repository holds the software for running our symposium day demo. Essentially, different versions of the algorithm race against each other, and results are plotted in real-time.