Ising Heuristic Solvers

Note

Not all accounts have access to this type of solver.

The Ising heuristic solver is intended to solve complex problem structures. It has some important differences from other solvers:

  • There is no fixed problem structure. In particular, this solver does not have the properties num_qubits, qubits, and couplers.
  • Only one solution is returned and it is not guaranteed to be optimal.
  • Solver properties and parameters are entirely disjoint from those of other solvers.
  • It cannot be used with the QSage solver.

Note that this heuristic solver can handle problems of arbitrary structure.

Algorithm

The core of the heuristic solver is a local search based on optimizing low-treewidth subgraphs. In pseudocode:

function local_search(problem, x)
  stuck = 0
  e = evaluate(problem, x)
  while (time limit not exceeded) and (stuck <= local_stuck_limit)
    select random low-treewidth subproblem
    (new_e, x) = solve(subproblem, x)
    if subproblem is the entire problem
      return (new_e, x, exact=true)
    if new_e < e
      stuck = 0
    else
      stuck = stuck + 1
    e = new_e
  return (e, x, exact=false)

The local_stuck_limit value is a user-supplied parameter. What constitutes a “low-treewidth subproblem” is determined by the parameter max_local_complexity. The time limit is provided by the parameter time_limit_seconds.

To escape local minima, multiple copies of the solution are made and bits are randomly flipped.

function ising_heuristic(problem)
  x = random solution vector
  (e, x, exact) = local_search(problem, x)
  if exact
    return (e, x)
  best_e = current_e = e; best_x = current_x = x
  iter = 0
  while (time limit not exceeded) and (iter < iteration_limit)
    iter = iter + 1
    new_e = current_e; new_x = current_x
    for i = 1 to num_perturbed_copies
      x = current_x
      flip each bit of x with probability p(i)
      (e, x, exact) = local_search(problem, x)
      if exact
        return (e, x)
      if e < new_e
        new_e = e; new_x = x
    current_e = new_e; current_x = new_x
    if current_e < best_e
      best_e = current_e; best_x = current_x
  return (best_e, best_x)

In the ising_heuristic function, iteration_limit and num_perturbed_copies are user-provided parameters. The (i-dependent) bit flip probability p(i) is determined by the parameters min_bit_flip_prob and max_bit_flip_prob.

Solver Name

ising-heuristic

Properties

None, except for the common property supported_problem_types.

Parameters

This section describes the parameters accepted by Ising heuristic solvers, in alphabetical order. See Summary of Ising Heuristic Solver Parameters for a summary and for the default values.

Note

Many of these parameters described here require a high-level understanding of the heuristic algorithm. Parameter settings can wildly affect solver performance and solution quality. It is difficult in general to know what good values are a priori; defaults are selected to favor quicker run times over aggressive searches. Therefore, experimentation with these values is recommended.

iteration_limit

Specifies the maximum number of solver iterations, not including the initial local search. Must be an integer >= 0; default = 10.

local_stuck_limit

Specifies the number of consecutive local search steps that do not improve solution quality to allow before determining a solution to be a local optimum. Larger values produce more thorough local searches but increase run time. Must be an integer > 0; default = 8.

max_bit_flip_prob

Bit flip probability range. The probability of flipping each bit is constant for each perturbed solution copy but varies across copies. The probabilities used are linearly interpolated between min_bit_flip_prob and max_bit_flip_prob. Larger values allow more exploration of the solution space and easier escapes from local minima but may also discard nearly-optimal solutions.

Must be a number [0.0 1.0] and min_bit_flip_prob <= max_bit_flip_prob, default min_bit_flip_prob = 1.0 / 32.0, default max_bit_flip_prob = 1.0 / 8.0.

max_local_complexity

Specifies the maximum complexity of subgraphs used during local search. The run time and memory requirements of each step in the local search are exponential in this parameter. Larger values allow larger subgraphs (which can improve solution quality) but require much more time and space. Subgraph “complexity” here means treewidth+1.

Must be an integer > 0; default = 9.

min_bit_flip_prob

Bit flip probability range. The probability of flipping each bit is constant for each perturbed solution copy but varies across copies. The probabilities used are linearly interpolated between min_bit_flip_prob and max_bit_flip_prob. Larger values allow more exploration of the solution space and easier escapes from local minima but may also discard nearly-optimal solutions.

Must be a number [0.0 1.0] and min_bit_flip_prob <= max_bit_flip_prob, default min_bit_flip_prob = 1.0 / 32.0, default max_bit_flip_prob = 1.0 / 8.0.

num_perturbed_copies

Number of perturbed solution copies created at each iteration. Run time is linear in this value.

Must be an integer > 0; default = 4.

num_variables

Provides a lower bound on the number of variables. This solver can accept problems of arbitrary structure and the size of the solution returned is determined by the maximum variable index in the problem. The size of the solution can be increased by setting this parameter.

Must be an integer >= 0, default = 0.

random_seed

Provides a random number generator seed. When a value is provided, solving the same problem with the same parameters will produce the same results every read. If no value is provided, a time-based seed is selected.

The use of a wall clock-based timeout may in fact cause different results with the same random_seed value. If the same problem is run under different CPU load conditions (or on computers with different performance), the amount of work completed may vary despite the fact that the algorithm is deterministic. If repeatability of results is important, rely on the iteration_limit parameter rather than the time_limit_seconds parameter to set the stopping criterion.

Must be an integer >= 0; default is a time-based seed.

time_limit_seconds

Specifies the maximum wall clock time in seconds. Actual run times will exceed this value slightly.

Must be a number >= 0.0; default = 5.0.

Summary of Ising Heuristic Solver Parameters

Ising heuristic solver parameters and their default values are summarized in the table below.

Table 1 Ising Heuristic Solver Parameters
Parameter Range Default Value
iteration_limit >= 0 10
local_stuck_limit > 0 8
max_bit_flip_prob [min_bit_flip_prob 1.0] 1/8
max_local_complexity > 0 9
min_bit_flip_prob [0.0 1.0] 1/32
num_perturbed_copies > 0 4
num_variables >= 0 0
random_seed >= 0 Time-based seed
time_limit_seconds >= 0.0 5