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
- Graph
-
- Supertypes
Members list
Value members
Concrete methods
Returns the domain of possible values for a given variable when applied to a specific state.
Returns the domain of possible values for a given variable when applied to a specific state.
Value parameters
- state
-
the current state
- variable
-
the variable index whose domain is queried
Attributes
- Returns
-
ll feasible values for the variable in this state
- Definition Classes
Given a solution such that solution(i) is the value of the variablex_i, returns the value of this solution and checks if the solution respects the problem's constraints.
Given a solution such that solution(i) is the value of the variablex_i, returns the value of this solution and checks if the solution respects the problem's constraints.
Value parameters
- solution
-
A solution of the problem.
Attributes
- Returns
-
The value of the input solution.
- Note
-
For maximization problems, the returned value is minus the computed value.
- Definition Classes
-
Problem -> Problem
Returns the initial state of the problem.
Returns the initial state of the problem.
Attributes
- Returns
-
the state representing the starting point of the optimization
- Definition Classes
-
Problem -> Problem
Returns the initial objective value associated with the initial state.
Returns the initial objective value associated with the initial state.
Attributes
- Returns
-
the starting value of the objective function
- Definition Classes
-
Problem -> Problem
Returns the total number of decision variables in this problem.
Returns the total number of decision variables in this problem.
Attributes
- Returns
-
the total number of decision variables in this problem
- Definition Classes
-
Problem -> Problem
Returns the optimal value of the problem if known
Returns the optimal value of the problem if known
Attributes
- Returns
-
the optimal value of the problem if known
- Definition Classes
Returns a string representation of the object.
Returns a string representation of the object.
The default representation is platform dependent.
Attributes
- Returns
-
a string representation of the object.
- Definition Classes
-
Any
Applies a decision to a state, computing the next state according to the problem's transition function.
Applies a decision to a state, computing the next state according to the problem's transition function.
Value parameters
- decision
-
the decision to apply
- state
-
the state from which the transition originates
Attributes
- Returns
-
the resulting state after applying the decision
- Definition Classes
-
Problem -> Problem
Computes the change in objective value resulting from applying a decision to a given state.
Computes the change in objective value resulting from applying a decision to a given state.
Value parameters
- decision
-
the decision to apply
- state
-
the state from which the transition originates
Attributes
- Returns
-
the incremental objective cost/value associated with this decision
- Definition Classes
-
Problem -> Problem
Inherited methods
Used by the solver. Converts the input of ouput of domainValues from Java to Scala and vice versa.
Used by the solver. Converts the input of ouput of domainValues from Java to Scala and vice versa.