Logical Equations

[artist]

Hi
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.

Thanks.

[salva]

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!

[moritz]

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.

[tilly]

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.

[moritz]

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.

[tilly]

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 http://en.wikipedia.org/wiki/Boolean_satisfiability_problem 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".

[dHarry]

A "LP-based tree search" jumps to mind to solve the IP (Integer Programming) problem. I recall this works well for the general case.

[tilly]

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.

[Fletch]

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+/

[jethro]

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

[planetscape]

Perusing the following may help:

• Truth Table
• Math::BooleanEval
• generating random thruth-tables
• Generate a truth table from input string
• parser for evaluating arbitrarily complex boolean function in a string
• A "but" operator.

[elTriberium]

If I remember my studies correctly, then this should be a CSP: http://en.wikipedia.org/wiki/Constraint_satisfaction_problem

The Wikipedia page also mentions ideas on how to solve these problems, for example backtracking: http://en.wikipedia.org/wiki/Backtracking