Minority Opinions

Not everyone can be mainstream, after all.

Archive for the ‘Uncategorized’ Category

Breaking GLPK

leave a comment »

Soon after last week’s post, I discovered what I had been doing wrong: I had failed to get the negative terms into the PuLP models, so my program was solving something completely different than it claimed to be working on.  Since then, I’ve had great success with many of my problems, returning results almost immediately.

Unfortunately, I’ve found one problem where GLPK crunches for days, without accomplishing anything.  That defeats the whole reason for using it:  I don’t really care about the optimal solution, but I care very much about finding either a solution or determining the infeasibility of the problem in a reasonable time.  Preferably within a minute, but anything more than a day is ridiculously unreasonable.

The problem in question is AB>CD>BC Borda-B.  That’s not a complete pairwise matrix, but simply an exploration into the types of situations where a Borda winner can differ from Condorcet methods.  It expands to eight inequalities over twenty-four variables:

AB > BA: abcd + abdc + acbd + acdb + adbc + adcb + cabd + cadb + cdab + dabc + dacb + dcab > bacd + badc + bcad + bcda + bdac + bdca + cbad + cbda + cdba + dbac + dbca + dcba
BC > CB: abcd + abdc + adbc + bacd + badc + bcad + bcda + bdac + bdca + dabc + dbac + dbca > acbd + acdb + adcb + cabd + cadb + cbad + cbda + cdab + cdba + dacb + dcab + dcba
CD > DC: abcd + acbd + acdb + bacd + bcad + bcda + cabd + cadb + cbad + cbda + cdab + cdba > abdc + adbc + adcb + badc + bdac + bdca + dabc + dacb + dbac + dbca + dcab + dcba
AB > CD: abcd + abdc + acbd + acdb + adbc + adcb + cabd + cadb + cdab + dabc + dacb + dcab > abcd + acbd + acdb + bacd + bcad + bcda + cabd + cadb + cbad + cbda + cdab + cdba
CD > BC: abcd + acbd + acdb + bacd + bcad + bcda + cabd + cadb + cbad + cbda + cdab + cdba > abcd + abdc + adbc + bacd + badc + bcad + bcda + bdac + bdca + dabc + dbac + dbca
Borda-B > Borda-A: abcd + abdc + -1*acbd + -3*acdb + -1*adbc + -3*adcb + 3*bacd + 3*badc + 3*bcad + 3*bcda + 3*bdac + 3*bdca + -1*cabd + -3*cadb + cbad + cbda + -3*cdab + -1*cdba + -1*dabc + -3*dacb + dbac + dbca + -3*dcab + -1*dcba > 3*abcd + 3*abdc + 3*acbd + 3*acdb + 3*adbc + 3*adcb + bacd + badc + -1*bcad + -3*bcda + -1*bdac + -3*bdca + cabd + cadb + -1*cbad + -3*cbda + -1*cdab + -3*cdba + dabc + dacb + -1*dbac + -3*dbca + -1*dcab + -3*dcba
Borda-B > Borda-C: abcd + abdc + -1*acbd + -3*acdb + -1*adbc + -3*adcb + 3*bacd + 3*badc + 3*bcad + 3*bcda + 3*bdac + 3*bdca + -1*cabd + -3*cadb + cbad + cbda + -3*cdab + -1*cdba + -1*dabc + -3*dacb + dbac + dbca + -3*dcab + -1*dcba > -1*abcd + -3*abdc + acbd + acdb + -3*adbc + -1*adcb + -1*bacd + -3*badc + bcad + bcda + -3*bdac + -1*bdca + 3*cabd + 3*cadb + 3*cbad + 3*cbda + 3*cdab + 3*cdba + -3*dabc + -1*dacb + -3*dbac + -1*dbca + dcab + dcba
Borda-B > Borda-D: abcd + abdc + -1*acbd + -3*acdb + -1*adbc + -3*adcb + 3*bacd + 3*badc + 3*bcad + 3*bcda + 3*bdac + 3*bdca + -1*cabd + -3*cadb + cbad + cbda + -3*cdab + -1*cdba + -1*dabc + -3*dacb + dbac + dbca + -3*dcab + -1*dcba > -3*abcd + -1*abdc + -3*acbd + -1*acdb + adbc + adcb + -3*bacd + -1*badc + -3*bcad + -1*bcda + bdac + bdca + -3*cabd + -1*cadb + -3*cbad + -1*cbda + cdab + cdba + 3*dabc + 3*dacb + 3*dbac + 3*dbca + 3*dcab + 3*dcba

My naïve solver gets into a cycle that doesn’t look like it will complete, so I wouldn’t be surprised to find that there is no solution to this.  What does surprise me is that the solver isn’t telling me so.  My Handbook of Mathematics seems to explain how to determine infeasibility, so a computer ought to be able to, right?

Is there a better program that I should be using instead?

Advertisements

Written by eswald

2 Aug 2011 at 8:09 pm

Posted in Uncategorized

Tagged with ,