Restarts
Restart means stopping the current tree search, then starting a new tree search from the root node. Restarting makes sense only when coupled with randomized dynamic branching strategies ensuring that the same enumeration tree is not constructed twice. The branching strategies based on the past experience of the search, such as adaptive search strategies, are more accurate in combination with a restart approach.
Unless the number of allowed restarts is limited, a tree search with restarts is not complete anymore. It is a good strategy, though, when optimizing an NPhard problem in a limited time.
Some adaptive search strategies resolutions are improved by sometimes restarting the search exploration from the root node. Thus, the statistics computed on the bottom of the tree search can be applied on the top of it.
Several restart strategies are available in Solver
.
On solutions
It may be relevant to restart after each solution.
// Restarts after after each new solution.
solver.setRestartOnSolutions()
Geometrical
Geometrical restarts perform a search with restarts controlled by the resolution event counter
which counts events occurring during the search.
Parameter base
indicates the maximal number of events allowed in the first search tree.
Once this limit is reached, a restart occurs and the search continues until base
$\times$ grow
events are done, and so on.
After each restart, the limit number of events is increased by the geometric factor grow
.
limit
states the maximum number of restarts.
solver.setGeometricalRestart(int base, double grow, ICounter counter, int limit)
Info
Some counters may required an argument on constructor that defines the limit to not overpass. Such an argument is ignored by a restart strategy which overrides that value with its own computed one.Luby
The Luby ’s restart policy is an alternative to the geometric restart policy.
It performs a search with restarts controlled by the number of resolution events counted by counter
.
The maximum number of events allowed at a given restart iteration is given by base multiplied by the Las Vegas coefficient at this iteration.
The sequence of these coefficients is defined recursively on its prefix subsequences:
starting from the first prefix $1$, the $(k+1)^{th}$ prefix is the $k^{th}$ prefix repeated grow
times and
immediately followed by coefficient grow
$^k$.

the first coefficients for
grow
= 2 : $$ [1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,\cdots]$$ 
the first coefficients for
grow
=3 : $$ [1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 9,\cdots] $$
solver.setLubyRestart(int base, int grow, ICounter counter, int limit)
You can design your own restart strategies using:
solver.setRestarts( LongCriterion restartCriterion,
IRestartStrategy restartStrategy,
int restartsLimit);
Recording nogoods on restart
When a restart occurs, one may want to prevent the search space explored before restarting to be discovered again in the future. This is achieved by recording nogoods on restart.
By calling:
solver.setNoGoodRecordingFromRestarts();
anytime a restart occurs, a nogood is extracted from the decision path in order to prevent the same scanning the same subtree in the futur.
Feedback
Was this page helpful?
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.