qat.opt.BILP

class qat.opt.BILP(c, S, b, A, B=1, **kwargs)

Specialization of the QUBO class for Binary Integer Linear Programming (BILP).

For a right encoding, one should ensure that \(A \gg B\) and \(A > 0, B > 0\).

Reference

“Ising formulations of many NP problems”, A. Lucas, 2014 - Section 3.

import numpy as np
from qat.opt import BILP

c = np.array([0, 1, 1, 1])
S = np.array([[1, 0, 1, 1], [0, 1, 0, 1]])
b = np.array([1, 1])

B = 1
A = 10 * B

bilp_problem = BILP(c, S, b, A, B=B)

print("To anneal the problem, the solver would need " + str(len(c)) + " spins.")

To anneal the problem, the solver would need 4 spins.
Parameters

  • c (1D numpy array of size N) – a specified vector \(c\). We want to maximize \(c * x\).

  • S (2D numpy array of size m*N) – the matrix, for which \(S * x = b\). This equation is our constraint.

  • b (1D numpy array of size m) – a specified vector \(b\) obeying the constraint \(S * x = b\)

  • A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.

  • B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

get_best_parameters()
Returns

6-key dictionary containing

  • n_monte_carlo_updates (int) - the number of Monte Carlo updates

  • n_trotters (int) - the number of “classical replicas” or “Trotter replicas”

  • gamma_max (double) - the starting magnetic field

  • gamma_min (double) - the final magnetic field

  • temp_max (double) - the starting temperature

  • temp_min (double) - the final temperature

qat.opt.binary_linear_integer_programming.produce_q_and_offset(c, S, b, A, B=1)

Returns the \(Q\) matrix and the offset energy of the problem. For right encoding \(A \gg B\) and \(A > 0, B > 0\).

Parameters

  • c (1D numpy array of size N) – a specified vector \(c\). We want to maximize \(c * x\).

  • S (2D numpy array of size m*N) – the matrix, for which \(S * x = b\). This equation is our constraint.

  • b (1D numpy array of size m) – a specified vector \(b\) obeying the constraint \(S * x = b\)

  • A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.

  • B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1