[gecode-users] Pruning search in optimisation problems

[Guido Tack]

Malcolm Ryan wrote:

> I have a question about optimisation. Say I have a constraint system
> and I'm trying to minimise the value of some variable X. As I
> understand it, the usual approach is to iteratively find a solution
> with X = x1, then add the constraint X < x1 and repeat until no more
> solutions can be found. Is this correct?

Yes, that's correct.

> It occurs to me that each iteration only makes the problem more
> constrained, so assignments which failed in one iteration will
> continue to fail in all subsequent iterations. Is there any standard
> way to make use of this information to prune the search?

There is, it's called branch-and-bound search:  When you find a  
solution X = x1, add X < x1 to all "open nodes" in the search tree,  
and go on searching from the last solution you found.  The simpler  
alternative is to restart from the root node with the added constraint  
X < x1.  Both search engines are implemented in Gecode (called BAB and  
Restart).

However, the overhead caused by restart is sometimes not as big as one  
could think.  First of all, if the added constraint is strong enough,  
only few states that were already explored will be explored again.   
Second, the hard part of optimization is typically proving  
optimality.  I.e., you arrive at the optimal solution relatively  
quickly, but then you have to explore the remaining (huge) tree which  
is completely failed in order to prove optimality.  This phase is the  
same for both BAB and Restart, so the advantage of BAB only pays off  
in the first phase when you still find solutions.

Cheers,
	Guido