[gecode-users] Gecode terminates on incomplete solution

[Philipp Keck]

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 at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users