ConstrainedQuadraticInstance

Module: iqm.applications.qubo

class iqm.applications.qubo.ConstrainedQuadraticInstance(cqm, penalty=1.0, allow_custom_var_names=False)

Bases: ProblemInstance

A class for constrainted quadratic binary problems.

The class saves the problem as a ConstrainedQuadraticModel and uses this object for its various methods. When the problem needs to be transformed into a QUBO, a private method _recalculate_bqm() is used to return a BinaryQuadraticModel formulation of the problem, making the constraints soft and penalizing their breaking with penalty.

Parameters:

• cqm (ConstrainedQuadraticModel) – The problem encoded as a ConstrainedQuadraticModel, passed over from a subclass.

• penalty (float) – The numerical penalty incurred by violating each constraint of the problem, to be used when the problem is transformed into a BQM.

• allow_custom_var_names (bool) – Specifies whether the variable names should be renamed or if their original names should be kept. Internally, variables are labelled by consecutive integers starting from 0, so if the variables in the input cqm have different names, this should be set to True.

Attributes

bqm	The BQM representation of the problem, penalizing constraint violation.
cqm	The ConstrainedQuadraticModel representation of the problem instance.
dim	The dimension of the problem (i.e., the number of binary variables).
penalty	The penalty for breaking the constraints.
qubo_graph	The QUBO graph of the problem instance.
qubo_matrix	The QUBO matrix of the problem instance.

Methods

constraints_checker	Checks whether the constrains of the problem are satisfied.
fix_constraint_violation	Take a dictionary and change the bitstrings in it in some minimal way so that they satisfy the constraints.
fix_constraint_violation_bitstring	Take a solution bitstring and change it in some minimal way so that it satisfies the constraints.
fix_variables	Fixes (assigns) some of the problem variables.
initialize_properties	The initialization method for upper/lower bound, average/best quality and the corresponding bitstrings.
loss	The loss function calculated for a given solution.
quality	The quality function overridden for constrainted problems.
satisfy_constraints	Take a dictionary of counts and removes the bitstrings which don't satisfy the constraints.

property cqm: ConstrainedQuadraticModel

The ConstrainedQuadraticModel representation of the problem instance.

property dim: int

The dimension of the problem (i.e., the number of binary variables).

property bqm: BinaryQuadraticModel

The BQM representation of the problem, penalizing constraint violation.

The problem represented as BinaryQuadraticModel. This is calculated using _recalculate_bqm() by inserting the constraints as penalties to the cost function.

fix_variables(variables, original_labels=False)

Fixes (assigns) some of the problem variables.

This method is not implemented in ConstrainedQuadraticInstance because in the general case, fixing one variable might have implications for the other variables (implied by the constraints). Therefore, this method needs to be implemented in a subclass of ConstrainedQuadraticInstance, if it’s needed.

Parameters:

• variables (list[int] | list[Hashable] | dict[int, int] | dict[Hashable, int]) – Either a list of variables (which get all fixed to the value 1) or a dictionary with keys equal to the variables to fix and whose values are equal to the values to fix them to (either 1 or 0).

• original_labels (bool) – Is the input using the original variable labels (in case they were labeled with e.g., strings or non-consecutive integers)? This refers to the fact that the input to the problem instance (in this case the input graph of ISInstance) may have variables labelled by any hashable, aliased as dimod.typing.Variable in dimod. On initialization of the problem instance, the problem variables are re-labeled by consecutive integers starting from 0 (for internal consistancy). If original_labels is set to True, this method fix_variables() is expected to receive the original names of the variables instead of their new integer labels.

Return type:

None

property penalty: float

The penalty for breaking the constraints.

property qubo_matrix: ndarray

The QUBO matrix of the problem instance.

The matrix is obtained from the internal attribute bqm.

• The i,i diagonal entry corresponds to the local field acting on the i-th variable.

• The i,j entry above the diagonal corresponds to the interaction between the i-th and j-th variables.

• The entries below the diagonal are empty.

property qubo_graph: Graph

The QUBO graph of the problem instance.

The nodes / edges of the graph have a bias parameter containing the local field / interaction strength of the corresponding variable(s). Variables without interaction aren’t connected by edges in the graph.

constraints_checker(bit_str)

Checks whether the constrains of the problem are satisfied.

Parameters:

bit_str (str) – A bitstring representing a solution.

Returns:

Bool indicating whether the solution satisfies the constraints or not.

Return type:

bool

loss(bit_str)

The loss function calculated for a given solution.

It is equivalent to the quality of the solution, but with extra penalties for breaking the constraints.

Parameters:

bit_str (str) – A bitstring representing a solution.

Returns:

The loss of the solution.

Return type:

float

quality(bit_str)

The quality function overridden for constrainted problems.

Technically, for solutions violating the constraints, the “quality” isn’t defined. The corresponding quantity is loss(). However, for simplicity, if a user calls this method, it just redirects to loss().

Parameters:

bit_str (str) – A bitstring representing a solution.

Returns:

The loss of the solution and a printed warning if the solution violates the constraints.

Return type:

float

initialize_properties(max_size=30)

The initialization method for upper/lower bound, average/best quality and the corresponding bitstrings.

This is the method from the parent class ProblemInstance, overridden so that the bruteforce search only includes solutions which satisfy the constraints.

Parameters:

max_size (int | None) – The maximum size of problems for which the properties may be calculated.

Raises:

ValueError – If initialize_properties() was called on a ConstrainedQuadraticInstance object with dimension larger than max_size.

Return type:

None

fix_constraint_violation(counts)

Take a dictionary and change the bitstrings in it in some minimal way so that they satisfy the constraints.

Iterates through the dictionary counts and for each key calls fix_constraint_violation_bitstring(). In case that multiple bitstrings get mapped to the same bitstring, their respective frequencies (values) are added.

Warning

The bitstrings in the counts need to be ordered the same way as the variables of the problem. If you’re using a dictionary of counts obtained directly from a qiskit experiment, you need to reverse the order of the bitstrings (keys of the counts dictionary) first.

Parameters:

counts (dict[str, int]) – The dictionary of bitstrings with their frequencies as values.

Returns:

The input dictionary modified so that the keys now satisfy the problem constraints.

Return type:

dict[str, int]

fix_constraint_violation_bitstring(bit_str)

Take a solution bitstring and change it in some minimal way so that it satisfies the constraints.

This is not possible to do generally, so this method is not implemented for :class:ConstrainedQuadraticInstance` and it needs to be defined for the individual subclasses of ConstrainedQuadraticInstance (if it’s possible to do). If the input bitstring bit_str already satisfies the problem constraints, it should be returned unchanged.

Parameters:

bit_str (str) – The bitstring to be modified to satisfy the constraints.

Returns:

The bitstring modified in some minimal way to satisfy the constraints.

Return type:

str

satisfy_constraints(counts)

Take a dictionary of counts and removes the bitstrings which don’t satisfy the constraints.

If none of the counts satisfy the constraints, the returned dictionary will be empty.

Warning

The bitstrings in the counts need to be ordered the same way as the variables of the problem. If you’re using a dictionary of counts obtained directly from a qiskit experiment, you need to reverse the order of the bitstrings (keys of the counts dictionary) first.

Parameters:

counts (dict[str, int]) – A dictionary of counts, with solution strings as keys and their frequencies as values.

Returns:

The same dictionary as inputted, except with removed entries whose keys don’t satisfy the problem constraints.

Return type:

dict[str, int]

Inheritance