Kevin Lynagh challenge

Just read this in Kevin Lynagh’s blog and thought it might be a nice puzzle to solve in Alloy.

A mechanical engineering friend of mine is designing a system that involves pumping a series of fluids through a column, where, uh, special chemistry stuff happens.

Each fluid has its own tank and valve, but they’re all slurped by a shared pump, something like:

A --x–|
B --x–|
| |-- Diversion – …
C --x–|— Pump —x
|---- Column — …
where A, B, C are fluid tanks and each x is a valve.

There are a few tricky constraints:

Bubbles will mess up the process, so the system must be “primed” before use: Liquid from each tank must be slurped one-by-one and pushed through a diversion line to remove air from the tubes.

Some fluids conflict with each other (e.g., explode on contact).

The fluids must be run through the column in a specific order.

The problem is to find an assignment of fluids to tanks and corresponding priming order that satisfies the constraints. In this toy example, if A and C conflict and the column order is A, B, C, a solution for the physical arrangement drawn above is to first pump C through the diversion, then B, then pump A through the column, then B, then C.

Of course, my friend’s problem is a bit more complex, with more fluids and additional dimensions (e.g., expensive fluids should have minimal “dead volume” — the length of tube between their tanks and the column/diversion).

Long-time readers probably have a guess about what technique I’ll try to use to solve this problem, though I’m not at all sure how well it’ll work.

If you have any suggestions or, even better, want to show me how you’d code up the toy problem above, I’d love to hear!

I’ll be back next month with (hopefully) a fun solution.

Until then!