to_pubo
class BinaryModel
BinaryModel(coeff: 'dict[tuple[int, ...], float]', constant: 'float')
normalize (self, factor) -> -
class CompiledInstance
CompiledInstance: object return compile_model
method.
Attributes
- sense(jijmodeling.ProblemSense) : problem sense minimize or maximize.
- objective(SubstitutedExpression) : objective expression.
- constraint(dict[str, dict[tuple[int, ...], SubstitutedExpression]]) : constraints. str key represents name of constraint. tuple[int,...] is values of forall index.
- penalty : dict[str, dict[tuple[int, ...], SubstitutedExpression]]
- var_map : VariableMap
- data : InstanceData
- problem : jijmodeling.InstanceData
Examples
import jijmodeling as jm
import jijmodeling_transpiler as jmt
n = jm.Placeholder("n")
x = jm.Binary("x", (n, n))
i = jm.Element("i", n)
problem = jm.Problem("sample")
problem += x[:, :]
problem += jm.Constraint("onehot", x[:, i], forall=i)
compiled_instance = jmt.core.compile_model(problem, {"n": 2}, {})
compiled_instance
CompiledInstance(
objective=SubstitutedExpression(
linear=LinearSubstitutedExpr(coeff={0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0}, constant=0.0),
nonlinear=None),
constraint={
'onehot': {
(0,): SubstitutedExpression(
linear=LinearSubstitutedExpr(coeff={0: 1.0, 1: 1.0}, constant=0.0),
nonlinear=None),
(1,): SubstitutedExpression(
linear=LinearSubstitutedExpr(coeff={2: 1.0, 3: 1.0}, constant=0.0),
nonlinear=None)}
},
penalty={},
var_map=VariableMap(var_map={'x': {(0, 0): 0, (0, 1): 2, (1, 0): 1, (1, 1): 3}},
var_num=4,
integer_bound={}),
...
)
add (self, source) -> -
class ProblemSense
An enumeration.
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
is converted to a penalty term by the following equation:
where and are detail parameters for each constraint and is uniformal weight for each penalties.
is parameters provided to set the weights for each penalty,
independently of the index of the constraint and penalty.
You can set using multipliers
.
By default .
The weight of parameters and are set by detail_parameters
.
By default, and for the penalty is converted from equality constraint,
and and for the penalty is converted from inequality constraint.
For example, the following constraint
is converted to the following penalty term with multipliers={"onehot": 1}
and detail_parameters={"onehot": {(1,): (1/2, 1)}}
that means and :
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)
class SubstitutedExpression
SubstitutedExpression(coeff: 'dict[tuple[int, ...], float]', constant: 'float', order: 'int')
add (self, other) -> -
from_serializable (data) -> -
is_constant (self) -> -
mul (self, other) -> -
power (self, exponent) -> -
to_serializable (self) -> -
binary_multiply_reduction (coeff) -> -
subs_ir_to_binary (subs_ir, encoder) -> -
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
where is a vector of decision variables. This problem is transpiled to an unconstrained problem as follows.
- Squared penalty method (
relax_method == RelaxationMethod.SquaredPenalty
)
where and are penalty weights and 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.
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.