Matrices, domains

About matrices

Sometimes it is useful if resources of one resource type can be arranged in a two dimensional array. The most common example of this is when you have a fixed number of time slots per day and a fixed number of days per week. Such resource types are called matrix resource types or matrices.

All resources in a matrix always have special names in the form of two integers separated by a single space. First integer gives the column index (x coordinate) and the second integer gives the row index (y coordinate). Resources in a matrix are also always ordered first by rows and then by columns (see res_new_matrix() function documentation for more information).

Modified module

Let's say we want to modify the previous example module so that we could define only the row of a resource an event will be using, not the exact resource. We will also modify the module so that it will be using resource domains, a new feature in 0.2.x kernels.

#include <stdio.h>
#include <stdlib.h>
#include "module.h"

#define        RESTYPE                "dummy-type"

static resourcetype *dummy;
static int width, height;

int handler(char *restriction, char *content, tupleinfo *tuple)
{
        int row;
        int result;
        int typeid;

        int *resid_list;
        int resid_num;

        int n;

        domain *dom;

        result=sscanf(content, "%d", &row);
        if(result!=1) {
                error(_("Row index must be an integer"));
                return -1;
        }

        if(row<0||row>height-1) {
                error(_("Row index must be between 0 and %d"), height-1);
                return -1;
        }

        typeid=dummy->typeid;

        resid_list=malloc(sizeof(*resid_list)*width);
        if(resid_list==NULL) {
                error(_("Can't allocate memory"));
                return -1;
        }

        for(n=0;n<width;n++) resid_list[n]=row+n*height;
        resid_num=width;

        dom=tuple->dom[typeid];

        domain_and(dom, resid_list, resid_num);

        free(resid_list);
        
        return 0;
}

int module_init(moduleoption *opt)
{
        int result;

        dummy=restype_find(RESTYPE);
        if(dummy==NULL) {
                error(_("Resource type '%s' not found"), RESTYPE);
                return -1;
        }

        result=res_get_matrix(dummy, &width, &height);
        if(result) {
                error(_("Resource type " RESTYPE " is not a matrix"));
                return -1;
        }

        if(handler_tup_new("row-" RESTYPE, handler)==NULL) return -1;

        return(0);
}

Module initialization

First thing you might notice is that this module doesn't define a fitness function. Because of this module initialization function is pretty straightforward. First we try to find our resource type. Then we use the res_get_matrix() function to get the dimensions width and height of the matrix. It is important that we check whether the resource type is really a matrix: res_get_matrix() will return -1 if it cannot determine the dimensions and 0 on success. The last thing in the initialization is the familiar call to handler_tup_new() to define a new tuple restriction handler.

Restriction handler

As you can see the important part of the code is this time in the restriction handler. Instead of using a fitness function to tell the genetic algorithm which timetables are better we will simply narrow the search space of the genetic algorithm. This of course means that it is impossible to make a non-mandatory restriction with this approach. As far as the genetic algorithm is concerned, timetables that do not satisfy our restriction are not even considered for a solution.

If you look at the restriction handler code you can see that we first read the row number specified by the user and do a check if it falls within the allowed range. Then we make a list of all resource IDs our event can use. Since we know in which row the allowed resources must be and we know how resources are ordered in a matrix it is quite straightforward to construct it.

Array resid_list holds the resource ID values and integer resid_num holds the length of the array. There are exactly width resources in a row, so we can set the length immediately. Resources are ordered first by row numbers and then by column numbers. So the first resource in the row row has the ID equal to row. The distance to the second resource is exactly height resources.

Now we pass the list of allowed resource to the domain_and() function. This function takes a resource domain and a list of resources as its arguments. Then it removes all resources from the domain that aren't also in the list. Note that this effectively narrows the search space to the lowest common denominator of all restrictions of this type, even those defined by other modules using domain_and() function.

Pointers to domain structures for the tuple the restriction handler was called for can be found in the tupleinfo structure. The dom structure field contains an array of pointers to domain structures, ordered by resource type ID. Because of this we must first obtain the resource type ID for our "dummy-type" resource type. Since we already have a pointer to that type, we can simply read the type ID from the type field.

Testing the module

Again we can construct a simple test case to check if the module is working correctly:

<?xml version="1.0" encoding="iso-8859-1"?>
<ttm version="0.2.0">
        <modules>
                <module name="row.so" weight="10" mandatory="yes"/> 
        </modules>

        <resources>
                <variable>
                        <resourcetype type="dummy-type">
                                <matrix width="10" height="10"/>
                        </resourcetype>
                </variable>
        </resources>

        <events>
                <event name="dummy-event" repeats="1">
                        <restriction type="row-dummy-type">3</restriction>
                </event>
        </events>
</ttm>

If you run Tablix on it and check one of the result files you will get a result similar to this one:

<event name="dummy-event" repeats="1" tupleid="0">
        <restriction type="row-dummy-type">3</restriction>
        <resource type="dummy-type" name="4 3"/>
</event>

You can see that the row of the chosen resource (second number in the resource name) is equal to the requested row of resources. If you run Tablix a couple of times with this same configuration file and compare the results you will see that the column of the resource is chosen randomly while the row will always stay the same.

Discussion

You should always use resource domains in your module if it is at all possible. Because this way you are limiting the search space Tablix will find the solution faster if there are more restrictions like this. On the other hand if there are more restrictions that are using fitness functions Tablix will need more time because it takes time to evaluate timetables with more fitness functions.

Also Tablix will detect if a domain does not contain any resources. This means that the user has applied an impossible combination of restrictions to an event and that a solution can not be found. This is one of the few cases where Tablix can predict that a solution to the problem described in the configuration file does not exist. On the other hand an impossible combination of restrictions that are using fitness functions is in most cases impossible to detect automatically.