java.lang.Object
org.cicirello.search.restarts.LubyRestarts
 All Implemented Interfaces:
Splittable<RestartSchedule>
,RestartSchedule
The Luby restart schedule originated with constraint satisfaction search, and was originally used
to control when to restart a backtracking constraint satisfaction search in number of backtracks.
Its motivation is the oftenencountered heavytailed runtime distributions of constraint
satisfaction search algorithms (i.e., although many runs may take exponentially long to solve the
instance, there tends to be a high density of runs that lead directly to a solution). The Luby
schedule's intention is to cut off search early, and that a restart may have a reasonable chance
of resulting in one of the fast runs. The Luby schedule, thus, is focused on short numbers of
restarts, but does continue to increase over time to ensure completeness of constraint
satisfaction search.
It is not likely a good choice for simulated annealing, and other similar optimization algorithms, as the Luby schedule's objective is rather different than how restarts are used in simulated annealing. However, we have included it in this library as it is a wellknown restart schedule for search more generally.
The Luby schedule of restart lengths is as follows: 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 16, .... The default constructor supports this original Luby schedule. An additional constructor provides the ability to multiply the Luby schedule by a constant.

Constructor Summary
ConstructorDescriptionConstructs a restart schedule that follows the Luby sequence of run lengths.LubyRestarts
(int a) Constructs a restart schedule, such that the run lengths are equal to a*L, where L follows the Luby sequence. 
Method Summary
Modifier and TypeMethodDescriptionstatic List<LubyRestarts>
createRestartSchedules
(int numThreads) A convenience method for generating several identical and independent LubyRestarts objects, such as when needed for a parallel search (e.g., if each instance needs its own restart schedule).static List<LubyRestarts>
createRestartSchedules
(int numThreads, int a) A convenience method for generating several identical and independent LubyRestarts objects, such as when needed for a parallel search (e.g., if each instance needs its own restart schedule).int
Gets the next run length in the restart schedule's sequence of run lengths.void
reset()
Resets the restart schedule to its initial conditions, such that the next call toRestartSchedule.nextRunLength()
will return the initial run length of the schedule.split()
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.

Constructor Details

LubyRestarts
public LubyRestarts()Constructs a restart schedule that follows the Luby sequence of run lengths. 
LubyRestarts
public LubyRestarts(int a) Constructs a restart schedule, such that the run lengths are equal to a*L, where L follows the Luby sequence. Parameters:
a
 A multiplier, which must be positive. Each run length is equal to a*L where L follows the Luby sequence. Throws:
IllegalArgumentException
 if a < 1


Method Details

nextRunLength
public int nextRunLength()Description copied from interface:RestartSchedule
Gets the next run length in the restart schedule's sequence of run lengths. Specified by:
nextRunLength
in interfaceRestartSchedule
 Returns:
 the length for the next run of a multistart metaheuristic

reset
public void reset()Description copied from interface:RestartSchedule
Resets the restart schedule to its initial conditions, such that the next call toRestartSchedule.nextRunLength()
will return the initial run length of the schedule. Specified by:
reset
in interfaceRestartSchedule

split
Description copied from interface:Splittable
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of theCopyable
interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state. Specified by:
split
in interfaceSplittable<RestartSchedule>
 Returns:
 A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.

createRestartSchedules
A convenience method for generating several identical and independent LubyRestarts objects, such as when needed for a parallel search (e.g., if each instance needs its own restart schedule). Parameters:
numThreads
 The number of restart schedules to generate. Returns:
 a list of Luby restart schedules
 Throws:
IllegalArgumentException
 if numThreads ≤ 0

createRestartSchedules
A convenience method for generating several identical and independent LubyRestarts objects, such as when needed for a parallel search (e.g., if each instance needs its own restart schedule). Parameters:
numThreads
 The number of restart schedules to generate.a
 A multiplier, which must be positive. Each run length is equal to a*L where L follows the Luby sequence. Returns:
 a list of Luby restart schedules
 Throws:
IllegalArgumentException
 if numThreads ≤ 0 or if a < 1
