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, JijSAParameters

sampler = 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

name	type	default	description
beta_min	Optional[float]	None	Minimum (initial) inverse temperature. If None, this will be set automatically.
beta_max	Optional[float]	None	Maximum (final) inverse temperature. If None, this will be set automatically.
num_sweeps	Optional[int]	None	The number of Monte-Carlo steps. If None, 1000 will be set.
num_reads	Optional[int]	None	The number of samples. If None, 1 will be set.
initial_state	Optional[dict]	None	Initial state. If None, this will be set automatically.
updater	Optional[str]	None	Updater algorithm. "single spin flip" or "swendsen wang". If None, "single spin flip" will be set.
sparse	Optional[bool]	None	If True, only non-zero matrix elements are stored, which will save memory. If None, False will be set.
reinitialize_state	Optional[bool]	None	If True, reinitialize state for each run. If None, True will be set.
seed	Optional[int]	None	Seed for Monte Carlo algorithm. If None, this will be set automatically.
needs_square_constraints	Optional[dict[str, bool]]	None	This 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_penalties	Optional[dict[str, bool]]	None	This 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

name	type	default	description
parameters	Optional[JijSAParameters]	None	Parameters for JijSASampler.
search	bool	False	If True, the parameter search will be carried out, which tries to find better values of multipliers for penalty terms.
num_search	int	15	The number of parameter search iteration. Defaults to set 15. This option works if search is True.
algorithm	Optional[Literal["v096", "v097-2", "v098"]]	None	Algorithm 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_time	Optional[Union[int, float]]	None	The 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.
sync	bool	True	If True, synchronous mode is enabled.
queue_name	Optional[str]	None	Queue name.