## Linear Inequalities

I had discovered that my inequality problems didn’t need the full power of a general constraint solver, but I hadn’t realized just how overkill it was. While trying to figure out how to determine whether a particular problem is unsolvable, I encountered references to linear matrix inequalities and convex optimization. I hadn’t considered the situation as an optimization problem, but it makes sense to aim for the fewest number of ballots; even some of my hand-coded attempts had tried to start from zero and work upwards.

The linear matrix part was a real surprise. I had learned linear algebra in college, and had used it in quantum physics problems, but hadn’t used it to solve inequalities before. It turns out that there are some tricks for it, particularly when the variables are non-negative integers. The main trick seems to involve the use of a “slack” variable, allowed to be positive, to turn the inequality into an equality.

Beyond that, however, the math is a bit beyond me, not least because my Handbook of Mathematics is a dense mess of jargon. Even more to the point, it has already been programmed several times over, so I shouldn’t need to do so myself. Unfortunately, PuLP and GLPK are giving me incorrect solutions, so I don’t have anything real to report just yet. It’s possible that I can fix the input, but I might need to try another program.

## Leave a Reply