Feature/randomize order

[jackraymond]

Our SA implementation based on Metropolis sweeps is not standard since spins are updated in a fixed sequential order as opposed to a fully randomized order (see e.g. Metropolis 1970, Kirkpatrick 1989, and other canonical definitions). Randomized order can avoid some dynamical pathologies, particularly at high and low temperature. If SA is to be used as a simulator of classical spin dynamics, or for dynamical studies more generally, random order is also better since fixed sequential order introduces a bias as a function of the arbitrary variable order (arbitrary from perspective of the bqm).

Using a fixed update order in the SA sampler per sweep, in combination with Metropolis spin updates, can lead to small increases in efficiency (time to solution or target, or convergence in the distribution) by C-level optimizations in the inner loop, advantageous correlations between the update order and the labeling order of bqms, or as a result of guaranteed rate of updates on a per spin basis. Outside of pathological regimes (Temperature near zero or infinity) the current implementation does allow convergence in the distribution (ergodicity is satisified, detailed balance is satisfied, performance empirically robust over many years), and therefore I think it is fine to leave the legacy behaviour as the default.

This pull request introduces a randomize_order Boolean argument to the sampler that can be used to switch between the two update regimes, with the default being the legacy one. Somebody familiar with optimization code in C should review the change, since as submitted avoiable branching is introduced to the inner loop. It is not clear to me which level the branching should occur, so I await a recommendation on where to put the if statement.

D-wave users can see the internal documentation on 'randomize order in simulated annealing'

[jackraymond]

I added a simple template per @arcondello after a side conversation with @randomir . I think part of the slowdown I saw was due to comparing precompiled and locally compiled libraries. Regardless, there are enough advantages to the templated version I think. Not much more code, and more explicit compile time handling of the randomize argument.

[jackraymond]

I couldn't resist adding a Gibbs update option, since the motivation for, and structure of, the change is almost identical to randomize_order. Again, see internal documentation for some justifications: primarily Gibbs update is useful for bypassing the high and low temperature dynamical pathologies of the Metropolis update, and for reproduction of results from alternative software platforms (in particular things like Block Gibbs on GPU).

[jackraymond]

@arcondello

class AcceptanceCriteria(Enum):
    GIBBS = 0
    METROPOLIS = 1
 class UpdateOrder(Enum):
      SEQUENTIAL = 0
      RANDOM = 1

You had this in mind (and then equivalent in C).

[arcondello]

I am fine with leaving the update order as a boolean, unless you think there will be other update orders in the future. I would also use

enum AcceptanceCriteria {
};

syntax because Cython plays better with that.

[arcondello]

Looks like going to C++17 has an interaction with orang. Let me make a separate PR updating to C++17, and then you can rebase this one off of that.

While I am at it I'll fix the doctest CI issues.

[codecov[bot]]

Codecov Report

Merging #51 (a163588) into main (bc79129) will increase coverage by 0.36%. The diff coverage is n/a.

@@            Coverage Diff             @@
##             main      #51      +/-   ##
==========================================
+ Coverage   92.66%   93.02%   +0.36%     
==========================================
  Files          17       17              
  Lines         545      545              
==========================================
+ Hits          505      507       +2     
+ Misses         40       38       -2     

Impacted Files	Coverage Δ
dwave/samplers/sa/sampler.py	84.96% <ø> (+1.50%)	:arrow_up:

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[jackraymond]

Oops, last commit was a mess.