ISInstance

Module: iqm.applications.mis

class iqm.applications.mis.ISInstance(graph, penalty, objective, allow_custom_var_names=False)

Bases: ConstrainedQuadraticInstance

The instance class for independent set problems on a graph with a custom cost function.

The objective of this class of problems is selecting a subset of nodes in a graph, such that no two nodes in the selected subset are connected by an edge, while minimizing some cost function. This class can be instantiated by giving it a graph, a penalty to the cost function to be incurred for each violation of the constraint (when the problem is converted to QUBO) and an objective function as a BinaryQuadraticModel. This class is not intended to be instantiated directly, but rather by its subclasses MISInstance and MaximumWeightISInstance. But if the user does the work of defining their own objective function, there is no harm in instantiating an object of ISInstance.

Parameters:

• graph (Graph) – The graph from which independent sets are to be picked.

• penalty (float | int) – The penalty to be incurred per each edge present in the solution. This is needed when the problem formulation is transformed into QUBO.

• objective (BinaryQuadraticModel) – The objective function to be minimized by the independent set.

• allow_custom_var_names (bool) – Determines whether it’s allowed for graph to have nodes labelled by anything other than consecutive integers starting at 0.

Attributes

graph

The graph corresponding to the problem.

Methods

draw_problem	The method to draw an instance of independent set, with the solution highlighted.
fix_variables	A method to fix (assign) some of the problem variables.

property graph: Graph

The graph corresponding to the problem.

Equals the graph that was given on initialization of MISInstance and shouldn’t be modified. Instead of modifying the graph, the user should instantiate a new object of MISInstance.

fix_variables(variables, original_labels=False)

A method to fix (assign) some of the problem variables.

When a variable is fixed to 1, all of its neighboring variables are fixed to 0 (because of the constraints).

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.

Raises:

• ValueError – If the user is trying to fix two neighbouring nodes to 1, violating the independence constraint.

• ValueError – If one of the variables has already been fixed previously to a different value.

Return type:

None

draw_problem(solution_bitstring=None, seed=None)

The method to draw an instance of independent set, with the solution highlighted.

Parameters:

• solution_bitstring (str | None) – A bitstring representing a solution to the problem. Selected nodes are represented as 1’s, the other nodes are represented as 0’s. This skips nodes that have been fixed. The full bitstring including the fixed nodes is restored internally by calling restore_fixed_variables_bitstring().

• seed (int | None) – The seed to derandomize the layout of the graph.

Return type:

None

Inheritance