Inside Class Cruncher

You’ll find here the concepts used to create Class Cruncher, a handy webapp for school administrators.

The problem

How should you deploy a certain number of teachers across your school’s classes, given rules about class sizes? You may need to use composite classes.

More precisely, given:

• The total number of teachers
• How many children are in each grade
• Min & max class sizes in each grade
• Which composite classes are allowed (eg. grades 1 & 2 but not grades 1 & 3 together)
• The smallest number of children from a grade allowed in a composite class (eg. so you don’t have a single lonely first grader in a class with grade 2).

Then list out the classes that each teacher should take (i.e. how many children from each grade are in each class).

A solution

Solve this as a mixed-integer linear programming problem, using lpsolve. This uses the simplex and branch-and-bound algorithms to maximise an objective function subject to some constraints. Here we have lots of constraints, and just want a feasible solution, rather than an “optimal” solution, so the objective function is not so important.

For every potential class j, we’ll have a binary variable y(j) (ie. it must be either 0 or 1), to tell us if it is being used or not.

Because classes can include students from different grades, we will invent the term “subclass” to refer to the number of children from one particular grade in a class. Then our key variables are x(i), the number of children in each potential subclass i.

Let’s relate the classes and subclasses via a matrix C(j,i), with 1 if subclass i is in class j, and 0 otherwise. Since subclasses are only in a single class, for any subclass i, C(j,i) is 1 for only one class j. So C is mostly 0s, with each row having at least one 1, and no columns having more than one 1.

Then the number of children in class j = the sum over i of C(j,i).x(i).

(In matrix notation, Cx = number of children in each class, where x and the right hand side are column vectors.)

C(j,i) also tells us if subclass i is being used: it is given by the sum over j of C(j,i).y(j).

Recall that y(j) tells us if class j is being used. Also, for a given subclass i, C(j,i) is only 1 for a single class j, so the sum is just a single term.

(In matrix notation, C’y = binaries telling if each subclass is used, where C’ is the transpose of C.)

For example: Suppose you have 3 grades (kindergarten, 1 and 2), and can allow for 1 pure kindy class, 2 composite K/1 classes, 2 pure 1st grade and 1 pure 2nd grade class. That’s a total of 6 classes and 8 subclasses. The matrix C is:

—-8 subclasses—–
| 1 . . . . . . .
| . 1 1 . . . . .
6 . . . 1 1 . . .
classes . . . . . 1 . .
| . . . . . . 1 .
| . . . . . . . 1

To simplify the model, we’ll assume potential composite classes cannot optionally only use some of their subclasses – it’s all or nothing.

So in fact, we also need a preliminary step (before solving) to decide on the number of potential classes and subclasses from the input data. We can make a guess at an upper limit, eg. by dividing the number of children in each grade by the maximum number allowed in a class, and rounding up.

Our constraints need to achieve these things:

1. Ensure all the children in each grade are in a class (or equivalently, a subclass)
2. Classes sizes must be between the minimum and maximum class size – or zero (since not all potential classes need to be used!)
3. Subclass sizes must be above the minimum subclass size, if the class is being used
4. The number of classes must match (or be less than) the number of available teachers

We also need to relate the x and y variables. In a linear program, all the constraints need to be linear in the variables z. This means you can express them as matrices A, so that A.z is greater than, equal to, or less than, another vector c. Here z is just a column vector containing both x and y.

Take each of the above in turn.

Ensure all the children in each grade are in a class (or equivalently, a subclass)

We have to express this in terms of the number of children in the subclasses x, because the y’s don’t tell us how many children there are in each class.

In our earlier example, the first point involves 3 constraints, one for each grade. Multiply the below matrix with the column vector x (which has 8 rows).

—-8 subclasses—– sums to
| 1 1 . 1 . . . . = number of kindergarteners
3 grades . . 1 . 1 1 1 . = number of first graders
| . . . . . . . 1 = number of 2nd graders

Classes sizes must be between the minimum and maximum class size, or zero

If we had to use every potential class (ie. all the y variables were known to be 1), then this is just the constraint Cx >= min_class_size, Cx <= max_class_size (where I’m applying the inequality to each row of each side, so these are 6+6=12 constraints in our example.)

