Skip to main content

# JijSASampler

Simulated Annealing (SA) is one of the most commonly used meta heuristic. This algorithm employs a method analogous to annealing in materials by gradually lowering the temperature. As a result, it avoids getting trapped in local minima while exploring for the global minimum. For a more detailed explanation, please see the following page: Simulated Annealing.

In JijSASampler, the temperature varies from the minimum inverse temperature $\beta_{\min}$ to the maximum inverse temperature $\beta_{\max}$ according to the following geometric cooling:

$\beta_{t}=\beta_{\min} \times r^{t-1},$

where $t$ is the Monte-Carlo steps and the maximum value of $t$ is determined by num_sweeps. The rate of temperature change is $r=(\frac{\beta_{\max}}{\beta_{\min}})^{1/\mathrm{num\_sweeps}}$.

## Method of Generating QUBO​

In JijSASampler, the mathematical model is converted to Quadratic Unconstrained Binary Optimization (QUBO) to execute Simulated Annealing (SA). Instead of the simple Penalty method, JijSASampler utilizes a method inspired by the Augmented Lagrangian Method (ALM) to generate QUBO. Specifically, suppose there is a mathematical model as follows:

\begin{align*} \min \quad & f(x) + \sum_k\alpha_k p_k(x) \\ \text{s.t.} \quad & g_i(x) = 0 \quad \forall i \in \mathcal{E}_1 \\ & h_j(x) \leq 0 \quad \forall j \in \mathcal{E}_2 \\ & x \in \{0,1\} \cup \mathbb{Z} \end{align*}

where $f(x)$ is an objective function, $p_k(x)$ is a jm.CustomPenaltyTerm with penalty coefficient $\alpha_k$. $g_i(x) = 0$ represents the equality constraints defined by the jm.Constraint class, and $h_j(x) \leq 0$ represents the inequality constraints also defined by the jm.Constraint class. Here, $\mathcal {E}_1$ and $\mathcal {E}_2$ denote the indices for the equality and inequality constraints respectively. Note that integer variables will be turned to binary variables with a log encoding method.

The method used in JijSASampler to convert this mathematical model into the following form:

\begin{align*} L(x) = f(x) + \sum_k\alpha_k p_k(x) + \sum_{i\in \mathcal {E}_1} \lambda_i g_i ({x}) + \sum_{i\in \mathcal {E}_1} \mu_i g_i (x)^2 + \sum_{j\in \mathcal {E}_2} \lambda_j' h_j(x) + \sum_{j\in \mathcal {E}_2} \mu_j' h_j(x)^2\end{align*}

where the $\lambda_i$, $\lambda_j'$ are Lagrange multipliers, and $\mu_i$, $\mu_j'$ are the penalty parameters. The advantage of using a method inspired by ALM instead of the Penalty method is the elimination of the need for slack variables. As a result, it is possible to reduce the number of bits required. On the other hand, it necessitates the proper adjustment of the parameters for linear terms. Therefore, it is recommended to use the parameter search provided by JijSASampler.

Furthermore, there are aspects in the above expression that differ from the conventional textbook notation of ALM. For instance, the different handling of inequality constraints is due to the inability to use expressions such as $\max$ on Annealing devices. Additionally, the absence of the coefficient of 1/2 for quadratic terms is for the sake of notation brevity.

## Usage​

Use the two classes provided by the jijzept and run the method sample_model in the JijSASampler class:

• JijSASampler: a class to sample by the SA method.
• JijSAParameters: a class to set parameters specifically for the SA sampler.
from jijzept import JijSASampler, JijSAParameterssampler = JijSASampler(config="./config.toml")parameters = JijSAParameters(beta_min=1, beta_max=10, num_search=15)response = sampler.sample_model(    problem=problem,     feed_dict=instance_data,    parameters=parameters,    search=True,    max_wait_time=300,)

## What does JijZept automatically tune?​

By setting the search argument of the sample_model method to True, the weight coefficients for converting the mathematical model to QUBO are auto-adjusted.

## Parameters​

### JijSAParameters​

nametypedefaultdescription
beta_minOptional[float]NoneMinimum (initial) inverse temperature. If None, this will be set automatically.
beta_maxOptional[float]NoneMaximum (final) inverse temperature. If None, this will be set automatically.
num_sweepsOptional[int]NoneThe number of Monte-Carlo steps. If None, 1000 will be set.
num_readsOptional[int]NoneThe number of samples. If None, 1 will be set.
initial_stateOptional[dict]NoneInitial state. If None, this will be set automatically.
updaterOptional[str]NoneUpdater algorithm. "single spin flip" or "swendsen wang". If None, "single spin flip" will be set.
sparseOptional[bool]NoneIf True, only non-zero matrix elements are stored, which will save memory. If NoneFalse will be set.
reinitialize_stateOptional[bool]NoneIf True, reinitialize state for each run. If NoneTrue will be set.
seedOptional[int]NoneSeed for Monte Carlo algorithm. If None, this will be set automatically.
needs_square_constraintsOptional[dict[str, bool]]NoneThis dictionary object is utilized to determine whether to square the constraint condition while incorporating it into the QUBO/HUBO penalty term. Here, the constraint's name is used as the key. If the value is set to True, the corresponding constraint is squared upon its addition to the QUBO/HUBO penalty term. By default, the value is set to True for linear constraints, and to False for non-linear ones.
relax_as_penaltiesOptional[dict[str, bool]]NoneThis dictionary object is designed to regulate the incorporation of constraint conditions into the QUBO/HUBO penalty term, with the constraint's name functioning as the key. If the key's value is True, the respective constraint is added to the QUBO/HUBO penalty term. If the value is False, the constraint is excluded from the penalty term, though it remains subject to evaluation to verify if it meets the constraint conditions. By default, all constraint conditions have this value set to True.

### JijSASampler.sample_model​

nametypedefaultdescription
parametersOptional[JijSAParameters]NoneParameters for JijSASampler.
searchboolFalseIf True, the parameter search will be carried out, which tries to find better values of multipliers for penalty terms.
num_searchint15The number of parameter search iteration. Defaults to set 15. This option works if search is True.
algorithmOptional[Literal["v096", "v097-2", "v098"]]NoneAlgorithm for parameter search. The valid strings for algorithm are "v096", "v097-2", "v098", users can specify the method used to the parameter search. If None, "v098" will be set.
max_wait_timeOptional[Union[int, float]]NoneThe number of timeout [sec] for post request. If None, 60 (one minute) will be set. Please note that this argument is for the jijzept timeout and not for configuring solver settings, such as solving time.
syncboolTrueIf True, synchronous mode is enabled.
queue_nameOptional[str]NoneQueue name.