org.ddolibscala.example.misp
This package implements the acs, astar and ddo models for the Maximum Independent Set Problem (MISP).
Given a weighted graph πΊ = (π,πΈ,π€) where π= {1,...,π} is a set of vertices, πΈ \subset π Γπ the set of edges connecting those vertices and π€ = {π€1,π€2,...,π€π} is a set of weights s.t. π€π is the weight of node π. The problem consists in finding a subset of vertices in a graph such that no edge exists in the graph that connects two of the selected nodes and the sum of the weight of the selected nodes is maximal.
Attributes
Members list
Type members
Classlikes
Example of MISP resolution with A* solver
Example of MISP resolution with A* solver
Attributes
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
MispAstarMain.type
Example of MISP resolution with DDO Solver.
Example of MISP resolution with DDO Solver.
Attributes
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
MispDdoMain.type
Implementation of a dominance relation for the Maximum Independent Set Problem (MISP).
Implementation of a dominance relation for the Maximum Independent Set Problem (MISP).
In this context, one state state1 is considered dominated by another state state2 if all vertices selected in state1 are also selected in state2. This allows pruning suboptimal states during the search.
Attributes
- Supertypes
Compute a org.ddolibscala.modeling.FastLowerBound for the Maximum Independent Set Problem (MISP).
Compute a org.ddolibscala.modeling.FastLowerBound for the Maximum Independent Set Problem (MISP).
Value parameters
- problem
-
the associated MISP problem instance
Attributes
- Supertypes
Companion object of the MispProblem class.
Companion object of the MispProblem class.
Attributes
- Companion
- class
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
MispProblem.type
Represents an instance of the Maximum Independent Set Problem (MISP) as a org.ddolibscala.modeling.Problem.
Represents an instance of the Maximum Independent Set Problem (MISP) as a org.ddolibscala.modeling.Problem.
The problem is defined on a weighted undirected graph. Each node can either be included in the independent set or not, and selected nodes cannot be adjacent.
The state of the problem is represented by a Set indicating which nodes can still be selected. The solver explores decisions for each node to build an independent set of maximum weight.
Value parameters
- _optimal
-
the value of the optimal solution if known
- neighbors
-
adjacency list for each node
- nodes
-
all the nodes of the graph
- weights
-
weight of each node
Attributes
- Companion
- object
- Supertypes
Implements a ranking strategy for states in the Maximum Independent Set Problem (MISP).
Implements a ranking strategy for states in the Maximum Independent Set Problem (MISP).
The ranking is based on the number of remaining nodes in the state: a state with more remaining nodes is considered more promising for exploration in a decision diagram.
Attributes
- Supertypes
-
trait StateRanking[BitSet]trait StateRanking[BitSet]trait Comparator[BitSet]class Objecttrait Matchableclass AnyShow all
Implements a relaxation strategy for the Maximum Independent Set Problem (MISP) to be used in decision diagram optimization (DDO) algorithms.
Implements a relaxation strategy for the Maximum Independent Set Problem (MISP) to be used in decision diagram optimization (DDO) algorithms.
This relaxation defines how to merge multiple states and how to adjust transition costs when exploring the relaxed search space.
In this implementation:
- The merged state is computed as the union of all given states, meaning all nodes that are available in at least one state are considered available in the merged state.
- The edge relaxation does not modify the transition cost; it returns the original cost.
Attributes
- Supertypes