[gecode-users] Gecode terminates on incomplete solution

[Guido Tack]

Hi,

you get unassigned variables in the output because you don't copy them properly in the copy constructor.  Please read the corresponding section in MPG (or look at the examples): you need to store your variables in a BoolVarArray and then use its update method in the copy constructor.

Regarding the more general problem, the search heuristic may have a huge impact on whether Gecode (or any solver) can find a solution quickly or not at all.  You could analyse the search tree for a long running instance using Gist.  That way you can see why the search fails often, and whether perhaps adding redundant constraints would add enough propagation to speed up the search.

The linear constraints on BoolVars are quite specialised so using them should be fine.

Cheers,
Guido

-- 
Guido Tack
http://www.csse.monash.edu/~guidot/



On 18 May 2014, at 5:38 pm, Philipp Keck <philipp.keck at gmx.de> 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?
> 
> 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?
> 
> 
> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140518/6cdd8265/attachment.html>