Category: constraints

I was originally planning to write a quick-and-dirty implementation of the simplex algorithm myself to demonstrate some of the gritty details, but I decided to leave that kind of thing for later, since there are going to be other, less well-known, constraint solving algorithms that I want to look at . There is a Haskell implementation of a simple version of simplex algorithm in the Matrix.Simplex module in the dsp package, although that comes with a comment that says "I only guarantee that this module wastes inodes", so let's view this more as a way to play with some interface issues than a serious attempt to implement any kind of constraint solver! The code that goes with this article is available here.

Pathetically slow in starting work on my little constraints project as I am, here's the first of what should be a long series of posts...

One of the constraint solvers I'm looking at starting from, Cassowary, uses what is essentially an extended version of one of the most venerable of optimisation algorithms, Dantzig's simplex algorithm. I'm going to start off thinking a little bit about the general setup of the kind of linear programming problems that the simplex algorithm is designed to solve, just to get a geometrical feeling for how these algorithms work and to understand the issues that might arise from relaxing some of the assumptions used in them.

I've recently started making some tiny contributions to Brent Yorgey's Haskell diagrams library, mostly bug fixes. The bug fixes are primarily just a way of familiarising myself with the diagrams codebase though. I have my eye on a rather chunkier task in the open issues list. That's writing a constraints solver for diagram layout. I've been interested in this sort of problem for some time, and have never had a good reason to get down to it, so I'm going to see what I can come up with.

And I'm going to try something I've not done before, which is to document experiments, design and development as blog articles. It may all turn out to be hideously embarrassing, it may end up that none of what I do actually makes it into the mainstream of the diagrams library, but having to write about what I'm doing will keep me honest, force me to be clear about what I'm doing, and will provide an incentive to work on this stuff.