MaximumWeightISInstance

Module: iqm.applications.mis

class iqm.applications.mis.MaximumWeightISInstance(graph, penalty)

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.

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

fix_constraint_violation_bitstring

Postprocessing function that fixes a single bitstring, making it satisfy the constraints.

property highest_quality_bitstrings: set[str]

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

fix_constraint_violation_bitstring(bit_str)

Postprocessing function that fixes a single bitstring, making it satisfy the constraints.

It works in the following way:

1. Get the subgraph induced by the bitstring bit_str.

2. Find the approximate minimum-weight vertex cover of the graph with a greedy algorithm, breaking ties at random.

3. Remove those nodes from the induced subgraph.

4. Return the bitstring corresponding to the remaining subgraph (which is an independent subset of the original graph).

Parameters:

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

Returns:

A bitstring corresponding to greedily pruned bit_str.

Return type:

str

Inheritance