MaximumWeightISInstance#
- class iqm.applications.mis.MaximumWeightISInstance(graph, penalty)[source]#
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 attributeweight
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 theweight
attribute.TypeError – If the weight of any node is a wrong data type (neither
float
norint
).
Attributes
Methods