Hi Christian,
thanks for your reply!
You are right, the boolean variants of these constraints can be modeled
like that. In fact, my current solution works fine with "linear" - but
it's slow. Therefore, I was looking for specialized constraints like
"distinct" or "atmost", because Max indicated that they might be faster
("They usually perform much better than linear constraints.").
If however the "linear" constraint in Gecode is already as good as
possible (I use the first one here
http://www.gecode.org/doc-latest/reference/group__TaskModelIntLB.html#ga7dbaf2c0ceb605f34731328004c73b57),
I'll stick with that. Since I don't know that much about constraint
propagation, I imagine (!) that a linear constraint requires some sort
of computation to sum up a (weighted) array, while an implementation of
"atmost_1" would only need to store the single variable from the array
that is currently true, and then prevent the rest from being set to
true. That's why I currently believe (!) that "linear" might by
unnecessarily powerful and not optimally efficient for my use case.
Again, I may well be wrong.
A "distinct" constraint on boolean variables would only make sense for
two variables, obviously. What I need is something like "distinct except
0"
(http://www.emn.fr/z-info/sdemasse/gccat/Calldifferent_except_0.html),
i.e. variables set to zero/false are ignored and only one variable is
allowed to be true/one. I can't achieve that with inequality, because
two variables may be 0, actually even all variables may be 0.
It does work with a pair-wise NAND constraint implemented like that:
forall i != j do: rel(*this, variables[i], BOT_AND, variables[j], 0);
But that gives me O(n^2) constraints only to express the single
requirement that at most one of these variables can be true. And I have
O(m^2) of these if m is my problem size, so I would end up with O(m^4)
constraints in Gecode. Am I overlooking something like an inequality
constraint for multiple boolean variables?
Best
Philipp
Am 12.06.2014 17:19, schrieb Christian Schulte:
Hi,
Yes, it is true that these constraints do not exist for 0/1 as they are not
needed:
- distinct for Boolean variables is inequality
- atmost/count is linear for 0/1! Check MPG.
Best
Christian
--
Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/
-----Original Message-----
From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf
Of Philipp Keck
Sent: Thursday, June 12, 2014 3:27 PM
To: Max Ostrowski; t...@gecode.org; users@gecode.org
Subject: Re: [gecode-users] Gecode terminates on incomplete solution
Hi Guido, Hi Max,
thank you very much for taking your time! Your tips and ideas just doubled
the size of my todo list :-), that's why it took me so long to reply. In
particular, the tip about pseudo-boolean solvers was great. I am now
experimenting with Sat4J (both PB and MinCostSAT), which is a lot slower
than Gecode, but solves some more problem instances on which Gecode needs to
search a large tree. But because it is only quick on decision problems and
too inefficient for my optimization problems, I continue my experiments with
Gecode.
About the initial problem mentioned in the subject of this mail:
BoolVarArray was indeed the solution. I didn't copy it from the examples at
first, because I don't know in advance how much variables there will be, so
I thought I couldn't use it. But by first reading all the variables to a
list and then placing them in an (uninitialized) BoolVarArray works fine.
Thank you!
Thanks to Gist, I can now try to experiment with different kinds of
constraints. It looks like the search space is simply too large right now.
With Gist activated, Gecode explores around 500 failures every two seconds -
no matter which way I model the constraints. In comparison to the entire
(binary) search tree, that's almost nothing. After a few hours, more than
90% of the search tree is still linear (to the left), i.e. has not yet been
explored.
Is it true that alldifferent/distinct/atmost/count only exist for integer
variables? And according to the manual BoolVars can't be casted to IntVars.
But maybe this is a solution (I don't know enough C++ to
tell): As described in the manual Figure 27.4, one could use
Gecode::Int::Count::LqInt<VX,VY> to implement a "count" or "atmost"
method that accepts a BoolVarArray instead of a IntVarArray. Is that
possible?
The kind of constraint I need should ensure that at most one of a given list
of boolean variables is true. So it could be "all different except 0",
"distinct except 0", "Multi-XOR", or it could be modeled with "atmost" or
"count", if they are able to handle boolean variables.
Best,
Philipp
Am 19.05.2014 09:36, schrieb Max Ostrowski:
Hi,
On 05/18/2014 06:38 PM, Philipp Keck wrote:
Hi,
I am new to Gecode and also to Constraint Programming. While my first
problem may be a general CP question (so off-topic here? In that case
ignore it please.), my second problem is Gecode-specific.
My first problem is that Gecode either finds a solution immediately
(<1ms) and without any backtracking (peak-depth equals explored
nodes-1), or takes longer than I want to wait (at least 2 hours).
This problem might be related to my problem instances, because
or-tools shows exactly the same behaviour. My problem instances have
1,000 to 10,000 boolean variables and 400 to 2,500 constraints. There
are both large and small instances that can be solved within
milliseconds, and both large and small instances that take a long
time. For those that take more than
2 hours, I still am sure that there is a solution, because Gurobi
finds one when I formulate the same problem as an LP.
How could I improve the running time of Gecode here? Does adding more
constraints make finding (any feasible) solution faster (because the
search space is more restricted and therefore the search tree is
smaller) or slower (because there are simply less solutions)? Should
I add redundant constraints?
If adding more constraints make the search faster or not can not be
said in general.
Adding redundant constraints is always worse a try, if you can improve
propagation strength with it.
For a set of boolean variables, if I want at most one of them to be
1, is it better to add "a+b+c+... <= 1" using a linear-Constraint, or
should I use "a!=b", "a!=c", "b!=c", ... instead? Unfortunately I
have difficulties finding out the answers by experimenting because
Gecode runs for such long times. Is there a way to get some output
during the computation?
The first thing you can try is using global cosntraints that exactly
fit your needs.
In this case, allDifferent or atmost, etc...
They usually perform much better than linear constraints.
(It may be the case that Gecode automatically detects this in your
case and replaces the linear constraints with the global constraints.
)
Furthermore, your problem sounds like a PB(Pseudo-Boolean) problem.
So maybe you should try a PB solver.
Best,
Max
My second problem is a weird behaviour of Gecode terminating with
some variables remaining unassigned:
My models have the following structure: I have boolean variables only
and two kinds of constraints. The first kind of constraints requires
exactly c variables out of a certain subset to be 1, e.g. "a+c+d+x+y
= 3" or "a+b = 1". The second kind allows at most one variable to be
1, e.g. "a+b+r <= 1". That's all.
As mentioned above, Gecode either terminates immediately, or takes a
very long time. However, I have a particular problem instances that
makes Gecode terminate and report "solutions: 1" without having all
the variables set. So there are variables that still have [0..1]
instead of a specific value and val() throws ValOfUnassignedVar. Why
does Gecode terminate before it has a solution?
I call it like this:
branch(*this, allVariablesArgs, INT_VAR_NONE(), INT_VAL_MIN()); Using
this call on the other hand makes Gecode compute forever (i.e.
more than 2 hours):
branch(*this, allVariablesArgs, INT_VAR_RND(someRnd),
INT_VAL_RND(someOtherRnd));
The problem might be related to how I implemented the copy function.
I have my variables inside a std::map<std::string, BoolVar> *and*
inside a BoolVarArgs and clone them like this:
variablesMap = s.variablesMap;
allVariablesArgs = BoolVarArgs(s.allVariablesArgs); I don't know if
that's the correct way to go. In particular, my copy implementation
never uses the share-parameter.
After reading the thread "Integer Variable Randomization" on this
mailing list, I also tried setting -c-d and -a-d to high values, but
still the copy-method was called many times.
Thank you for any help!
Philipp
Platform: Windows 7 x64, Visual Studio 2013 x64, Gecode 4.2.1
_______________________________________________
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 mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
