Module org.cicirello.chips_n_salsa
Package org.cicirello.search.restarts

Class LubyRestarts

java.lang.Object
org.cicirello.search.restarts.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.

  • Method Summary

    Modifier and Type
    Method
    Description
    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).
    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
    nextRunLength()
    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 to RestartSchedule.nextRunLength() will return the initial run length of the schedule.
    LubyRestarts
    split()
    Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • 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 interface RestartSchedule
      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 to RestartSchedule.nextRunLength() will return the initial run length of the schedule.
      Specified by:
      reset in interface RestartSchedule

    • 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