Excessive compilation time

[ofer...@gmail.com]

I have a model for which the compilation time takes over 8 hours. I restricted it heavily just so I can print some stats about the flattening phase, and I got what appears below. 

Is there anything that I can do about it ? it ran with the default (-o1) optimization. Will changing the optimization level may make it faster ?  

Thanks, 

Ofer

 

Flattening ...

CompilePass: Flatten with 'C:\Program Files\MiniZinc IDE (bundled)\share\minizinc/gecode/' library ...

MIP domains ... done (2415.11 s)

Optimizing ... done (2415.13 s)

Converting to old FlatZinc ... done (2415.16 s)

done (2415.16 s)

done (2415.54 s), max stack depth 26

% Generated FlatZinc statistics:

%%%mzn-stat: paths=0

%%%mzn-stat: flatBoolVars=3861

%%%mzn-stat: flatIntVars=659

%%%mzn-stat: flatFloatVars=462

%%%mzn-stat: flatBoolConstraints=1623

%%%mzn-stat: flatIntConstraints=2857

%%%mzn-stat: flatFloatConstraints=774

%%%mzn-stat: evaluatedReifiedConstraints=258

%%%mzn-stat: evaluatedHalfReifiedConstraints=2262

%%%mzn-stat: method="minimize"

%%%mzn-stat: flatTime=2415.55

%%%mzn-stat-end

Maximum memory 496 Mbytes.

[Gabriel Hjort Åkerlund]

To investigate long compilation times, you can try running the minizinc compiler with "--output-detailed-timing" flag. This will tell you how long each constraint takes to compile.

If your model contains functions that are expensive to compute and is invoked often, you can reduce compilation time by storing the result of each argument into an array and then simply do a lookup into that array.

% bad

int: foo(int: n) = <expensive computation>;

% good

int: foo(int: n) = foo_cache[n];

array[int] of int: foo_cache = [ <expensive computation> | n in <lower bound>..<upper bound>];

Cheers,

Gabriel

[guido.tack]

Looking at your statistics output, it's clear that the generated FlatZinc is tiny, ~5000 variables and constraints. The time for optimising and "converting to old FlatZinc" is also very short. That suggests that most of the time is spent in "par" calculations, i.e., where you pre-process your input data in some complex way, but then only generate a small number of variables and constraints from the data. If that's the case, it may be better to do some of the pre-processing in another language.

Other than that, Gabriel's tips are great. Try to find out where the time is spent and then work on that part.

Cheers,

Guido

[ofer...@gmail.com]

Thank you both. I did what gabriel  suggested and so far it still runs for many hours (did not kill it yet). So I ran a restricted version with  -output-detailed-timing . Assuming I read the output correctly, the following line tells me that the constraint/ definition in line 47, takes 78234 miliseconds. 

%%%mzn-stat: profiling=["C:\Users\Ofer\Dropbox\manor\plason.mzn",47,78234]

This is 100 times more than all the other constraints, so I assume that the problem is here.   Here is the constraint at that line. Can you think of a more efficient way to write it ? 

It identifies the pairs of orders that have  a non-empty intersection sets of machines that can serve them. The range 'orders' is rather large (~350).

array[orders,orders] of bool: orders_with_intersecting_machine_sets = 

array2d(orders,orders, 

[exists(p1 in parts, p2 in parts)

( p_code[p1] = o_part[o1] /\ p_code[p2] = o_part[o2] /\ p_machine[p1] = p_machine[p2]) 

| o1 in orders, o2 in o1 + 1 .. n_orders]);

There are two synched arrays that define the 'parts' table: 

p_code is the part code in the parts table; 

p_machine is a machine with which you can manufacture the part.

And one array that defines the part of each order:  

o_part is the part code of the order.

Also, what is an elegant way to compute all pairs (n*(n-1)/2) rather than n*2 as I did? 

Thanks again, 

Ofer

[Gabriel Hjort Åkerlund]

How about something like thps:

array[orders] of set of parts: orders_with_matching_parts =
  [ { p | p in parts where p_code[p] = o_part[o] } | o in orders];
array[parts] of set of parts: parts_with_matching_machines =
  [ { q | q in parts where p_machine[p] = p_machine[q] } | p in parts];

array[orders,orders] of bool: orders_with_intersecting_machine_sets =
  array2d(orders,orders,

    [ let { set of parts: P = orders_with_matching_parts[o1] intersect
                              orders_with_matching_parts[o2]
          }
      in card(P) > 0 /\
         exists (p1, p2 in P) (p_machine[p1] = p_machine[p2])
    | o1, o2 in orders
    ]
  );

On a small testcase I tried, it brought down running time from 19s down to 6s. There is probably a way of removing the "exists" component, but I'm too tired to think of a solution at the moment.

Cheers,

Gabriel

[Mikael Zayenz Lagerkvist]

HI Ofer,

First of all, the code you supplied would not work anyway, since you
are constructing a matrix of size order * order from just
order*(order-1)/2. However, if you use the full definition instead for
the comprehension (o1, o2 in orders) it works. Now, disregarding the
fact that we are creating a very large output array, given this code
(I've added some trivial data

int: n_orders = 50;
set of int: orders = 1..n_orders;
int: n_parts = 50;
set of int: parts = 1..n_parts;

array[parts] of int: p_code = [1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6,
6, 7, 7, 8, 8, 9, 9, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7, 7,
8, 8, 9, 9, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9];
array[orders] of int: o_part = [2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
7, 8, 8, 9, 9, 1, 11, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7, 7, 8,
8, 9, 9, 0, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9];
array[parts] of int: p_machine = [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6,
7, 7, 8, 8, 9, 9, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9];

array[orders,orders] of bool: orders_with_intersecting_machine_sets =
array2d(orders,orders, [
exists(p1 in parts, p2 in parts) (
p_code[p1] = o_part[o1] /\
p_code[p2] = o_part[o2] /\
p_machine[p1] = p_machine[p2]
)

| o1, o2 in orders
]
);

solve satisfy;
output [show2d(orders_with_intersecting_machine_sets)];

The above takes 1.6 s flattening time on my machine. One very simple
way to improve the code, is to make two exist calls instead, and hoist the
checks for the code into the enumerations. Like this

array[orders,orders] of bool: orders_with_intersecting_machine_sets =
array2d(orders,orders, [

exists(p1 in parts where p_code[p1] = o_part[o1]) (
exists(p2 in parts where p_code[p2] = o_part[o2]) (

p_machine[p1] = p_machine[p2]
)

)
| o1, o2 in orders
]
);

This takes the flattening time down to 0.2 seconds on my computer. The
reason is that the inner loop body is not executed once for each
order*order*part*part as is done for the first variant.

A better solution is probably to change the representation, and
instead generate an array of sets

array[orders[ of set of orders: orders_with_intersecting_machine_sets;

The idea is to have each orders_with_intersecting_machine_sets[o] be
the set of other orders for which your original definition would have
been true. This can be constructed as follows

array[orders] of set of orders: orders_with_intersecting_machine_sets = [
{ o2
| o2 in orders where
exists(p1 in parts where p_code[p1] = o_part[o1]) (
exists(p2 in parts where p_code[p2] = o_part[o2]) (

p_machine[p1] = p_machine[p2]
)

)
}
| o1 in orders
];

This takes the same amount of time as the matrix version for this
small example, but might be more efficient for other parts of your
model.

Cheers,
Mikael

> --
> You received this message because you are subscribed to the Google Groups "MiniZinc" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/df47aca7-d7e8-4c28-9ce8-00d8498c90c7n%40googlegroups.com.



--
Mikael Zayenz Lagerkvist