pubo

class BinaryModel

BinaryModel(coeff: 'dict[tuple[int, ...], float]', constant: 'float')

normalize (self, factor) -> -

---

class PuboBuilder

A class to build a PUBO from a problem and an instance.

Attributes

• objective(BinaryModel) : a binary model of the objective function
• linear_penalty(dict[str, dict[tuple[int, ...], BinaryModel]]) : a binary model of linear penalties
• penalty(dict[str, dict[tuple[int, ...], BinaryModel]]) : a binary model of penalties
• custom_penalty(dict[str, dict[tuple[int, ...], BinaryModel]]) : a binary model of custom penalties
• binary_encoder(dict[str, IntegerEncoder]) : a binary encoder for each variable
• constraint_expr(dict[str, jm.Constraint]) : a constraint expression
• obj_norm(float) : a normalization factor of the objective function
• const_norm(dict[str, dict[tuple[int, ...], float]]) : a normalization factor of constraints
• pena_norm(dict[str, dict[tuple[int, ...], float]]) : a normalization factor of penalties

get_hubo_dict (self, multipliers, detail_parameters) -> tuple[dict[tuple[int, ...], float], float]

Get a HUBO from the built PUBO.

A constraint with label=const

$$g_k(x) = C_k, \forall k$$

is converted to a penalty term by the following equation:

$$A_{\text{const}} \left[\sum_{k} \lambda_k \left( g_k(x) - C_k \right)^2 + \sum_k \mu_k (g_k(x) - C_k) \right]$$

where $\lambda_k$ and $\mu_k$ are detail parameters for each constraint and $A_{\text{const}}$ is uniformal weight for each penalties.

$A$ is parameters provided to set the weights for each penalty, independently of the index of the constraint and penalty. You can set $A$ using multipliers. By default $A=1$.

The weight of parameters $\lambda_k$ and $\mu_k$ are set by detail_parameters. By default, $\lambda_k=1$ and $\mu_k=0$ for the penalty is converted from equality constraint, and $\lambda_k=1$ and $\mu_k=1$ for the penalty is converted from inequality constraint.

For example, the following constraint

$$\sum_{i=1}^N x_{ij} = 1, \forall j \in \{0, 1\}~\text{label=onehot}$$

is converted to the following penalty term with multipliers={"onehot": 1} and detail_parameters={"onehot": {(1,): (1/2, 1)}} that means $A_{\text{onehot}}=1$ and $\lambda_{1}=1/2, \mu_{1}=1$:

$$\begin{align} &A_{\text{onehot}}\sum_j \left(\lambda_j \left(\sum_{i=1}^N x_{ij} - 1\right)^2 + \mu_j \left(\sum_{i=1}^N x_{ij} - 1\right)\right)\\ &= \left(\sum_{i=1}^N x_{i0} - 1\right)^2 + \frac{1}{2}\left(\sum_{i=1}^N x_{i1} - 1\right)^2 + \left(\sum_{i=1}^N x_{i1} - 1\right) \end{align}$$

Parameters

• multipliers(dict[str, float]) : a multiplier for each penalty. Defaults to None.
• detail_parameters(dict[str, dict[tuple[int, ...], tuple[float, float]]]) : detail parameters for each penalty. Defaults to None.

Returns

• tuple[dict[tuple[int, ...], float], float] : a HUBO dictionary and a constant term

get_qubo_dict (self, multipliers, detail_parameters) -> dict[tuple[int, int], float]

Get a QUBO COO format dictionary.

Please see the document of get_hubo_dict for the detail.

Parameters

• multipliers(dict[str, float]) : a multiplier for each penalty. Defaults to None.
• detail_parameters(dict[str, dict[tuple[int, ...], tuple[float, float]]]) : detail parameters for each penalty. Defaults to None.

Returns

• dict[tuple[int, int], float] : a QUBO dictionary

---

class RelaxationMethod

Relaxation method.

• SquaredPenalty: Squared penalty method
• AugmentedLagirangian: Augmented Lagrangian method (default)

---

decode_from_openjij (response, pubo_builder, compiled_model) -> jm.SampleSet

decode from openjij response to jijmodeling SampleSet.

Parameters

• response(oj.Response) : openjij response.
• pubo_builder(PuboBuilder) : pubo builder.
• compiled_model(CompiledInstance) : compiled model.

Returns

• jm.SampleSet : decoded sample set.

---

transpile_to_pubo (compiled_model, normalize, integer_encoders, relax_method, convert_to_penalty, square_penalty) -> PuboBuilder

Transpile to PUBO.

PUBO is polynomial unconstrained binary optimization. This function transpile to PUBO from compiled model.

In this function, integer variables are encoded to binary variables and constraints are relaxed to objective function.

In the following, we explain how to transpile to PUBO. Original problem is

$$\begin{aligned} \min_x~& f(x) \\ \text{subject to}~& g_k(x) \leq C_k ~\forall k \\ & h_l(x) = B_l \forall l \\ \end{aligned}$$

where $x$ is a vector of decision variables. This problem is transpiled to an unconstrained problem as follows.

• Squared penalty method (relax_method == RelaxationMethod.SquaredPenalty)

$$\begin{aligned} \min_{x, S_{C_k}} & f(x) + \sum_k \lambda_k \left(g_k(x) - S_{C_k}\right)^2 + \sum_l {\lambda'}_l \left(h_l(x) - B_l\right)^2 \\ & x \in \{0, 1\}^n, 0 \leq S_{C_k} \leq C_k, S_{C_k} \in \mathbb{Z}\\ \end{aligned}$$

where $\lambda_k$ and ${\lambda'}_l$ are penalty weights and $S_{C_k}$ is slack variable.

• Augmented Lagrangian method (relax_method == RelaxationMethod.AugmentedLagrangian)

The Augmented Lagrangian method is a method for continuous optimization that includes an algorithm for adjusting the weights of terms added as penalties, but here we refere to the conversion to Laguranian functions used in the Aurgumented Lagrangian method. Also note that unlike the original Augmented Lagrangian method, the weight of penalties do not have 1/2.

$$\min_x~ f(x) + \sum_k \lambda_k \left(g_k(x) - C_k\right)^2 + \sum_l \mu_l \left(g_l(x) - B_l\right)^2 + \sum_k \lambda_k \left(g_k(x) - C_k\right)^2 + \sum_l \mu_l \left(h_l(x) - B_l\right)^2$$

Parameters

• compiled_model(CompiledInstance) : Compiled model.
• normalize(bool) : Normalize objective function. Defaults to True.
• integer_encoders(dict[str, Int2BinaryEncoderDecoder]) : Integer encoder. Defaults to None.
• relax_method(RelaxationMethod) : Relaxation method. Defaults to RelaxationMethod.AugmentedLagrangian.
• with_penalty : (dict[str, bool], optional): Constraint automatically convert to penalty. Defaults all constraint convert to a penalty.
• square_penalty : (dict[str, bool], optional): Constraints will be squared or not as a penalty. Defaults all constraint will be squared.

Returns

• PuboBuilder : PUBO builder.