# Solving Logic Problems

A few years ago I asked this question. I have another question along the same lines. Sorry about the <-> notation, I don't know how else to indicate bijection:

children = { Abe, Dan, Mary, Sue }
ages = { 3, 5, 6, 9 }
children <-> ages  #bijection - one child per one age

Abe > Dan          #Abe is older than Dan
Sue < Mary         #Sue is younger than Mary
Sue = Dan + 3      #Sue's age is Dan's age plus 3 years
Mary > Abe         #Mary is older than Abe


Can sagemath determine that:

Abe = 5
Dan = 3
Mary = 9
Sue = 6

edit retag close merge delete

Sort by ยป oldest newest most voted

For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:

sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....:    if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....:        print p
(5, 3, 9, 6)

more

The case I present is contrived. What general method can offer solutions for which the set of candidates is "large"?

( 2016-06-27 11:54:17 -0500 )edit

This is more like an algorithmic question. It really depends on what "large" means. In whole generality such problems are likely to be NP-hard, so there is no much hope to get asymptotically faster ways. That said, there might be ways to express the problem as an integer linear program and use a strong solver, see http://doc.sagemath.org/html/en/refer... and http://doc.sagemath.org/html/en/thema...

Also, it depends on the kind of instances of your problem, because some of them might belong to some nicer class which could be solved by polynomial means. For example, if there are only comparisons, you can look for linear extensions of partial orders.

( 2016-06-27 12:04:17 -0500 )edit

So, the question is : could you provide an example of instance that you are interested in ?

( 2016-06-27 12:05:28 -0500 )edit

I don't really have a better example. My interest is in solving arbitrary systems of constraints, which I understand is a tall order. I believe the first step is to identify what problem domain a set of constraints belongs to. For example, you can model aerodynamic drag as a function "constrained" by an ODE and boundary conditions. Recognizing that problem class, a solution can be determined symbolically. However, I don't know what problem domain my original question falls into; only that it's presented in some logic that includes arithmetic operations and inequalities. I believe Prolog can handle questions like this, so I hoped that sagemath could too. I also noticed that there's a "sudoku" function which, to me atleast, indicates some kind of satisfiability solving.

( 2016-06-27 12:34:55 -0500 )edit

How can my question be expressed as an ILP problem?

( 2016-06-27 13:09:41 -0500 )edit