Timetabler

This project generates a timetable given a set of inputs and constraints. It encodes constraints of the timetabling problem as a SAT formula in the Conjunctive Normal Form, and then calls a MaxSAT solver to solve the problem.

Installation

For Ubuntu/Debian users: Download the deb for the latest version of Timetabler from here and install it.

To build the project from source follow the steps below.

Prerequisities

This project requires following tools to build.

• cmake (version 3.10 or higher)
• g++ or any other C++ compiler with C++11 support
• zlib (On ubuntu: sudo apt install zlib1g-dev)
• libgmp (On ubuntu: sudo apt install libgmp-dev)

Dependencies

The following software are dependencies for this program:

• Open WBO 2.1
• yaml-cpp 0.6.2
• CSVparser
• PEGTL 2.7.0
• GoogleTest 1.8.1 (Optional, needed only for testing)

Get the code

The most recent stable release can be downloaded from here.

To get the latest code, use

$ git clone https://github.com/sukrutrao/Timetabler
$ cd Timetabler

Setting up the dependencies

Short method

To set up all the dependencies required, simply run the following command

$ ./install_dependencies.sh

If building with tests, use instead

$ ./install_dependencies.sh --enable-tests

If the above command fails, you can try installing the individual dependencies manually by following the instructions below.

Long method

This describes the process of setting up each dependency.

Open WBO 2.1

This needs to be built as a library. The following steps need to be followed:

• Clone the repository. $OPEN_WBO_PATH will be used to denote the path where the repository is cloned.

$ git clone https://github.com/sat-group/open-wbo.git $OPEN_WBO_PATH
$ cd $OPEN_WBO_PATH

• Build as a static library

$ LIB=open-wbo make libr

CSVparser

This does not require any setup other than cloning the repository. The path where this is cloned will be referred to as $CSVPARSER_PATH.

yaml-cpp

• Download yaml-cpp-0.6.2 and unpack it. $YAML_CPP_PATH will be used to denote the path where it is unpacked.
• Build the project

$ cd $YAML_CPP_PATH
$ mkdir build && cd build
$ cmake ..
$ make

PEGTL

• Download PEGTL 2.7.0 and unpack it. $PEGTL_PATH will be used to denote the path where it is unpacked.
• Build the project.

$ cd $PEGTL_PATH
$ mkdir build && cd build
$ cmake ..
$ make

GoogleTest

• Download GoogleTest 1.8.1 and unpack it. $GTEST_PATH will be used to denote the path where it is unpacked.
• Build the project

$ cd $GTEST_PATH
$ mkdir build && cd build
$ cmake ..
$ make

Building the project

• Build the project. Set the cmake variables OPEN_WBO_PATH, YAML_CPP_PATH, CSVPARSER_PATH and PEGTL_PATH appropriately.

$ mkdir build && cd build
$ cmake -DOPEN_WBO_PATH="../dependencies/open-wbo" -DYAML_CPP_PATH="../dependencies/yaml-cpp-yaml-cpp-0.6.2" -DCSVPARSER_PATH="../dependencies/CSVparser" -DPEGTL_PATH="../dependencies/PEGTL-2.7.0" -DENABLE_TESTS=Off ..
$ make timetabler

If building with tests, set GTEST_PATH appropriately and use

$ mkdir build && cd build
$ cmake -DOPEN_WBO_PATH="../dependencies/open-wbo" -DYAML_CPP_PATH="../dependencies/yaml-cpp-yaml-cpp-0.6.2" -DCSVPARSER_PATH="../dependencies/CSVparser" -DPEGTL_PATH="../dependencies/PEGTL-2.7.0" -DGTEST_PATH="../dependencies/googletest-release-1.8.1" -DENABLE_TESTS=On ..
$ make timetabler

• To run tests

$ make tests # Build tests
$ make test # Run tests

• Install

$ make install

Running the Timetabler

To execute the program, use

$ timetabler -f fields.yml -i input.csv -c custom.txt -o output.csv

where

• fields.yml is the path to the file containing the list of values a field can take and the weights for the constraints. This includes list of instructors, available classrooms, weights of clauses, etc.
• input.csv is the path to the file containing the input data. This file contains the course data input given to the solver as a CSV file.
• custom.txt is the path to the file containing the list of custom constraints. This file contains the custom constraints that can be provided to the solver using the grammar provided. For the full grammar, please refer to the Project Wiki.
• output.csv is the path to the file to which the output must be written to.

A detailed explanation on each file can be found in the Project Wiki.

For more options, see help

$ timetabler -h

Examples of Configuration files

Examples for configuration files can be found here. This contains some examples for the field information, the input, and custom constraints to be added to the solver.

For further details and examples, please refer to the Project Wiki.

Documentation

The project web page is sukrutrao.github.io/Timetabler.

Code documentation for this project can be found on Read the Docs.

Issues

If you have any queries, suggestions, or feature requests, or would like to report any bugs or issues, please open an issue on GitHub.

When reporting bugs, please provide sufficient information (such as the inputs and the configuration used) to reproduce the bug.

Contributing

To contribute to this project, please send a pull request.

License

This software is provided under the MIT License.