However, Cx >= min_class_size should only apply if y is 1. That’s easy to write: Cx – min_class_size.y >= 0. So the constraint matrix has C (N_classes × N_subclasses or 6×8) on the left and -min_class_size (N_classes × N_classes or 6×6, a diagonal matrix of the minimum class sizes) on the right.

I make the same modification for the max class sizes, although it’s not strictly necessary; this has the effect of forcing y >= 0.

Subclass sizes must be above the minimum subclass size, if the class is being used

If we had to use every potential class (ie. all the y variables were known to be 1), and therefore every subclass, then this is a very simple set of constraints: x >= min_subclass_size. However, we only want this constraint to apply if the corresponding binary value is 1. That corresponding y is actually the corresponding row of C’y (as we discussed earlier).

There’s a classic trick to only apply constraints based on the value of a binary variable, called the “big M” method.

Write x >= min_subclass_size as (x – min_subclass_size) >= 0, and then replace the right hand side with M(C’y – 1), where M is a big number (eg. 10000). Now when C’y is 1, the constraint applies; when it is 0, it does not. Cool!

The number of classes must match (or be less than) the number of available teachers

The last constraint is easy – the sum of the y’s must be less than or equal the number of teachers; the x’s don’t come into it.

Do we need to explicitly constrain y to be binary?

Certainly all our variables need to be integers, not floating point. But y already can’t be bigger than 1, because our big M constraint would fail. And it can’t be less than 0 because of the way we wrote our max class size constraint.

So y is already forced to be binary.

Matrix representation of the constraints

```A:  (integer vars)      (binary vars)                     b:
-- num_subclasses -- -- num_classes --
(--------------------+-----------------)                  (--------------)
(                    |                 )      |           (       |      )
(                    |                 )      |           (       |      )
(--------------------+-----------------)                  (--------------)
(                    |-l1              )      |           (       |      )
( class_size_matrix  |     (diag.)     )  num_classes >=  (       0      )
(                    |             -lnc)      |           (       |      )
(--------------------+-----------------)                  (--------------)
(                    |-u1              )      |           (       |      )
( class_size_matrix  |     (diag.)     )  num_classes <=  (       0      )
(                    |             -unc)      |           (       |      )
(--------------------+-----------------)                  (--------------)
( 1                  |                 )      |           (       |      )
(     1              |                 )      |           (       |      )
(        ...         |     -M * C'     ) num_sub_classes>=(    ls - M    )
(              1     |                 )      |           (       |      )
(                  1 |                 )      |           (       |      )
(--------------------+-----------------)                  (--------------)
(         0          | 1 1   ...   1 1 ) num_classes =,<= ( max_classes  )
(--------------------+-----------------)                  (--------------)

where l is the min_class_size
u is the max_class_size
ls is the min_subclass_size
C' is the transpose of the class_size_matrix
M is a large number
```

Step 3: Choose the objective function

For a single answer, I just minimise the sum of all the x(i).

Ideally you could get second-best and other feasible solutions from the solver, but I had trouble doing this. As a work-around, I produce different solutions by changing the weights on each subclass. I raise the weight from 1 to 2 for the subclasses in a given grade or composite class, and repeat.

Step 4: Express the solution in an understandable way

We recast the resulting x and y values so that people can understand them, eg. in our example with 8 subclasses we might get an answer like

```--------------- x ----------- ------- y -------
[20, 12, 10, 0, 0, 25, 22, 21, 1, 1, 0, 1, 1, 1]
```

This is more easily understood as being 5 classes with the following compositions:

```           K  1st 2nd
class #1: 20,  0,  0
class #2: 12, 10,  0
class #3:  0, 25,  0
class #4:  0, 22,  0
class #5:  0,  0, 21
```

Step 5: Post-process to humanise the answers

The optimisation produces often solutions with very different numbers of students in each class, eg. two kindergarten classes, one with 10 students, and one with 20. Clearly, a better solution is two classes of 15.

As is often the case, the constraints we thought we needed don't quite fully give us the solutions we expected.

