MaximumWeightISInstance

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 has to have an attribute weight storing a number.

• 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 node of the input graph is missing the weight attribute.

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

Attributes

Methods