cimod
C++ library for a binary (and polynomial) quadratic model.
Loading...
Searching...
No Matches
cimod

Overview

cimod is a C++ library for a binary quadratic model. This library provides a binary quadratic model class which contains an Ising model or a quadratic unconstrained binary optimization (QUBO) model. It also provides utilities for constructing a model and transforming to some other interfaces. This library is created based on dimod (https://github.com/dwavesystems/dimod).

Binary quadratic model

A binary quadratic model class can contain an Ising model or a QUBO model.

Ising model

An energy of an Ising model \(E_{\mathrm{Ising}}\) is represented by

\[ E_{\mathrm{Ising}} = \sum_{i} h_i s_i + \sum_{i \neq j} J_{ij} s_i s_j + \delta_{\mathrm{Ising}}, \]

where \(s_i \in \{+1, -1\}\) denotes a spin at the site \(i\), \(h_i\) denotes an external magnetic field parameter, \(J_{ij}\) denotes an interaction parameter and \(\delta_{\mathrm{Ising}}\) denotes an offset. Note that this library assumes that the interaction is not symmetric, i.e., \(J_{ij} \neq J_{ji}\).

QUBO model

An evaluation function of a QUBO model \(E_{\mathrm{QUBO}}\) is represented by

\[ E_{\mathrm{QUBO}} = \sum_{i, j} Q_{ij} x_i x_j + \delta_{\mathrm{QUBO}}, \]

where \(x_i \in \{0, 1\}\) denotes a decision variable, \(Q_{ij}\) denotes a quadratic bias and \(\delta_{\mathrm{QUBO}}\) denotes an offset. Note that this library assumes that the quadratic bias is not symmetric, i.e., \(Q_{ij} \neq Q_{ji}\) if \(i \neq j\).

Binary polynomial model

A binary polynomial model, which can be regarded as an extended model of the binary quadratic model, can handle Ising and HUBO models.

Ising model

An energy of an "extended" Ising model \(E_{\mathrm{Ising}}\) is represented by

\[ E_{\mathrm{Ising}} = \sum_{i} h_i s_i + \sum_{i \neq j} J_{ij} s_i s_j + \sum_{i \neq j \neq k} J_{ijk} s_i s_j s_k + \ldots \]

Here \(s_i \in \{+1, -1\}\) denotes the spin at the site \(i\), \( h_i \) denotes the external magnetic field at the site \( i \), and \(J_{ijk\ldots}\) represents the interaction between the sites. Note that \( i \neq j \neq k \) means \( i \neq j \), \( j \neq k \), and \( i \neq k \). This library assumes that the interaction is not symmetric. For example, \(J_{ij} \neq J_{ji}\) for \( i\neq j\), \(J_{ijk} \neq J_{jik}\) for \( i \neq j \neq k \), and so on.

HUBO model

An energy of an "extended" QUBO model \( E_{\mathrm{HUBO}}\), here we call polynomial unconstrained binary optimization (HUBO), is represented by

\[ E_{\mathrm{HUBO}} = \sum_{i \neq j} Q_{ij} x_i x_j + \sum_{i \neq j \neq k} Q_{ijk} x_i x_j x_k + \ldots \]

Here \( x_i \in \{0, 1\} \) denotes the spin at the site \( i \) and \(Q_{ijk\ldots}\) represents the interaction between the sites. Note that \( i \neq j \neq k \) means \( i \neq j \), \( j \neq k \), and \( i \neq k \). This library assumes that the interaction is not symmetric. For example, \(Q_{ij} \neq Q_{ji}\) for \( i\neq j\), \(Q_{ijk} \neq Q_{jik}\) for \( i \neq j \neq k \), and so on.

Example

#include "../src/binary_quadratic_model.hpp"
#include "../src/binary_polynomial_model.hpp"
using namespace cimod;
int main() {
// Set linear biases and quadratic biases
Linear<uint32_t, double> linear{ {1, 1.0}, {2, 2.0}, {3, 3.0}, {4, 4.0} };
{std::make_pair(1, 2), 12.0}, {std::make_pair(1, 3), 13.0}, {std::make_pair(1, 4), 14.0},
{std::make_pair(2, 3), 23.0}, {std::make_pair(2, 4), 24.0},
{std::make_pair(3, 4), 34.0}
};
// Set variable type
Vartype vartype = Vartype::BINARY;
// Set offset
double offset = 0.0;
// Create a BinaryQuadraticModel instance
BinaryQuadraticModel<uint32_t, double> bqm(linear, quadratic, offset, vartype);
// Print informations of bqm
bqm.print();
//Set polynomial biases
//Linear biases
{{1}, 1.0}, {{2}, 2.0}, {{3}, 3.0},
//Quadratic biases
{{1, 2}, 12.0}, {{1, 3}, 13.0}, {{2, 3}, 23.0},
//Polynomial bias
{{1, 2, 3}, 123.0}
};
// Create a BinaryPolynominalModel instance
// Print informations of bpm
bpm.print();
return 0;
}
Class for BinaryPolynomialModel.
Definition binary_polynomial_model.hpp:168
Class for dense binary quadratic model.
Definition binary_quadratic_model.hpp:148
void declare_BQM(py::module &m, const std::string &name)
Definition main.hpp:41
vartype
Definition binary_polynomial_model.py:412
quadratic
Definition legacy/binary_quadratic_model.py:405
offset
Definition legacy/binary_quadratic_model.py:399
Definition binary_polynomial_model.hpp:139
std::unordered_map< IndexType, FloatType > Linear
Type alias for linear bias.
Definition binary_quadratic_model.hpp:111
std::unordered_map< std::pair< IndexType, IndexType >, FloatType, pair_hash > Quadratic
Type alias for quadratic bias.
Definition binary_quadratic_model.hpp:119
std::unordered_map< std::vector< IndexType >, FloatType, vector_hash > Polynomial
Type alias for the polynomial interactions as std::unordered_map.
Definition binary_polynomial_model.hpp:145
Vartype
Enum class for representing problem type.
Definition vartypes.hpp:24