[gecode-users] Controlling memory use

[Mikael Zayenz Lagerkvist]

On Wed, Apr 9, 2008 at 2:14 AM, Malcolm Ryan <malcolmr at cse.unsw.edu.au> wrote:
> On 09/04/2008, at 1:57 AM, Christian Schulte wrote:
>  > Malcolm,
>  >
>  > That's a lot of constraints!
>
>  Is it? I have no idea what constitutes "a lot" in this area.

Lets look at the following small part of your model to evaluate the
number of constraints.

>  >> Constants:
>  >> G = (V, E)  graph   The map
>  >> V   {1, Nv}   The vertices are numbered
>  >> E   in V^2   The edges are stored as a table
>  >> Nr    # robots  The number of robots
>  >> Ns   # subgraphs  The number of subgraphs
>  >> Si    subset of V, Subgraphs are sets of consecutive vertices
>  >> Si_min <= v <= Si_max
>  >> ES   in {1..Ns}^2 The adjacency betweem subgraphs as a table
>  >> Nb   # subplans  The size of the abstract plan
>  >> Lmax  maximum plan length
>  >>
>  >> Concrete plans:
>  >> P[b][r][t] in V   The position of robot r at time t in subplan b
>
>  Typical values:
>
>  Nv      100-1000
>  Ns      50-100
>  Nr      20 or more (the more we can handle the better)
>
>  Nb and Lmax depend on the problem. I usually start Nb small (around 5)
>  and increase it if this value fails. Lmax depends on the size and
>  types of subgraphs. I'm currently working with Lmax = 40.
>
>  >> Concrete plans: for all b:
>  >>
>  >> * No two robots can occupy the same vertex at the same time:
>  >> distinct(P[b][1][t], P[b][2][t], ..., P[b][Nr][t]) for all t

This will give rise to Nb*Lmax (=200) distinct-constraints. Depending
on wheter you use naive, bounds consistent, or domain consistent
propagation, this will take varying amounts of memory.

The worst case occurs if you use domain-consistent pruning on these
(ICL_DOM). For each propagator a variable-value graph (a bipartite
graph with the variables on one side and the values on the other) is
maintained. These graphs have O(Nv+Nr) nodes and O(Nv*Nr) edges. This
means that for just this set of distinct propagators might have graphs
with O(Nb*Lmax*Nv*Nr) edges in total, or up to 4000000 edges.

Given the discrepancy between the number of variables and values (~20
vs. ~1000), I would guess that domain-consistent pruning does not help
very much, it is usually more important when then number of variables
and values are of similar size.

Using naive propagation takes much less memory (on the order of the
number of variables per propagator, saving a factor of Nr), while
bounds propagation takes slightly more memory, but only by a constant
factor.


>  >> I've outlined the problem description below. All the boolean
>  >> expressions are constructed from BExprs. The only ones that are
>  >> expressly reified as BoolVars are those noted in the Variables
>  >> section. These are created because there is no BExpr which tests set
>  >> membership.

As a general rule, you might want to cache Boolean reification
variables if they occur more than once (not sure if this is the case
for you), since it is quite wasteful to create them and their
propagators several times through a modeling interface.


Cheers,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/