Ask Your Question
2

Solving Logic Problems

asked 2016-06-27 18:06:30 +0100

coder0xff gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2016-06-27 18:46:01 +0100

tmonteil gravatar image

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)
edit flag offensive delete link more

Comments

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

coder0xff gravatar imagecoder0xff ( 2016-06-27 18:54:17 +0100 )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.

tmonteil gravatar imagetmonteil ( 2016-06-27 19:04:17 +0100 )edit

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

tmonteil gravatar imagetmonteil ( 2016-06-27 19:05:28 +0100 )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.

coder0xff gravatar imagecoder0xff ( 2016-06-27 19:34:55 +0100 )edit

How can my question be expressed as an ILP problem?

coder0xff gravatar imagecoder0xff ( 2016-06-27 20:09:41 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-06-27 18:06:30 +0100

Seen: 418 times

Last updated: Jun 27 '16