Restarts in or-tools

It is very easy to use restarts in or-tools

They are handled via a search monitor:

The monitors tracks the number of fails...
...And causes a restart whenever the limit is reached

There are two types of restart search monitor:

slv.LubyRestart(scale) # Luby restart sequence
slv.ConstantRestart(limit) # Constant limit

We will also need to randomize the search strategy:

We can use CHOOSE_RANDOM_VAR for variable selection...
...Or ASSIGN_RANDOM_VALUE for value selection

LNS in or-tools

Or-tools allows to specify easily a fragment selection strategy

We just need to implement a simple python class:

class MyRandomLns(pywrapcp.BaseLns):
  def __init__(self, x, size, rand):
    pywrapcp.BaseLns.__init__(self, x)
    self.size_ = size # Number of vars to relax (e.g.)
    self.rand_ = rand # RNG

  def InitFragments(self):
    pass

  def NextFragment(self):
    positions =
    for pos in positions:
      self.AppendToFragment(pos)
    return True

__init__ is called when the class is built

LNS in or-tools

Or-tools allows to specify easily a fragment selection strategy

We just need to implement a simple python class:

class MyRandomLns(pywrapcp.BaseLns):
  def __init__(self, x, size, rand):
    pywrapcp.BaseLns.__init__(self, x)
    self.size_ = size # Number of vars to relax (e.g.)
    self.rand_ = rand # RNG

  def InitFragments(self):
    pass

  def NextFragment(self):
    positions = # random indices of the variables
    for pos in positions:
      self.AppendToFragment(pos)
    return True

NextFragment specifies the variables to relax

LNS in or-tools

Or-tools allows to specify easily a fragment selection strategy

We just need to implement a simple python class:

class MyRandomLns(pywrapcp.BaseLns):
  def __init__(self, x, size, rand):
    pywrapcp.BaseLns.__init__(self, x)
    self.size_ = size # Number of vars to relax (e.g.)
    self.rand_ = rand # RNG

  def InitFragments(self):
    pass

  def NextFragment(self):
    positions = # random indices of the variables
    for pos in positions:
      self.AppendToFragment(pos)
    return True

InitFragments is called whenever an improving solution is found