$or works differently than I expected

[Misophistful]

I've just started playing with loco, but I've hit an immediate brick wall where $or isn't behaving how I expected it to.

I'm trying to solve Project Euler problem 1, which is nice and easy with the for macro:

(for [x (range 1 10)
      :when (or (= 0 (mod x 3))
                (= 0 (mod x 5)))]
  x)

=> (3 5 6 9)

But my first attempt at a similar approach with loco didn't work:

(solutions
  [($in :x 1 9)
   ($or ($= 0 ($mod :x 3))
        ($= 0 ($mod :x 5)))])

=> ({:x 1} {:x 2} {:x 3} {:x 4} {:x 5} {:x 6} {:x 7} {:x 8} {:x 9})

I'm guessing that I've totally misunderstood how $or should be used, so I'd really appreciate a prod in the right direction.

Thanks for your work on this cool project.

Cheers,
James

[aengelberg]

Don't worry, you don't have a misunderstanding of how loco works... It's either a bug with $or, $mod, or $=, or there's something quirky about the Choco API that I missed from the Java docs.

I'll get back to you on this as soon as I get the chance to investigate further. Thanks for finding this issue.

[aengelberg]

Hi James,

This is a bug within Choco, so unfortunately it is beyond my control for now. The Choco mod constraint is actually represented as an intricate composition of multiple constraints (division, addition, etc), so somehow nesting it in the or constraint is making it behave oddly.

For now, a workaround would be:

(solutions [($in :x 1 10)
            ($in :_x-mod-3 0 2)
            ($in :_x-mod-5 0 4)
            ($= :_x-mod-3 ($mod :x 3))
            ($= :_x-mod-5 ($mod :x 5))
            ($or ($= :_x-mod-3 0)
                 ($= :_x-mod-5 0))])
=> ({:x 6} {:x 3} {:x 9} {:x 10} {:x 5})

[Misophistful]

Thanks for figuring it out, and for posting the workaround.

Does the workaround have a strong negative impact on performance? I ask because I'm seeing poor performance compared to for for large ranges of x. For example, this takes ~1430ms:

(time (reduce + (map :x (solutions [($in :x 1 10e4)
                                    ($in :_x-mod-3 0 2)
                                    ($in :_x-mod-5 0 4)
                                    ($= :_x-mod-3 ($mod :x 3))
                                    ($= :_x-mod-5 ($mod :x 5))
                                    ($or ($= :_x-mod-3 0)
                                         ($= :_x-mod-5 0))]))))

Whereas this takes ~30ms:

(time (reduce + (map :x (for [x (range 1 10e4)
                              :when (or (= 0 (mod x 3))
                                        (= 0 (mod x 5)))]
                          {:x x}))))

And ($in :x 1 10e5) times out on my machine.

---

By the way, are you worried by the lack of recent updates for Choco?

[aengelberg]

In my experience, Choco has not been very good at handling domains that large. This particular problem seems not very applicable to Constraint Programming because it's a very simple constraint on a very large domain.

Also, I wouldn't expect that my workaround alone is making it this slow. A lot of the slowness you're experiencing is most likely coming from the propagator having to iterate through each possible x, and spend its usual overhead of propagating and recording possible solutions.

That said, if you are trying to apply Loco to a domain this large, you'll want to be using bounded variables instead of enumerated ones (the default). That way, Choco is not storing every value from 1 to 10,000 in an array somewhere, which normally would help the propagation but in this case is hurting it. On my machine, changing it to ($in :x 1 10e4 :bounded) halved the time it took (~700 ms), and upping it to 10e5 from there made it about 7 seconds (which is still reasonable for Project Euler problems).

[Misophistful]

Constraint Programming is a totally new approach for me, so I'm still trying to figure out which problems it's well suited to. Thanks for taking the time to explain why it's not well suited in this case.

[arichiardi]

Learning as well, I am going to plus-one that thank you of yours 😄

[jgFages]

Hi guys,

@aengelberg, I have provided a clean workaround for the mod problem here: chocoteam/choco-solver#272
is that ok for you?

@Misophistful, we are used to releasing the code every 3-6 months, but our development branch is often updated.

@ALL Please do not hesitate to post messages on our forum (http://choco-solver.org/?q=Forum) or on Github if you have any request or simply to inform us about your usage of Choco!

[jgFages]

I have encoded it in Choco to see what it gives. I got the following model:

public void testEuler(){
Solver s = new Solver();
int n = 100000;
IntVar number = VF.bounded("multiple of 3 or 5",1,n-1,s); // a number between 1 and n-1
IntVar mod = VF.enumerated("mod",new int[]{3,5},s); // either 3 or 5
IntVar zero = s.ZERO; // a zero constant
s.post(ICF.mod(number,mod,zero)); // the modulo operation should return 0
sum = 0; // a (long) java global variable
s.plugMonitor((IMonitorSolution) () -> sum += number.getValue());// callback on each solution (valid number)
s.findAllSolutions();
System.out.println("sum is : "+sum);
}

It deals with 10^5 in 0.5 seconds, so there is no problem with a large domain in itself. See that there are only two variables but the sum is computed with a callback.

@Misophistful CP is used to solve harder problems that require to trigger sophisticated algorithms and explore a search space (apply decisions). A simple and classical example is the sudoku problem (solved in a few ms with CP). In practice, CP is often used for planning and scheduling applications (human resources, manufacturing, etc.). This Euler problem is not relevant to CP because it can be solved with a simple "for" loop. Solving it with a CP solver is like hunting a bee with a bazooka.

[aengelberg]

@jgFages Using the enumerated "mod" variable is clever (I would have never thought to do that!) but I think your custom aggregator would not give the right answer, because now multiple solutions are being generated for multiples of 15. For example, n = 15, mod = 3, and n = 15, mod = 5. Now 15 is counted twice in the result.

And thanks for the further clarification about what types of problems CP is meant for. I'm glad to have an actual CP expert join the discussion. ;-)

[jgFages]

You are right I have not seen this! Although it is not that straightforward, you can solve this efficiently by specifying a search heuristic :

s.set(ISF.lexico_LB(number), new Once(new IntVar[]{mod},ISF.lexico_var_selector(),ISF.min_value_selector()));

It will first branch on "number" and then branch ONCE on "mod" (given the current value of number, it will not try different values for the latter).