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).

This class allows for the encoding of a BILP problem from a given matrix \(S\), vectors \(b\) and \(c\) and positive constants \(A\) and \(B\). The aim is to maximise \(c * x\) subject to \(x\) obeying \(S * x = b\). The method produce_q_and_offset() is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent class QUBO and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.

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()

This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).

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