MaximumWeightISInstance

Module: iqm.applications.mis

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

Bases: ISInstance

The instance class for maximum-weight independent set problems.

The maximum-weight independent set problem refers to finding a subset of nodes of a graph, such that no nodes in the subset are connected by an edge and sum of the weights of the nodes in the subset is maximized. The class is initialized by initializing its parent class ISInstance with a custom objective function (carrying the weights of the graph nodes).

Parameters:

• graph (Graph) – The Graph describing the maximum-weight independent set problem. Each node of the graph needs to have an attribute (something like “weight”) storing a number. Specifically, the initialization method looks fornode attributes from the tuple NODE_ATTR_PRIORITY (in order) and takes the first one as the node weight.

• penalty (float | int) – The penalty to be incurred per each edge present in the solution, sometimes referred to as \(\lambda\) in the literature. The higher it is, the less likely the algorithm is to include an edge in the solution. This is needed when the problem formulation is transformed into QUBO.

• 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.

Raises:

• ValueError – If any of the input graph’s nodes doesn’t have any attribute from the tuple of attributes NODE_ATTR_PRIORITY.

• TypeError – If the weight of any node is a wrong data type (neither float nor int).

Attributes

highest_quality_bitstrings

The worst bitstring(s) for the MWIS problem, determined trivially if all weights are non-negative.

Methods

property highest_quality_bitstrings: set[str]

The worst bitstring(s) for the MWIS problem, determined trivially if all weights are non-negative.

Inheritance