Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Logical Equations

by artist (Parson)
on Jul 08, 2009 at 17:37 UTC ( [id://778356] : perlquestion . print w/replies, xml ) Need Help??

artist has asked for the wisdom of the Perl Monks concerning the following question:

I have set of logical equations. I like to solve them with proper techniques which may include Boolean logic, Graphs, Linear programming, Matrix etc
A + E <= 1 A + B <= 1 C + E <= 1 D + F <= 1 B + D <= 1 A + C + E >= 1 B + D >= 1 E + F >= 1 D + F = 1 A + E <= 1 C + D <= 1 A + B + C + D + E + F = 3
I like to solve for the value of the variables. In above code, the variables A..F can take values only from 0 and 1. There are redundant equations and others that looks like overlaps. There is no overlap in conditions. For example B + D <=1 and B+D >=1 implies B +D = 1. One thing to note: The RHS is not necessarily 1 all the time.
This is just a sample. I can solve easily doing manual effort. There could be many such equations. I like to automate this and need some helpful hints. It may also mean to convert my equations into some recognizable format by some Perl modules which can assist to do the job. A data structure which can hold these equations can also be very useful.


Replies are listed 'Best First'.
Re: Logical Equations
by salva (Canon) on Jul 09, 2009 at 08:29 UTC
    Prolog to the rescue!
    use Language::Prolog::Yaswi qw(:load :query); use Language::Prolog::Sugar vars => [qw(A B C D E F)], functors => [qw(problem)]; swi_inline <<EOP; :- use_module(library(clpfd)). problem(Vars) :- Vars = [A, B, C, D, E, F], Vars ins 0..1, A + E #=< 1, A + B #=< 1, C + E #=< 1, D + F #=< 1, B + D #=< 1, A + C + E #>= 1, B + D #>= 1, E + F #>= 1, D + F #= 1, A + E #=< 1, C + D #=< 1, A + B + C + D + E + F #= 3, label(Vars). EOP swi_set_query(problem([A, B, C, D, E, F])); while (swi_next) { my @r = swi_vars(A, B, C, D, E, F); print join(', ', @r), "\n"; } # prints: # 0, 1, 0, 0, 1, 1 # 0, 1, 1, 0, 0, 1
    update: Language::Prolog::Yaswi 0.18 required!
Re: Logical Equations
by moritz (Cardinal) on Jul 08, 2009 at 18:05 UTC
    Your problem seems to be a Linear Programming problem, for which Wikipedia lists the simplex algorithm as a possible solving method.

    Searching CPAN for simplex lists at least two implementations, PDL::Opt::Simplex and Algorithm::Simplex.

    So you're in luck, all you have to do is to build the coefficient matrix, call one of the modules, and be happy.

      It is not a linear programming problem for at least two reasons. The first is that you're not maximizing a linear function over that search space. The second is that you're not allowed to have fractional numbers in the solution. So a linear algebra package would say that A+B=1, A+C=1 and B+C=1 has a solution, but that would not be a valid solution to the requested problem.
        The first is that you're not maximizing a linear function over that search space

        That's not a problem, since artist is looking of any solution, one that maximizes a certain function will do just fine

        The second is that you're not allowed to have fractional numbers in the solution.

        You're right. I misread can take values only from 0 and 1 as can take values only from 0 to 1.

Re: Logical Equations
by tilly (Archbishop) on Jul 09, 2009 at 06:42 UTC
    I'm sorry to tell you that your problem is NP-complete, and therefore there is no efficient solution. Your problem is NP because any proposed solution can be verified in polynomial time. It is NP-complete because the known NP-complete problem 3SAT can be reduced to your problem. See for a description of 3SAT. To see how to represent it with your format, first include a bunch of equations of the form Xi + Yi = 1 so that Yi represents (NOT Xi). Then string together a series of equations where the sum of 3 terms is >= 1, meaning at least one of them is true.

    That said, there is lots of research on how to tackle this kind of problem. A term I'd suggest googling for is "Constraint Satisfaction".

      A "LP-based tree search" jumps to mind to solve the IP (Integer Programming) problem. I recall this works well for the general case.
        There are many NP complete problems with heuristic solutions that work well for some set of real world inputs. There are also many apparently NP complete problems where you can tackle a reduced form of the problem into something simpler to solve. However none of those solutions work well in the general case.
Re: Logical Equations
by Fletch (Bishop) on Jul 08, 2009 at 18:01 UTC

    Nothing off the shelf comes to mind but given a suitable grammar (which judging by your examples would probably need just a few rules(*)) you could get something using Parse::RecDescent building a parse tree fairly easily.

    (*) Been a while so it's not the right syntax, but along the lines of: STATEMENT => EXPR OP EXPR, EXPR => TERM OP EXPR | TERM, OP => "<=" | ">=", "=", TERM => /A-Z/ | /\d+/

    The cake is a lie.
    The cake is a lie.
    The cake is a lie.

Re: Logical Equations
by jethro (Monsignor) on Jul 08, 2009 at 18:04 UTC

    Well, do you want to solve them algebraic/symbolically or through brute force, i.e. testing all the values ?

    In the first case you might use a mathematics package (a free alternative would be gap, for money you can get maple, mathematica, magma,...) and use perl to translate your problem into the language of that package

    In the second case it might be better to write the search code in C and only do the parsing in perl as the search space grows fast with the number of variables

    For the parsing you might use Parse::RecDescent, but if you never have anything more complicated than what you showed in the example, that would be overkill

Re: Logical Equations
by planetscape (Chancellor) on Jul 09, 2009 at 05:29 UTC
Re: Logical Equations
by elTriberium (Friar) on Jul 10, 2009 at 00:23 UTC