[gecode-users] Large distinct model
Hi,
I have been playing with gecode for a few days and having a lot of fun.
My overall goal is to solve a large problem that has close to 6 million
values that must be distinct. So kind of like this:
IntVarArray b(*this, 5784689, 0, 5784688);
distinct(*this, b);
Notice that the b's are constrained to be essentially a permutation of
0...5784688.
These b values are generated by sets of linear equations derived from a
directed acyclic multi-graph.
I expect district is a killer. I don't have a hope of attacking this big
problem I think. So I am playing with smaller problems. I see gecode
searching spaces like this:
So 6 b's that are distinct values with a range of 0..5:
b{[2..5], [1..4], [1..4], [1..4], [0..3], [0..3]} this should really be
b{[5], [1..4], [1..4], [1..4], [0..3], [0..3]}. Maybe I am not using the
right way to express what I want and the range and distinct aren't
cooperating enough?
b{[2..4], [1..4], [1..4], [1..4], [0..3], [0..3]} no 5 at all so this
should fail.
More complex case:
b{5, [3..4], [3..4], [2..4], [0..3], [0..3]} should be b{5, [3..4],
[3..4], [2], [0..1], [0..1]}.
Computationally I guess it might be very expensive to discover these
things. Even if you do discover these things I guess it might be it
doesn't help that much.
Thanks.
Neill.
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
Re: [gecode-users] Large distinct model
Thank you very much for this. In my models using the domain propagation
in distinct does seem to improve the run-time substantially so the extra
work does pay off in my case.
I can see this option in the doc now I look for it!
Neill.
On 9/20/2015 3:58 PM, Guido Tack wrote:
Hi,
there are several different propagators for the distinct constraint in Gecode,
and the default one is quite weak and won’t detect these cases. If you post
distinct with ICL_DOM as the third argument you will see the behaviour you
expect (but you’re right, 6M variables will be stretching it - the complexity
of propagating distinct with ICL_DOM is quadratic).
Cheers,
Guido
On 21 Sep 2015, at 8:55 am, Neill Clift <neillcl...@live.com> wrote:
Hi,
I have been playing with gecode for a few days and having a lot of fun.
My overall goal is to solve a large problem that has close to 6 million values
that must be distinct. So kind of like this:
IntVarArray b(*this, 5784689, 0, 5784688);
distinct(*this, b);
Notice that the b's are constrained to be essentially a permutation of
0...5784688.
These b values are generated by sets of linear equations derived from a
directed acyclic multi-graph.
I expect district is a killer. I don't have a hope of attacking this big
problem I think. So I am playing with smaller problems. I see gecode searching
spaces like this:
So 6 b's that are distinct values with a range of 0..5:
b{[2..5], [1..4], [1..4], [1..4], [0..3], [0..3]} this should really be b{[5],
[1..4], [1..4], [1..4], [0..3], [0..3]}. Maybe I am not using the right way to
express what I want and the range and distinct aren't cooperating enough?
b{[2..4], [1..4], [1..4], [1..4], [0..3], [0..3]} no 5 at all so this should
fail.
More complex case:
b{5, [3..4], [3..4], [2..4], [0..3], [0..3]} should be b{5, [3..4], [3..4],
[2], [0..1], [0..1]}.
Computationally I guess it might be very expensive to discover these things.
Even if you do discover these things I guess it might be it doesn't help that
much.
Thanks.
Neill.
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
[gecode-users] Sub expression limits
Hi,
I am having a blast with Gecode! I have this small system to demonstrate
something I want to improve in my code:
e[0] == v[0]
e[2] == v[1]
e[4] == v[2]
v[0] >= 1
v[1] + v[0] >= 2
v[2] + v[1] >= 1
v[2] >= 1
v[0] + v[1] + v[2] == 5
e[4] + e[2] + e[0] == b[0]
e[5] + e[2] + e[0] == b[3]
This gives me:
b{[2..5], [1..5], [1..5], [1..5], [0..5], [0..5]} v{[1..4], [0..3], [1..4]}
So the code doesn't see that
e[4] + e[2] + e[0] == b[0]
e[0] == v[0]
e[2] == v[1]
e[4] == v[2]
v[0] + v[1] + v[2] == 5
means that b[0] == 5.
A more complicated case is b[3] must be >= 2.
Is the level of indirection (v -> e -> b) the problem or recognizing an
inequality is common to two expressions? I am guessing it's the second case.
Is there a way to do this differently to get the better result?
Thanks.
Neill.
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
[gecode-users] Linear Diophantine Equations
Hi, I was wondering if people thought if constraint satisfaction in general and more specifically gecode was suitable for solving quickly a system system like this: $a_1x_1+a_2x_2+...+a_rx_r=n$ $1 \leq a_i$ $1 \leq x_i \leq 2^l$ $1 \leq l$ All variables are integers. a_i is given. We want to find the x_i's. I have billions of these problems that I could attempt to solve in an algorithm I have for computing optimal addition chains. Currently I am only solving cases with $r=2$ using extended gcd. This gives me a very powerful prune in the code. Do you think gecode solves these type of problems efficiently? I know I can do the equivalent of extended gcd in higher dimensions with the Blankinship algorithm etc and then try to enumerate solutions via the specific solution and the null space but I haven't managed to achieve anything with this approach yet. What techniques does gecode use to solve such systems (assuming you have something special for linear constraints)? I have written code using gecode before so I am familiar with it's usage. I am just trying to understand if it might be a good approach or if there are good approaches from constraint satisfaction. Thanks. Neill. ___ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
Re: [gecode-users] Linear Diophantine Equations
Hi, Thanks for your response. I was hoping there was some technique I wasn't aware of used in constraint satisfaction systems. r is small in my system. In fact just having something for r=3 would be a big deal. It has to be very fast though as this would be a prune. I am familiar with integer programming but I thought using something like glpk would be too slow. Neill. On 1/4/2017 3:03 AM, Christian Schulte wrote: > Hi Neill, > > Gecode uses standard propagation techniques for linear equations: depending > on the size and values of the a_i propagation tends to be rather weak. It > can use domain consistent propagation for the linear constraint but its > complexity is exponential. > > It might work reasonably well for small r but why not using a linear integer > programming solver: > https://en.wikipedia.org/wiki/Integer_programming > > Cheers > Christian > > -- > Christian Schulte, www.gecode.org/~schulte > Professor of Computer Science, KTH, cschu...@kth.se > Expert Researcher, SICS, cschu...@sics.se > > > -Original Message- > From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf > Of Neill Clift > Sent: Wednesday, January 4, 2017 01:00 > To: users@gecode.org > Subject: [gecode-users] Linear Diophantine Equations > > Hi, > I was wondering if people thought if constraint satisfaction in general and > more specifically gecode was suitable for solving quickly a system system > like this: > > $a_1x_1+a_2x_2+...+a_rx_r=n$ > $1 \leq a_i$ > $1 \leq x_i \leq 2^l$ > $1 \leq l$ > All variables are integers. a_i is given. We want to find the x_i's. > > I have billions of these problems that I could attempt to solve in an > algorithm I have for computing optimal addition chains. Currently I am only > solving cases with $r=2$ using extended gcd. This gives me a very powerful > prune in the code. > > Do you think gecode solves these type of problems efficiently? I know I can > do the equivalent of extended gcd in higher dimensions with the Blankinship > algorithm etc and then try to enumerate solutions via the specific solution > and the null space but I haven't managed to achieve anything with this > approach yet. > What techniques does gecode use to solve such systems (assuming you have > something special for linear constraints)? > I have written code using gecode before so I am familiar with it's usage. I > am just trying to understand if it might be a good approach or if there are > good approaches from constraint satisfaction. > Thanks. > Neill. > ___ > Gecode users mailing list > users@gecode.org > https://www.gecode.org/mailman/listinfo/gecode-users ___ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
Re: [gecode-users] Extra level of variables needed for count?
Thanks.
I think I might now be seeing what you are saying. Sorry to be so stupid. I
found this count stuff to be mind boggling.
IntSetArgs s((LPTYPER)bp.MaxBit);
for (LPTYPER i = 0; i < (LPTYPER)bp.MaxBit;
i++) {
s[i] =
IntSet((LPTYPER)bp.Bits[i], (LPTYPER)bp.Bits[i]);
}
count(*this, b, s, IPL_DOM);
I guess I was feeling I was using an overly more general mechanism with
variables for counts when I have constants for counts. With the sets I am still
using something which allows much more general situations but since it’s
constants it might be optimized away.
So I assume this would be the recommended way to code this?
Neill.
Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10
From: Christian Schulte <cschu...@kth.se>
Sent: Monday, March 12, 2018 9:31:36 AM
To: Neill Clift; users@gecode.org
Subject: RE: Extra level of variables needed for count?
No, the point is to not use variables, you can use sets with a single element
instead. Christian
--
Christian Schulte, https://chschulte.github.io/
Professor of Computer Science, KTH, cschu...@kth.se<mailto:cschu...@kth.se>
Expert Researcher, RISE SICS,
christian.schu...@ri.se<mailto:christian.schu...@ri.se>
From: Neill Clift [mailto:neillcl...@live.com]
Sent: Monday, March 12, 2018 17:30
To: Christian Schulte <cschu...@kth.se>; users@gecode.org
Subject: RE: Extra level of variables needed for count?
OK thanks for that. This makes the code simpler but I do still have to make a
set of variables to contain the multiplicities (the v’s).
Of course they immediately become assigned to a single value. Would it be right
in assuming the cost of that on the model is very small?
Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10
From: Christian Schulte <cschu...@kth.se<mailto:cschu...@kth.se>>
Sent: Monday, March 12, 2018 2:31:26 AM
To: Neill Clift; users@gecode.org<mailto:users@gecode.org>
Subject: RE: Extra level of variables needed for count?
Hi,
I think you stopped reading a little too early. MPG says that you can also use
integer sets instead of variables.
Then, in your example you do not need x and c, just pass b and v directly!
IntVarArray is automatically casted to IntVarArgs.
Cheers
Christian
--
Christian Schulte, https://chschulte.github.io/
Professor of Computer Science, KTH, cschu...@kth.se<mailto:cschu...@kth.se>
Expert Researcher, RISE SICS,
christian.schu...@ri.se<mailto:christian.schu...@ri.se>
From: users-boun...@gecode.org<mailto:users-boun...@gecode.org>
[mailto:users-boun...@gecode.org] On Behalf Of Neill Clift
Sent: Saturday, March 10, 2018 20:37
To: users@gecode.org<mailto:users@gecode.org>
Subject: [gecode-users] Extra level of variables needed for count?
Hi,
I want to restrict the values of an array to members of a multiset. This is a
bit like distinct but can have repeated values.
So for example I want the values of b[0..7] to come from the multiset
{5,5,5,4,3,2,1,0}. The b’s are essentially a permutation of the multiset
Count seems to be the way to achieve this but I have to add a whole new set of
variables (the v’s below) that contain the counts of the multiplicities.
I cut out a bunch of stuff that’s not relevant to the code below so I hope it
still makes sense.
bp.MaxBit is the number of distinct values in the multiset. And bp.Bits[i] is
the multiplicity for the multiset value i.
Is this the expected way to do what I am trying to do here?
Thanks.
Neill.
public:
IntVarArray b;
public:
PartialOrderSort(LPTYPER n, BIT_PATTERN , LPTYPER TopIndex) :
b(*this, n, 0, TopIndex)
{
IntVarArgs x(n);
IntVarArgs c((LPTYPER)bp.MaxBit);
for (int i = 0; i < n; i++) {
x[i] = b[i];
}
IntVarArray v(*this, (LPTYPER)bp.MaxBit, 0, n -
1);
for (int i = 0; i < bp.MaxBit; i++) {
c[i] = v[i];
rel(*this, v[i] ==
(LPTYPER)bp.Bits[i]);
}
count(*this, x, c, IPL_DOM);
Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
Re: [gecode-users] Extra level of variables needed for count?
OK thanks for that. This makes the code simpler but I do still have to make a
set of variables to contain the multiplicities (the v’s).
Of course they immediately become assigned to a single value. Would it be right
in assuming the cost of that on the model is very small?
Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10
From: Christian Schulte <cschu...@kth.se>
Sent: Monday, March 12, 2018 2:31:26 AM
To: Neill Clift; users@gecode.org
Subject: RE: Extra level of variables needed for count?
Hi,
I think you stopped reading a little too early. MPG says that you can also use
integer sets instead of variables.
Then, in your example you do not need x and c, just pass b and v directly!
IntVarArray is automatically casted to IntVarArgs.
Cheers
Christian
--
Christian Schulte, https://chschulte.github.io/
Professor of Computer Science, KTH, cschu...@kth.se<mailto:cschu...@kth.se>
Expert Researcher, RISE SICS,
christian.schu...@ri.se<mailto:christian.schu...@ri.se>
From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of
Neill Clift
Sent: Saturday, March 10, 2018 20:37
To: users@gecode.org
Subject: [gecode-users] Extra level of variables needed for count?
Hi,
I want to restrict the values of an array to members of a multiset. This is a
bit like distinct but can have repeated values.
So for example I want the values of b[0..7] to come from the multiset
{5,5,5,4,3,2,1,0}. The b’s are essentially a permutation of the multiset
Count seems to be the way to achieve this but I have to add a whole new set of
variables (the v’s below) that contain the counts of the multiplicities.
I cut out a bunch of stuff that’s not relevant to the code below so I hope it
still makes sense.
bp.MaxBit is the number of distinct values in the multiset. And bp.Bits[i] is
the multiplicity for the multiset value i.
Is this the expected way to do what I am trying to do here?
Thanks.
Neill.
public:
IntVarArray b;
public:
PartialOrderSort(LPTYPER n, BIT_PATTERN , LPTYPER TopIndex) :
b(*this, n, 0, TopIndex)
{
IntVarArgs x(n);
IntVarArgs c((LPTYPER)bp.MaxBit);
for (int i = 0; i < n; i++) {
x[i] = b[i];
}
IntVarArray v(*this, (LPTYPER)bp.MaxBit, 0, n -
1);
for (int i = 0; i < bp.MaxBit; i++) {
c[i] = v[i];
rel(*this, v[i] ==
(LPTYPER)bp.Bits[i]);
}
count(*this, x, c, IPL_DOM);
Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
[gecode-users] Extra level of variables needed for count?
Hi,
I want to restrict the values of an array to members of a multiset. This is a
bit like distinct but can have repeated values.
So for example I want the values of b[0..7] to come from the multiset
{5,5,5,4,3,2,1,0}. The b’s are essentially a permutation of the multiset
Count seems to be the way to achieve this but I have to add a whole new set of
variables (the v’s below) that contain the counts of the multiplicities.
I cut out a bunch of stuff that’s not relevant to the code below so I hope it
still makes sense.
bp.MaxBit is the number of distinct values in the multiset. And bp.Bits[i] is
the multiplicity for the multiset value i.
Is this the expected way to do what I am trying to do here?
Thanks.
Neill.
public:
IntVarArray b;
public:
PartialOrderSort(LPTYPER n, BIT_PATTERN , LPTYPER TopIndex) :
b(*this, n, 0, TopIndex)
{
IntVarArgs x(n);
IntVarArgs c((LPTYPER)bp.MaxBit);
for (int i = 0; i < n; i++) {
x[i] = b[i];
}
IntVarArray v(*this, (LPTYPER)bp.MaxBit, 0, n -
1);
for (int i = 0; i < bp.MaxBit; i++) {
c[i] = v[i];
rel(*this, v[i] ==
(LPTYPER)bp.Bits[i]);
}
count(*this, x, c, IPL_DOM);
Sent from Mail for Windows 10
___
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
