Module hercules::local_search_utils

This module contains utility functions for local search algorithms.

This typically includes functions that are used by multiple local search algorithms.

These include:

• 1-opt local search
• 1-step gain criteria local search

Functions

• compute_I
  Auxiliary function to calculate I, as defined in Boros2007
• compute_d
  Auxiliary function to calculate Delta, as defined in Boros2007
• contract_point
  This is a helper function for the basic particle swarm algorithm. It takes two points, x_0 and x_1, and sets up to num_contract variables to be the same between the two points, and then returns the new point.
• get_gain_criteria
  Auxiliary function to calculate the gains from flipping each variable
• one_flip_objective
  Efficient calculation of the delta of the objective function for a single bit flip for each variable more or less this is a helper function that allows for selecting the best bit to flip option without having to calculate the objective function for each bit flip, independently.
• one_step_local_search
  Performs a single gain local search, which is to say that it will flip a single bit and return the best solution out of all of the possible bit flips. This takes O(n|Q|) + O(n) time, where |Q| is the number of non-zero elements in the QUBO matrix.
• one_step_local_search_improved
  Performs a single step of local search, which is to say that it will flip a single bit and return the best solution out of all of the possible bit flips. This takes O(n|Q|) + O(n) time, where |Q| is the number of non-zero elements in the QUBO matrix.