Skip to content

Independent Set

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/" folder within the code and execute IndependentSet/IndependentSetMain. 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 IndependentSetMain file, you will find a generalization of the IndependentSet problem. Here's how to work with it:

1. Provide a Dictionary of Variables:
  • Create a dictionary where the key is the variable's ID, 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.
  • Provide the variable IDs in the dict_node_neighbors 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.