Practical Problem Solving

I frequently read announcements or descriptions for software that sound interesting, except that I have no real reason to use them.  When I do find a reason to use one, it has often been so long that I have only a vague recollection of the item in question.  In the most recent such case, I found myself with a set of inequalities for which I wanted sample solutions.  I seem to remember something called a “master system” that could solve problems, but perhaps not that particular kind of problem.  However, that phrase is particularly resistant to searching, so I completely failed to find the page in question.

Fortunately, I managed to find a few other relevant items with a slightly different search.  The documentation for Minion and the python-constraint module each seemed to be exactly what I wanted.  In fact, each could easily solve a small-scale version of my problem, within a second or two.  However, each would spend more than a day on the full-scale problem without any apparent progress toward a solution.

Perhaps it was jumping from 3 to 12 variables on each side of the inequality.  Perhaps it was jumping from 5 to 11 constraints.  Either way, it became apparent that the generic problem solvers just weren’t cutting it, even on the very simplest of my full-scale problems.  Even more frustrating was that I had been able to solve a more complex one by hand in less than an hour or two; I might even still have the spreadsheet somewhere.

Fortunately, I knew that my constraints followed exactly two simple patterns: Each constraint was either a strict equality or inequality, and each side was a sum of non-negative integer variables.  Minion in particular has far more types of constraints to deal with, so I was confident that a simpler solution, with hard-coded heuristics specific to the problem domain, could be much faster.

I also had my own experience solving one as a guide.  However, one of the techniques I employed was a sort of eyeballing:  I looked at which variables contributed to the rows I wanted to increase but not the rows that needed to be kept down.  That sort of vague educated guessing certainly wasn’t going to work for a computer…

Fortunately, the computer has an important resource that I lack:  The ability to keep all sorts of sums in memory at once.  In this case, I was able to simulate my eyeballing maneuver by adding up the errors in each equation to which a given variable contributes.  Comparison of those sums gives me a set of good candidates for increasing or decreasing.  As a fortunate side effect, those sums also tell me when a solution has been reached:  All of the errors are zero.

Amazingly enough, this leads to a program that can solve even my full-scale problems in a second or two.  The easy ones take only a few iterations, particularly with the optional extra constraints enabled.  I can even increase the scale to the next level, with 60 variables on each side of 18 constraints, and the problem is solved before I can even think about getting impatient.

If it gets solved at all.  My new solver has an unfortunate habit of manipulating a limited set of variables in an infinite loop.  Sometimes it flips each one between a single pair of values; other times it increases one to infinity while attempting to decrease another that’s already zero.  I have a few measures in place to mitigate these effects, but they don’t always work; in particular, they completely fail to detect when a problem is fundamentally unsolvable.

Perhaps I’ll get there.  Perhaps it won’t matter.  As a fun little challenge, though, it has probably served its main purpose in my life.