1. 12

Followup article to Constraint Solving with MiniZinc.

  1.  

  2. 3

    Your experience unfortunately matches mine with generic solvers of all kinds (well, except one): its too slow for any input that could interest me. I’m amazed at how clear the write-up is despite things not going that well. I might try some of the same things but would be mum if asked to explain it.

    What happens if, to break symmetry, you just said “there are at most # rooms (R) talks at any time”? And remove ROOMS entirely from the model.

    Like

    constraint forall(t in TIMES)(
        sum(talk_times[talk] == t) <= R);
    
    1. 2

      I just tried that, and it’s pretty nice! You can rip out sched entirely. I couldn’t find a good way to add symmetry on times, but that plus a crude constraint talk_time[talks[1]] = TIMES[1]; gives you another 5x speedup.

      This gave me an idea: what if we have a variable set of the talks for each time and link them via int_set_channel? In theory, this would give you another huge bonus.

      array[TIMES] of var set of talks: talks_per_time;
      
      constraint int_set_channel(talk_time, talks_per_time);
      
      constraint forall(t in TIMES)(
         card(talks_per_time[t]) = R);
      

      In practice, Chuffed can’t handle var sets :(

      1. 2

        Oh yeah, good idea. So you’re basically saying the talks are partitioned into TIMES sets, each of size at most R [1]. Looks like MiniZinc even has a builtin partition_set but Chuffed won’t handle that either.

        I couldn’t find a good way to add symmetry on times, but that plus a crude constraint talk_time[talks[1]] = TIMES[1]; gives you another 5x speedup.

        If instead of using partition_set, you wanted to do this by hand, you could continue along the same lines as the crude constraint and say “the lowest indexed talk scheduled at time i or later is always scheduled at time i” (for all i).

        [1] I think you still need “at most” instead of “equal” unless you happen to have (# rooms) * (# time slots) talks (or add dummy talks nobody likes to get this to be true).

      2. 1

        solvers of all kinds (well, except one)

        And that exception would be…?

        1. 1

          Solvers for problems with continuous valued variables (float values) with linear constraints and objective.

          This might be a somewhat disappointing answer since the problems you can specify are much less generic. Usually needs some work just translating the problem into the input format (if it can be done at all), which is opposite to MiniZinc’s interface improvement.