ConstrainedQuadraticInstance

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

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.

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

_recalculate_bqm()
constraints_checker(bit_str)	Checks whether the constrains of the problem are satisfied.
fix_constraint_violation(counts)	Post-processing which takes a dictionary of counts and changes the bitstrings in it in some minimal way so that they all satisfy the constraints.
fix_constraint_violation_bitstring(bit_str)	Post-processing which takes a solution and changes it in some minimal way so that it satisfies the constraints.
fix_variables(variables)	Fixes (assigns) some of the problem variables.
initialize_properties([max_size])	The initialization method for upper/lower bound, average/best quality.
loss(bit_str)	The loss function calculated for a given solution.
quality(bit_str)	The quality function overridden for constrainted problems.
satisfy_constraints(counts)	Post-processing method that takes a dictionary 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)

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[Hashable] | 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).

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.

For solutions violating the constraints, the “quality” isn’t defined. If a user asks for the quality of the solution, this function first checks if the constraints are satisfied, prints out a warning if they aren’t, and then returns the loss function.

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.

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)

Post-processing which takes a dictionary of counts and changes the bitstrings in it in some minimal way so that they all 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.

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)

Post-processing which takes a solution and changes 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)

Post-processing method that takes a dictionary and removes the bitstrings which don’t satisfy the constraints.

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]