[gecode-users] Controlling memory use

[Malcolm Ryan]

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.

Many of the constraints are actually redundant and are only used to  
improve propagation. The whole problem could just be expressed as a  
concrete plan with only the first four constraints, but this would  
require a lot more search to solve.

> But what is n?

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.

I have found that I am getting much better memory usage by setting C_d  
very large (around 200). What am I trading off in this case? I presume  
this means that failures are more expensive in terms of computation  
time. Is that right?

> Is it intentional to just send
> it to me? Normally I do not reply to personal messages on Gecode.

Sorry, my mail program doesn't have a "reply to list" option, and I  
don't always remember to change the 'To' field.

Malcolm

> On 4/8/08 9:08 AM, "Malcolm Ryan" <malcolmr at cse.unsw.edu.au> wrote:
>
>> On 08/04/2008, at 5:52 AM, Christian Schulte wrote:
>>> As I have no idea what's inside your model I can't say a thing. Do
>>> you store
>>> BExpr somewhere? What other datastructures do you use? How many and
>>> which
>>> propagators?
>>
>> 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.
>>
>> 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
>>
>> Variables
>> ---------
>>
>> Concrete plans:
>> P[b][r][t] in V   The position of robot r at time t in subplan b
>> L[b]  {1, Lmax}  The length of subplan b
>>
>> Abstract Plan:
>> A[b][r]  in {1,Ns}  The subgraph occupied by robot r in subplan b
>> L_total  {1, Lmax * Nb} The total length of the plan
>>
>> In[b][r][i] bool   True if robot r is in subgraph i in subplan b
>> Pop[b][i] {0, |Si|}  The number of robots in subgraph i in subplan b
>>
>> IsHall[b][r] bool  True if robot r is in a hall subgraph in subplan b
>> HOrd[b][ri][rj] {-1, 0, 1} The ordering of ri and rj in the hall in
>> subplan b
>>
>> IsRing[b][r] bool  True if robot r is in a ring subgraph in subplan b
>> ROrd[b][ri][rj][rk] {-1,0,1} The ordering or ri, rj, rk in the ring
>> in subplan b
>>
>> Constraints
>> -----------
>>
>> 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
>>
>> * No two robots can occupy the same vertex on subsequent time steps:
>> distinct(P[b][1][t], ..., P[b][r][t+1], ... P[b][Nr][t]) for allt,r
>>
>> * Robots can only move between adjacent positions
>> (P[b][r][t], P[b][r][t+1]) \in E or P[b][r][t] == P[b][r][t+1]
>>
>> * No-ops can only occur at the end of the plan
>> (L[b] > t <=> \exists r : P[b][r][t-1] == Pos[b][r][t])
>>
>> Abstract plans:
>> ---------------
>>
>> for all b (except b=0 or b=Nb where appropriate)
>>
>> * Robots can only transition between adjacent subgraphs
>> (A[b][r], A[b+1][r]) \in ES
>>
>> * No-ops can only occur at the end of the plan
>> \exists r A[b+1][r] != A[b][r] --> \exists r A[b][r] != A[b-1][r]
>>
>> * Subplans are linked
>> (P[b][r][Lmax], P[b+1][r][1]) \in E or P[b][r][Lmax] == P[b+1][r][1]
>>
>> * No two robots can occupy the same vertex on subsequent time steps:
>> distinct(P[b][1][Lmax], ..., P[b+1][r][1], ... P[b][Nr][Lmax]) for
>> all r
>>
>> * The abstract plan step constrains the domain of the corresponding
>> subplan
>> (A[b][r] == i) <=> (P[b][r][t] \in Si)
>>
>> * When a subgraph is full, none of its inhabitants can move
>> Pop[b][s] == count(r, A[b][r] == s)
>> Pop[b][s] = |Si| and A[b][r] == s --> P[b][r][t] == P[b][r][0]
>>
>> * Robots in halls must maintain their ordering
>> A[b][ri] == A[b][rj] && isHall(A[b][ri]) <=> HOrd[b][ri][rj] != 0
>> HOrd[b][ri][rj] == -1 --> P[b][ri][t] < P[b][rj][t] for all t
>> HOrd[b][ri][rj] ==  1 --> P[b][ri][t] > P[b][rj][t] for all t
>>
>> * Hall orderings persist across subplans if neither robot  
>> transitions.
>> A[b-1][ri] == A[b][ri] && A[b-1][rj] == A[b][rj]
>> --> HOrd[b-1][ri][rj] == HOrd[b][ri][rj]
>>
>> * Robots in rings must maintain their ordering (clockwise or
>> anticlockwise)
>> A[b][ri] == A[b][rj] && A[b][ri] == A[b][rk] && isRing(A[b][ri])
>> <=> Ord[b][ri][rj][rk] != 0
>>
>> Ord[b][ri][rj] == -1 => RingOrder(rk, rj, ri) for all t
>> Ord[b][ri][rj] ==  1 => RingOrder(ri, rj, rk) for all t
>>
>> where:
>> RingOrder(ri, rj, rk) <=> (ri < rj && rj < rk)
>> or (rk < ri && ri < rj)
>> or (rj < rk && rk < ri)
>>
>> * Ring orderings persist across subplans if neither robot  
>> transitions.
>> A[b-1][ri] == A[b][ri]  && A[b-1][rj] == A[b][rj] && A[b-1][rk] ==
>> A[b][rk]
>> --> Ord[b-1][ri][rj][rk] == Ord[b][ri][rj][rk]
>>
>
> --
> Christian Schulte, web.ict.kth.se/~cschulte/
>
>
>
>