Skip to content

independentSet

Detailed Explanation of Optimization Problems and their Implementations

For a comprehensive understanding of these classes, it is recommended to thoroughly review the examples available in the "/Examples/IndependentSetInstance/IndependentSetProblem" folder within the code and execute the Main file. These examples are generic and open for testing different values. Below, we will explain the examples in detail.

Independent Set Problem

The Independent Set Problem is a fundamental problem in graph theory and combinatorial optimization. It involves finding a subset of vertices in a graph such that no two vertices in the subset are adjacent.

Components of the Independent Set Problem:

1. Graph:
  • A graph G=(V,E) consists of a set of vertices V and a set of edges E.
  • The edges represent connections between pairs of vertices.
2. Independent Set:
  • A subset of vertices S ⊆ V is an independent set if no two vertices in S are connected by an edge in E.
3. Objective:
  • The goal is often to find the largest independent set, i.e., the independent set with the maximum number of vertices.

Example:

Consider a graph with vertices {A, B, C, D, E} and edges {(A, B), (B, C), (C, D), (D, E), (A, E)}.

An example of an independent set in this graph is {A, C, E}. None of these vertices are directly connected by an edge.

Types of Independent Set Problems:

Maximum Independent Set:
  • Find the largest independent set in the graph.
  • This problem is NP-hard, meaning it is computationally challenging to solve exactly for large graphs.
Maximum Weight Independent Set:
  • Each vertex has a weight, and the goal is to find an independent set with the maximum total weight.
  • This is a generalization of the maximum independent set problem.

Applications:

  • Network design
  • Scheduling
  • Resource allocation
  • Social network analysis (e.g., finding non-interacting groups)

Implementation

In the IndependentSetProblem file, you will find a generalization of the IndependentSet problem. Here's how to work with it:

1. Provide a Dictionary of Vertices and Edges:
  • Create a dictionary where the key is the variable's ID (Vertices), and the value is a list of all nodes reachable in a single arc, formatted as integers.
2. Instantiate IndependentSet:
  • With the variables selected, create an instance of the IndependentSetProblem class.
3. Define Initial State and Variables:
  • Set the initial state in the initial_state parameter as a bitset.
  • Provide the variable IDs in the dict_node_neighbors explained in the point 1 along with their domain in the variables parameter.
4. Generate Decision Diagram:
  • After defining all the parameters, generate a decision diagram and test the other features.
5. Data Consistency Checks:
  • The implementation includes checks to ensure data consistency, avoiding any inconsistencies in the provided data.

By following these steps, you can effectively test and utilize the IndependentSet problem features.