[gecode-users] doing multiple minimising searches with the same space

[Guido Tack]

Christian Schulte wrote:
> There is special support for specialized "constrain" functions which  
> just
> return a cost variable, you might want to check that in "Modeling with
> Gecode". Rather than fixing a particular cost variable you can use a  
> cost
> function that then decides which variable to return depending on  
> which cost
> variable you want use now. Remember: any problem can be solved with  
> one
> additional level of indirection ;-)

Exactly!  You can even use actual assignment instead of an equality  
constraint.  I.e., your space has a member "IntVar cost" that the cost  
function returns.  When you initialize optimization for variable x,  
you execute "space.cost = x" instead of posting the constraint  
"rel(space, cost, IRT_EQ, x)".  That way, you can change that  
assignment later when you start the next search!  You just have to  
make sure that you actually do make such an assignment before you  
start search, and that you update cost (as usual) in the copy  
constructor.

Cheers,
	Guido

> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On  
> Behalf
> Of Kish Shen
> Sent: Tuesday, July 21, 2009 12:54 PM
> Cc: users at gecode.org
> Subject: Re: [gecode-users] doing multiple minimising searches with  
> the same
> space
>
> Guido Tack wrote:
>> Hi Kish,
>>
>> do I understand you correctly, you want to first minimize one cost
>> variable, and then (independently) minimize another?  I.e., when the
>> first one is minimized, there's potentially still variables left that
>> are not assigned, and then you branch over them, minimizing the  
>> other?
>> Or is the actual cost a function of more than one variable (say, a
>> weighted sum or something like that)?
>> If it is the latter, you can (of course) just use a single cost  
>> variable
>> and post constraints that implement the cost function.
>> But I assume it is more like the former.  In this case, I'm not  
>> sure it
>> can be done with the current Gecode search engines.  You'd probably  
>> have
>> to split the search, first minimizing the first cost, then setting  
>> up a
>> new problem and minimizing the second variable.
>> Actually, the new problem might even use the same space (the one
>> returned as the optimal solution), as long as you install a new
>> branching for the remaining variables and tell the cost method to  
>> return
>> the new cost variable.
>>
>> Cheers,
>>    Guido
>>
> Hi Guido,
>
> Thanks for your reply!
>
> I am thinking of the first case. The idea is that you may want to
> subdivide the problem into different set of variables, and perform an
> optimising search on them separately.
>
> If I understood the documentation correctly, the cost/constrain member
> function is part of the space, rather than part of the search (or
> branching), and that I need to define this member function in my code.
> This is why I was thinking of defining a Cost variable as part of the
> space, and at runtime linking this to a specific problem variable --
> this is to allow me to specify the actual cost function at run-time. I
> expect that the programmer will define the cost function as a  
> constraint
> using the problem variable, say
>
> vInt[i] = vInt[j] + vInt[k]
>
> where i is the problem variable I am using as the cost variable. In  
> the
> above case, the search will probably not branch on i, but will  
> branch on
> j and k (and possibly other variables, of course).
>
> I do expect that the new search will use a new branching, and I expect
> it to use a different cost variable (and cost function). I am not  
> sure I
> see how I could use the same space, since I would have already linked
> the space's cost variable to my previous problem variable, i.e. I  
> would
> have posted a constraint like
>
> Cost = vInt[i]
>
> for the previous search. This constraint is no longer valid for the  
> new
> search.
>
> To do the equivalent in the existing ECLiPSe branch-and-bound library
> code, I will call branch-and-bound with a new cost variable, but as  
> the
> cost variable is part of the space, I am not sure how I can do this  
> with
> Gecode. I can of course restrict the problem to have one optimising
> search (during forward execution) only, and most problem will probably
> need more, but it is difficult to explain this restriction.
>
> Cheers,
>
> Kish
> -- 
> This e-mail may contain confidential and privileged material for the
> sole use of the intended recipient. Any review, use, distribution or
> disclosure by others is strictly prohibited. If you are not the  
> intended
> recipient (or authorized to receive for the recipient), please contact
> the sender by reply e-mail and delete all copies of this message.
> Cisco Systems Limited (Company Number: 02558939), is registered in
> England and Wales with its registered office at 1 Callaghan Square,
> Cardiff, South Glamorgan CF10 5BT.
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users