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

[Kish Shen]

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.