ISInstance

ISInstance#

class iqm.applications.mis.ISInstance(graph, penalty, objective)[source]#

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.

Attributes

graph

The graph corresponding to the problem.

Methods

_induced_subgraph_from_bitstring(bit_str)

Helper method that takes a bitstring representing a solution and returns the graph induced from it.

_recalculate_bqm()

The function calculating the BQM is relatively simple for independent set problems.

fix_variables(variables)

A method to fix 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)[source]#

A method to fix 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[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).

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