5
$\begingroup$

I would like to know if there is a way to do constraint programming in Mathematica? I think there are no built-in functions, but maybe some of you know some additional packages addressed to the constraint satisfaction problem.

Update

@Histograms mentioned FindInstance but I have to say that I have tried it before but it works a bit strange consider example below:

system = {
 -(1/2) + x + (1 - θ^2)/( 1 + θ^2) + (1 - (1 - θ^2)/( 1 + θ^2)) ω1^2 > 0, 
 1/2 + x + (1 - θ^2)/( 1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1^2 > 0,
 -(1/2) + y + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω2 + (2 θ ω3)/(1 + θ^2) < 0, 
 1/2 + y + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω2 + (2 θ ω3)/(1 + θ^2) > 0, 
 -(1/2) + z - (2 θ ω2)/( 1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω3 < 0, 
 1/2 + z - (2 θ ω2)/(1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω3 > 0, 
 -∞ <= θ <= ∞, 
 {ω1, ω2, ω3} ∈ Sphere[{0, 0, 0}, 1], 
 0 <= ω1 <= ω2 <= ω3 <= 1, 
 -(1/2) < x < 1/2, 
 -(1/2) < y < 1/2, 
 -(1/2) < z < 1/2};

FindInstance[system, {θ, ω1, ω2, ω3, x, y, z}, Reals, 1] 
  (*change n to two to get the answer*)

In Mathematica 10.0.2 I cannot get any answer for n = 1, it just run all the time. But if I change it eg to 2 I get answer almost immediately. Any suggestions what is wrong?

$\endgroup$

closed as too broad by m_goldberg, Bob Hanlon, C. E., MarcoB, dr.blochwave Jun 14 '15 at 17:10

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ In principle you can do Prolog in any language $\endgroup$ – Dr. belisarius Jun 13 '15 at 7:20
  • $\begingroup$ Well FindInstance is basically a SAT solver, and Select and Cases are pretty useful. $\endgroup$ – Histograms Jun 13 '15 at 7:49
  • $\begingroup$ @Histograms well I've tried FindInstance before and I have a problem with it. In particular, for my problem it gives me very quickly more than one solutions but if I will call it with n == 1 it cannot finish... $\endgroup$ – marekszpak Jun 13 '15 at 11:14
  • $\begingroup$ @marekszpak well if you want help with that particular problem you know where to come. You should also try Select if you're able to pre-generate lists of potential solutions to seive. $\endgroup$ – Histograms Jun 13 '15 at 14:37
  • 1
    $\begingroup$ @image_doctor Here mathematica-journal.com/issue/v4i1/columns/maeder/… $\endgroup$ – Dr. belisarius Jun 13 '15 at 15:41
2
$\begingroup$

I was able to generate one instance (the all-zeros solution) but FindInstance refuses to generate 2 or more for me (v10.1) using the final argument, despite copious solutions existing.

Horrible hack incoming in 3... 2... 1:

(* N.B I removed your greek and the sphere constraint is now `Ball`. 
If you only want the surface of the sphere, then `Sphere` is fine,
but only works up to ninstances = 2 giving:
{{x -> 0, y -> 0, z -> 0, t -> 0, w1 -> 0, w2 -> 0, w3 -> 1},
{x -> 15/32, y -> 1/4, z -> -(1/4), t -> -1, w1 -> 1/4, 
 w2 -> 1/2, w3 -> Sqrt[11]/4}} *) 

system = {
   -1/2 < x < 1/2,
   -1/2 < y < 1/2,
   -1/2 < z < 1/2,
   -(1/2) + x + (1 - t^2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1^2 > 0,
    1/2 + x + (1 - t^2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1^2 > 0,
   -(1/2) + y + (1 - (1 - t^2)/(1 + t^2)) w1 w2 + (2 t w3)/(1 + t^2) < 0, 
    1/2 + y + (1 - (1 - t^2)/(1 + t^2)) w1 w2 + (2 t w3)/(1 + t^2) > 0,
   -(1/2) + z - (2 t w2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1 w3 < 0,
    1/2 + z - (2 t w2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1 w3 > 0,
 {w1, w2, w3} \[Element] Ball[{0, 0, 0}],
 0 <= w1 <= w2 <= w3 <= 1};

newsystem = system; i = 0; ninstances = 10;
Flatten[Reap@
While[i < ninstances, 
newsystem = 
 Flatten[Append[newsystem, 
   First[Sow[
      FindInstance[And @@ newsystem, {x, y, z, t, w1, w2, w3}, 
       Reals, 1]]] //. Rule -> Unequal]];
i++], 3] // Rest

I noticed that if you get a single instance from FindInstance then you append an extra constraint to the system that the solution cannot be the previous one, rinse and repeat, you can generate more solutions. Of course, this is an absolutely horrific way of getting around FindInstance failing to do as it's told and just give us multiple solutions out of the box without hanging.

$\endgroup$
  • $\begingroup$ thanks! Well, my system from example above is just a demo. In real case I have to work with something a bit bigger around 40 strict inequalities. Well, I added just 6 more inequalities to my system and FindInstance again cannot finish. I was worried from the very beginning that my shell constraint makes a lot of troubles here. Do you have any idea how I could speed up FindInstance for more general cases? $\endgroup$ – marekszpak Jun 14 '15 at 15:49
  • $\begingroup$ @marekszpak no I'm afraid FindInstance is hopeless. I've been playing around with it and crikey, what a nightmare. At this point I'm thinking generate the w1,w2,w3 in the shell randomly, then use Reduce after substituting them into the system. $\endgroup$ – Histograms Jun 14 '15 at 15:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.