Quine-McCluskey Solver Inefficient for Formulas with Many Input Variables

[zeirew]

Hello, I have been running into some issues with the Quine-McCluskey solver when there are many input variables. Unfortunately, the solver seems to be very inefficient in these cases. Do you have any suggestions to speed up the computation when analyzing formulas such as f1 or f2 below?

f1 = "(0 & ~1 & ~3 & 2) | (0 & 1 & 2 & 4) | (0 & ~1 & 5 & 6 & 7 & ~1 & ~8 & ~9 & ~10 & ~11 & ~12 & 13 & ~3 & ~2) | (0 & 1 & 2)"
f2 = "(0 & 1 & 2) | (0 & ~1 & 5 & 6 & 7 & ~1 & ~8 & ~9 & ~10 & ~11 & ~12 & ~3 & ~2) | (0 & 1 & 2 & 4) | (0 & ~1 & 5 & 6 & 7 & ~1 & ~8 & ~9 & ~3 & ~2) | (0 & ~1 & ~3 & 2) | (0 & ~1 & 5 & 6 & 7 & ~1 & ~8 & ~9 & ~10 & ~11 & ~12 & 13 & ~3 & ~2) | (0 & ~1 & ~3 & ~2) | (0 & 1 & ~2)"

final FormulaFactory f = new FormulaFactory();
final PropositionalParser p = new PropositionalParser(f);
final Formula formula = p.parse(f1);
final Formula dnf = QuineMcCluskeyAlgorithm.compute(formula);

[czengler]

Hi,

the original Quine-McCluskey implementation is very limited in its input size. But there is another far more efficient implementation of QMC in the Advanced Simplifier. Depending on what your goal ist (e.g. if you need a real DNF) you can configure the Advances Simplifier to behave exactly like Quine McCluskey:

final FormulaFactory f = new FormulaFactory();
        final PropositionalParser p = new PropositionalParser(f);
        final Formula formula = p.parse(f2);
        final AdvancedSimplifierConfig config = AdvancedSimplifierConfig.builder()
                .restrictBackbone(false)
                .factorOut(false)
                .simplifyNegations(false)
                .build();
        final Formula dnf = new AdvancedSimplifier(config).apply(formula, true);

This code can compute your formulas in < 100 milliseconds each :)

[zeirew]

Thank you so much @czengler. This is exactly what I was looking for, and I've verified that it works on my end. Really appreciate your help :-)