We could tackle this by adding more constraints or changing the objective function, but in this case it is simpler to do some "shuffling" after the optimisation, according to some prescribed rules.

Composite classes make this a bit harder. For another example, given the formatted output (note the composite classes are listed at the end):

```[[10,0,0], [20,0,0], [0,25,0], [0,0,10], [25,5,0], [0,5,25]]
```

We could return:

```[[21,0,0], [21,0,0], [0,22,0], [0,0,20], [13,8,0], [0,5,15]]
```

The rules I came up with took some discovering:

1. For each grade, find the average class size of classes with subclasses from that grade. (In the above example, it's 20, which includes 5 grade 1s in the comp class)
2. For each grade, move that grade's students around to make them as close to this average as possible, eg:
• kindergarten: avg = 20;

`[[20,0,0], [20,0,0], [0,25,0], [0,0,10], [15,5,0], [0,5,25]]`

• grade 1: avg = (25+20+30)/3 = 25; in the example, this cannot be done, since the last class is the problem.
• grade 2: avg = (10+30)/2 = 20,

`[[20,0,0], [20,0,0], [0,25,0], [0,0,20], [15,5,0], [0,5,15]]`

3. Repeat until class sizes only change by 1, eg:
• kindergarten: avg = 20, no shuffling required
• grade 1: avg = (25+20+20)/3 = 21.7;

`[[20,0,0], [20,0,0], [0,22,0], [0,0,20], [15,7,0], [0,6,15]]`

• grade 2: avg = (20+21)/2 = 20.5, no change required
• kindergarten: avg = (20+20+22)/3 = 20.7,

`[[21,0,0], [20,0,0], [0,22,0], [0,0,20], [14,7,0], [0,6,15]]`

• etc

Step 6: Build it!

Build a web app to take the inputs, perform the optimisation and serve the results!

Asynchronous calls from Django

I have an optimisation I would like to run when the user presses a button on a Django page. For small cases, it is fine to run it synchronously.  However, when it takes more than a second or so, it is not great to have the web server held back by a process of unknown length.

The solution I have settled on is Celery, with Redis as the message broker.  I am using Redis over the alternatives, since it seems to have much lower memory requirements (I find it uses under 2 Mb, vs. 10-30 Mb per Celery process). And the equivalent commands if you want to use redis-queue (which uses about 10 Mb per worker) instead of Celery are given in this post.

There is a bit of a learning curve to get started with this, so I am making a guide for the next person by listing all the steps I have taken to get set up on both my development platform (running MacOS X) and a unix server (hosted by Webfaction).  Along the way I hope to answer questions about security and what the right settings are to put in the `redis.conf` file, the celery config file, and the usual Django `settings.py` file.

Install Redis

Redis is the message broker. You will need to have this running at all times for Celery’s tasks to be executed.

Installing Redis on Mac OS X is described in this blog. Basically, just download the latest version from redis.io, and in the resulting untarred directory:

```make test
make
sudo mv src/redis-server /usr/bin
sudo mv src/redis-cli /usr/bin
mkdir ~/.redis
touch ~/.redis/redis.conf```

Installing Redis on your server is similar, though you may need to know how to download the code from the command line first (e.g. see this post):

```wget http://redis.googlecode.com/files/redis-2.6.14.tar.gz
tar xzf redis-2.6.14.tar.gz
cd redis-2.6.14
make test
make```

On the production server we don’t need to relocate the `redis-server` or `redis-cli` executables, as we’ll see in the next section.

Run Redis

To run Redis on your Mac, just type one of:

```redis-server  # if no config required, or:
redis-server ~/Python/redis-2.6.14/redis.conf```

To run it on your Webfaction server, first add a custom app listening on a port, and note the port number you are assigned.

Now we need to daemonize it (see this post from the Webfaction community). In summary, in your redis directory, edit the `redis.conf` file like so (feel free to change the location of the `pid` file):

```daemonize yes
...
...
port xxxxx   # set to the port of the custom app you created```

To test this works, type the commands below. If all is well, the `pid` file will now contain a process id which you can check by providing it to the `ps` command.

```src/redis-server redis.conf
ps xxxxx # use the number in the pid file```

Note – when I did this without assigning the port number of the custom app, I got the following error:

```# Warning: no config file specified, using the default config. In order to specify a config file use src/redis-server /path/to/redis.conf
# Unable to set the max number of files limit to 10032 (Operation not permitted), setting the max clients configuration to 4064.

It turns out someone else was already using port `6379`, the default Redis port.

Now in practice you will want Redis to be managed with `cron`, so that it restarts if there is a problem. Webfaction has some docs on how to do this here; I used:

```crontab -e
# and add this line to the file, changing the path as necessary:
0,10,20,30,40,50 * * * * ~/webapps/redis/redis-2.6.14/src/redis-server ~/webapps/redis/redis-2.6.14/redis.conf```

FYI, for me the running Redis process uses 1.7 Mb (i.e. nothing compared to each celery process, as we’ll see).

Install Celery

The Celery docs cover this.  Installation is simple, on both development and production machines (except that I install it in the web app’s environment with Webfaction, as explained here):

`pip install django-celery-with-redis`

I have added the following to `settings.py`, replacing the port number for production:

```BROKER_URL = 'redis://localhost:6379/0'
CELERY_RESULT_BACKEND = 'redis://localhost:6379/0'

import djcelery

INSTALLED_APPS = (
...
'djcelery',
...
)
```

And added the suggested lines to the top of `wsgi.py`:

```import djcelery

I found lots more detail here, but I haven’t yet established how much of this is required.

Run a Celery worker

Now you need to start a Celery worker.

On your development server, you can enter your Django project directory and type:

`python manage.py celery worker --loglevel=info`

On your production server, I started by trying the same command above, to test out whether Celery could find the Redis process and run jobs – and it worked fine.  But in practice, the Celery docs say: “you will want to run the worker in the background as a daemon“.  (Note this link also talks about Celery beat, which “is a scheduler. It kicks off tasks at regular intervals, which are then executed by the worker nodes available in the cluster.” In my case, I do not need this.)

To do this, I copied the CentOS `celeryd` shell script file from the link at the end of the daemonization doc (since the server I am using runs CentOS), and placed it in a new `celerydaemon` directory in my Django project directory, along with the Django celeryd config file (I renamed the config file from `celeryd,` which was confusing as it is the same name as the shell script, to `celery.sysconfig`). I also created a new directory in my home directory called `celery` to hold the `pid` and `log` output files.

One more change is required, at least if you are using Webfaction to host your site: the call to `celery_multi` does not have a preceding python command by default.  While this works in an `ssh` shell, it does not work with `cron` - I believe because the `\$PATH` is not set up the same way in `cron`.  So I explicitly add the `python` command in the front, including the path to python.

The config file looks like this:

```# Names of nodes to start (space-separated)
CELERYD_NODES="myapp-node_1"

# Where to chdir at start. This could be the root of a virtualenv.

# How to call celeryd-multi (for Django)
# note python (incl path) added to front
CELERYD_MULTI="/home/user/bin/python \$CELERYD_CHDIR/manage.py celeryd_multi"

# Extra arguments
#CELERYD_OPTS="--app=my_application.path.to.worker --time-limit=300 --concurrency=8 --loglevel=DEBUG"
CELERYD_OPTS="--time-limit=180 --concurrency=2 --loglevel=DEBUG"
#  If you want to restart the worker after every 3 tasks, can use eg:
#  (I mention it here because I couldn't work out how to use

# Create log/pid dirs, if they don't already exist
CELERY_CREATE_DIRS=1

# %n will be replaced with the nodename

# Workers run as an unprivileged user
CELERYD_USER=celery
CELERYD_GROUP=celery

# Name of the projects settings module.
export DJANGO_SETTINGS_MODULE="myproject.settings"```

In the shell script, I changed the two references to `/var` (`DEFAULT_PID_FILE` and `DEFAULT_LOG_FILE`) and the reference to `/etc` (`CELERY_DEFAULTS`) in the shell script to directories I can write to, e.g.:

```DEFAULT_PID_FILE="/home/username/celery/%n.pid"
...

I found a problem in the CentOS script – it calls `/etc/init.d/functions`, which resets the `\$PATH` variable globally, so that the rest of the script cannot find python any more. I have raised this as an issue, where you can also see my workaround.

To test things out on the production server, you can type (use `sh` rather than `source` here because the script ends with an exit, and you don’t want to be logged out of your `ssh` session each time):

`sh celerydaemon/celeryd start`

and you should see a new `.pid` file in `~/celery` showing the process id of the new worker(s).

Type the following line to stop all the celery processes:

`sh celerydaemon/celeryd stop`

Restart celery with cron if needed

As with Redis, you can ensure the celery workers are restarted by `cron` if they fail. Unlike with Redis, there are a lot of tricks here for the unwary (i.e. me).

1. Write a script to check if a celery process is running. Webfaction provides an example here, which I have changed the last line of to read:
`sh /home/username/webapps/webappname/projectname/celerydaemon/celeryd restart`
2. This is the script we will ask `cron` to run. Note that I use `restart` here, not `start`; I am doing this because I have found in a real case that if the server dies suddenly, celery continues to think it is still running even when it isn’t, and so `start` does nothing. So add to your crontab (assuming the above script is called `celery_check.sh`):
```crontab -e
1,11,21,31,41,51 * * * * ~/webapps/webappname/projectname/celerydaemon/celery_check.sh```
3. One last thing, pointed out to me in correspondence with Webfaction: the `celeryd` script file implements `restart` with:
``stop && start``

So if `stop` fails for any reason, the script will not restart celery.  For our purposes, we want `start` to occur regardless, so change this line to:

`stop; start;`

Your celery workers should now restart if there is a problem.

Controlling the number of processes

If you’re like me you are now confused about the difference between a node, a worker, a process and a thread. When I run the `celeryd start` command, it kicks off three processes, one of which has the pid in the node’s `pid` file. This despite my request for one node, and “`--concurrency=2`” in the config file.

When I change the `concurrency` setting to 1, then I get two processes. When I also add another node, I get four processes.

So what I assume is happening is: workers are the same things as nodes, and each worker needs one process for overhead and “`concurrency`” additional processes.

For me, at first I found each celery process required about 30-35Mb (regardless of the number of nodes or concurrency). So three use about 100Mb.  When I looked again a week later, the processes were using only 10 Mb each, even when solving tasks.  I’m not sure what explains the discrepancy.

Use it

With this much, you can adapt the Celery demo (adding two numbers) to your own site, and it should work.

On my site I use ajax and javascript to regularly poll whether the optimisation is finished. The following files hopefully give the basic idea.

`urls.py`

```# urls.py
from myapp.views import OptView, status_view
...
url(r'^opt/', OptView.as_view(), name="opt"),
url(r'^status/', status_view, name="status"), # for ajax
...
```

`views.py`

```# views.py
import json
from django.views.generic import TemplateView
from django.core.exceptions import SuspiciousOperation
from celery.result import AsyncResult

class OptView(TemplateView):
template_name = 'opt.html'

def get_context_data(self, **kwargs):
"""
Kick off the optimization.
"""
# save the task id so we can query its status via ajax
# if you need to cancel the task, use:
context = super(OptView, self).get_context_data(**kwargs)
return context

def status_view(request):
"""
Called by the opt page via ajax to check if the optimisation is finished.
If it is, return the results in JSON format.
"""
if not request.is_ajax():
raise SuspiciousOperation("No access.")
try:
except KeyError:
ret = {'error':'No optimisation (or you may have disabled cookies).'}
return HttpResponse(json.dumps(ret))
try:
# to do - check if it is really solved, or if it timed out or failed
ret = {'status':'solved'}
# replace this with the relevant part of the result
ret.update({'result':result})
else:
ret = {'status':'waiting'}
except AttributeError:
ret = {'error':'Cannot find an optimisation task.'}
return HttpResponse(json.dumps(ret))
return HttpResponse(json.dumps(ret))
```

`javascript`

```// include this javascript in your template (needs jQuery)
// also include the {% csrf_token %} tag, not nec. in a form
\$(function() {
function handle_error(xhr, textStatus, errorThrown) {
clearInterval(interval_id);
}

function show_status(data) {
var obj = JSON.parse(data);
if (obj.error) {
clearInterval(interval_id);
}
if (obj.status == "waiting"){
// do nothing
}
else if (obj.status == "solved"){
clearInterval(interval_id);
// show the solution
}
else {
clearInterval(interval_id);
}
}

function check_status() {
\$.ajax({
type: "POST",
url: "/status/",
data: {csrfmiddlewaretoken:
document.getElementsByName('csrfmiddlewaretoken')[0].value},
success: show_status,
error: handle_error
});
}

setTimeout(check_status, 0.05);
// check every second
var interval_id = setInterval(check_status, 1000);
});
```

As mentioned in the comments to the code above, if you need to cancel an optimisation, you can use:

`revoke(task_id, terminate=True)`

Monitoring

You can monitor what’s happening in celery with celery flower, at least on dev:

```pip install flower
celery flower --broker=redis://localhost:PORTNUM/0```

And then go to `localhost:5555` in your web browser.

When you use `djcelery`, you will also find a `djcelery` app in the admin panel, where you can view workers and tasks.  There is a little bit of set up required to populate these tables.  More info about this is provided in the celery docs.

Security

• http://redis.io/topics/security
• http://docs.celeryproject.org/en/latest/userguide/security.html

I hope that’s helpful – please let me know what you think.

Install lpsolve for Python

Today I wanted to try out using lpsolve with the python API on my Mac (OS X 10.7) and on my linux server.

Installing it on the Mac is tricky, but the essence is described in this blog post (here I clarify a few things that stumped me for a while, leave out some of the changes mentioned there that I didn’t need to do, and update a path or two):

• `lp_solve_5.5.0.15_source.tar.gz`
• `lp_solve_5.5.0.15_Python_source.tar.gz`

e.g. from sourceforge (I originally got a different version of one of these, and it did something quite different).

• The first will extract to a folder `lp_solve_5.5`. The second will extract to a folder with the same name, however it will only contain an `extra/Python` directory. Copy this extra directory into the first download’s `lp_solve_5.5` folder.
• `cd` into this `lp_solve_5.5` directory.
• `cd lpsolve55`
• `sh ccc.osx` . You will get a lot of warnings, but that’s ok. This will create a `bin/` directory. On my Mac it has a subdirectory `osx64/`, containing `liblpsolve55.a` and `liblpsolve55.dylib`.
• `sudo cp bin/osx64/liblpsolve55.a bin/osx64/liblpsolve55.dylib /usr/local/lib` (this step courtesy of this blog)
• `cd ../extra/Python`
• You now need to edit `setup.py`, as suggested in the blog post above (here I have updated the included directories to reflect current Xcode practice):
```...
LPSOLVE55 = '../../lpsolve55/bin/osx64' # not ux32
...
ext_modules = ...
...
include_dirs = ['../..', '/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk/usr/include', '/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk/usr/include/malloc'],
...
```

You may also want to update the version number (5.5.0.8) in `setup.py`, which does not match the originally downloaded files (5.5.0.15); I’m not sure which is correct.

• `python setup.py build`
• `python setup.py install` . This writes out …`/lib/python2.7/site-packages/lpsolve55-5.5.0.8-py2.7.egg-info` (in my case into my virtualenv)
• `>>> from lpsolve55 import *` should now work in python.

Once this was working, I also installed `lpsolve` on my linux (CentOS) server. I followed the same steps there, except I executed the straight `ccc` file rather than `ccc.osx` (I changed it to refer to `~/tmp` instead of `/tmp`, since I’m using shared hosting and cannot execute from `/tmp`). On linux there is no need to change the `setup.py` file. And I did not find it necessary to copy the `.a` or `.dylib` files anywhere.

If you’re using WebFaction, you will also want to change the final `install` command (as described here), to:

```python setup.py install --install-lib=\$HOME/webapps/web_app/lib/python2.7 \
--install-scripts=\$HOME/webapps/web_app/bin \
--install-data=\$HOME/webapps/web_app/lib/python2.7```

This also worked.

Hope that helps someone out there – let me know if you have any comments.