Class LubyRestarts

  • All Implemented Interfaces:
    Splittable<RestartSchedule>, RestartSchedule

    public final class LubyRestarts
    extends Object
    implements 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 often-encountered heavy-tailed 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 well-known 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

      Constructors 
      Constructor Description
      LubyRestarts()
      Constructs 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.
    • Constructor Detail

      • 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 Detail

      • 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 interface RestartSchedule
        Returns:
        the length for the next run of a multistart metaheuristic
      • split

        public LubyRestarts 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 the Copyable 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 interface Splittable<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

        public static 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).
        Parameters:
        numThreads - The number of restart schedules to generate.
        Returns:
        a list of Luby restart schedules
        Throws:
        IllegalArgumentException - if numThreads ≤ 0
      • createRestartSchedules

        public 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).
        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