Constraint Solvers

Lately, I've become interested in integer factorization and have been playing with constraint solvers. I started out with minion but quickly became frustrated. Minion does not support nesting of constraints or custom constraints from what I can tell. The set of equations I was working with were mostly comprised of terms that were either a*b mod 10 or (a*b - a*b mod 10) / 10. I would need to have all sorts of intermediate variables and constraints to express these terms. Which isn't difficult, but would be tedious.

Enter python-constraint. This module is awesome and I thank the author for creating it. It allowed me to write constraints that were easy to read and understand. It supports constraints expressed as lambda functions (nameless functions in py). Unfortunately, the worst case performance of python-constraint is not great when compared to minion. I ended up writing a simple benchmark in py and minion to contrast the differences. Here is the python benchmark. It is nice and readable.

import sys

from constraint import *

p = Problem()

p.addVariables(["x", "y"], range(0, 999))

p.addVariable("z", range(0, 999999))

p.addConstraint(lambda x, y: x > 1 and y > 1, ["x", "y"])

p.addConstraint(lambda x, y, z: x * y == z, ["x", "y", "z"])

p.addConstraint(lambda z: z == 123456, ["z"])

print p.getSolution()

This little snippet took 17 minutes and 11 seconds to complete.

time ./bench.py

{'y': 192, 'x': 643, 'z': 123456}

real 17m16.996s

user 17m11.200s

sys 0m0.392s

And now, minion:

MINION 3

**VARIABLES**

DISCRETE x {0..999}

DISCRETE y {0..999}

DISCRETE z {0..999999}

**SEARCH**

VARORDER [x, y]

PRINT[[x, y, z]]

**TUPLELIST**

**CONSTRAINTS**

product(x, y, z)

eq(z, 123456)

sumgeq([x], 2)

sumgeq([y], 2)

**EOF**

Minion spits out a result in under 1 second. Yipes.

Sol: 192 643 123456

Solution Number: 1

Time:0.000000

Nodes: 2

Solve Time: 0.208013

Total Time: 0.276017

Total System Time: 0.288018

Total Wall Time: 0.651100

Maximum Memory (kB): 0

Total Nodes: 2

Problem solvable?: yes

Solutions Found: 1

real 0m0.680s

user 0m0.276s

sys 0m0.312s

That's a huge reduction in processing time. Note that both problems are poorly structured. Looks like I may need to dive into that tedious process of translating equations to minion.