[gecode-users] Multiple separate searches

[Guido Tack]

On 23/04/2012, at 3:31 PM, Milton Friedman wrote:

> Guido Tack <tack at ...> writes:
>> 
>> -- 
>> Guido Tack
>> http://www.csse.monash.edu/~guidot/
>> 
>> When you construct DFS from a space, DFS takes ownership of that space, 
>> unless you give it a search options argument where you set clone to false 
>> (see the reference documentation for the DFS class).  So here it depends 
>> on whether s is still the initial space (in which case you mustn't delete it) 
>> or a space returned from e.next (in which case you must delete it).
>> But that's not the main problem with the code above: 
>> a space returned from e.next() is always NULL or SS_SOLVED.
>> What you probably want to do is to implement your own Brancher 
>> that runs a DFS internally.  There is code that does more or less that in 
>> gecode/flatzinc/flatzinc.cpp in the current svn trunk, it's called 
>> "AuxVarBrancher".  Perhaps that can help you to get started.
>> 
>> Cheers,
>> Guido
>> 
>> _______________________________________________
>> Gecode users mailing list
>> users at ...
>> https://www.gecode.org/mailman/listinfo/gecode-users
>> 
> 
> Thanks Guido.
> 
> I see what you mean about DFS only returning NULL & Solved, and not Branch.
> It looks like when you initialize DFS, s.status() returns Branch,
> you're immediately going to use e.next to call DFS,
> so no need to check for Branch.

As I said, DFS takes ownership of s, so you shouldn't do anything with s after initialising DFS.  You are definitely not allowed to delete it!

> That makes the function simpler, and it works. 
> But now I'm able to delete s in two places,
> as I was originally trying to do: 
> - The first deletion deletes the initial space.
> - The final deletion deletes the space returned by s = e.next()
> So I'm not sure why it's letting me delete both spaces,
> since I didn't use the .clone=false option.
> I must have misunderstood what you meant.

It may just work by accident.

> void DoOneDFS(int argc, char* argv[],const char* ModelName){
>        SizeOptions optModel(ModelName);         
>        optModel.iterations(1);          
>        optModel.size(3);          
>        optModel.parse(argc,argv);     
>        ModelB* s = new ModelB(optModel);
>        //initialize DFS search engine
>        DFS<modelB> e(s);
>        delete s;       //deletes initial space
>        s = e.next();   //calls DFS
>        if (s)  {               //if not null, then solved
>                if (SS_SOLVED==s->status()){
>                        cout<<"Solved"<<endl;
>                        s->myprint();
>                        s->mydebugprint();
>                        //system("PAUSE");
>                }
>                else if (SS_FAILED==s->status()){
>                        cout<<"Failed"<<endl;
>                        //system("PAUSE");
>                }
>                else { 
>                        cout<<"Shouldn't arrive here. status: "<<s->status()<<endl;
>                        system("PAUSE");
>                }
>        }
>        else     //null...no solution found.
>        delete s;
>  }

I'm still puzzled what you are trying to do here.  I thought you wanted to run another DFS on a different set of variables when the first DFS finishes, so I would have expected the code to look more or less like this:

DFS<modelB> e(s);
modelB* sol=NULL;
while (sol==NULL) {
  sol = e.next();
  if (sol==NULL) break; // no more solutions -> done
  branch(*sol,....); // Add branch for second set of variables
  DFS<modelB> e2(sol);
  sol = e2.next();
}
if (sol) {
  sol->print();
  delete sol; // this is the only object that needs deletion
}

> Thanks for the suggestion about writing my own brancher.
> Would it be significantly faster?  If so, what is the source of the speedup?

It wouldn't be faster, it would just be easier to encapsulate (you can run it with any search engine, not just with your own combination of engines).

Cheers,
Guido