Minority Opinions

Not everyone can be mainstream, after all.

Linear Inequalities

leave a comment »

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.


Written by eswald

26 Jul 2011 at 10:42 pm

Posted in Python

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s