[gecode-users] Linear memory allocation

[Christian Schulte]

I tried the example, and everything works as expected, regardless of whether
using Boolean or integer variables (Boolean variables are much more
efficient, though, as the linear propagators are specially optimized for
Booleans).

The first solution is found after less than a second on my machine. I used
-c-d 500 and -a-d 500 for recomputation (remember: with O(n^2) variables,
the search tree is O(n^2) deep as the model has close to no propagation).

Gist also works just fine.

Changing to Boolean does not fix the domain consistency issue, it is the
same for Boolean or integer. Please note that for your example domain
consistency is the same as bounds consistency: for inequalities, bounds and
domain consistency is equivalent (and Gecode does the right thing by always
choosing bounds consistency). For equality (you use that for constraining
the Sum variable) in this special case domain consistency is also equivalent
to bounds consistency as all coefficients are unit and all but one variable
are ranges (they are 0/1) (and stupidly Gecode does not realize, aargh).

So I do not really know what your problem is.

Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/

-----Original Message-----
From: Farshid Hassani Bijarbooneh [mailto:farshid.hassani at gmail.com] 
Sent: Tuesday, September 06, 2011 11:21 AM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] Linear memory allocation


On Sep 6, 2011, at 10:04 AM, Christian Schulte wrote:

> Hi,
> 
> 1) The problem here is the number of variables, the number of constraints
is
> not that much of an issue. Are they Boolean or integer variables. Boolean
> variables are much smaller. But still it takes too much memory. Could I
have
> a look at your model?
The variables are integer with domain 0,1. I had to change to integers at
some point due to troubles in implementation of a custom branching. 
> 
> 2) Domain consistent propagation for linear is exponential (that is, here
it
> is 2^49) Please read Tip 4.6 in MPG. Maybe MPG should have a big fat
warning
> (we had this issue before, that's why the reference doc has a big fat
> warning).
I see, though I still wonder why changing to boolean variables fixes the
Domain consistency issue here. I thought integer variables with domain 0,1
are treated the same as boolean despite the memory.
> 
> 2) What does "Gist crashes" mean. It should crash even though propagation
> does not terminate. 
Gist starts but doesn't show the window, and can not be closed unless
killing the process.

Cheers,
Farshid 
> 
> Cheers
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Farshid Hassani Bijarbooneh
> Sent: Tuesday, September 06, 2011 9:38 AM
> To: users at gecode.org
> Subject: [gecode-users] Linear memory allocation
> 
> Hello,
> 
> I have a model with 10^2 to 80^2 variables and linear constraints over 49
> variables each. We have the following issues:
> 1. The code allocates at least 1Gb of memory for even N=50.
> Changing the recomputation distance (-c-d) doesn't seem to help in this
> case.
> 2. Changing the consistency to Domain (line 187) causes the code to
process
> endlessly! (Gist crashes) even for N=20 I suspected the domain consistency
> problem is because of the use of IntVarArray instead of BoolVarArray and
> changing to Bool fixed it, but still very strange that Int gets stuck.
> 
> Please find the code of the isolated problem attached.
>