Package org.ddolib.examples.misp

Class MispProblem

java.lang.Object
org.ddolib.examples.misp.MispProblem
All Implemented Interfaces:
Problem<BitSet>
public class MispProblem extends Object implements Problem<BitSet>
Represents an instance of the Maximum Independent Set Problem (MISP) as a 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 BitSet indicating which nodes can still be selected. The solver explores decisions for each node to build an independent set of maximum weight.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final BitSet[]
    neighbors
    For each node i, neighbors[i] contains the adjacency list of i.
    final BitSet
    remainingNodes
    The remaining nodes that can be selected in the current independent set.
    final int[]
    weight
    For each node i, weight[i] contains the weight associated with i.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MispProblem(String fname)
    Loads a MISP problem from a DOT file.
    MispProblem(BitSet remainingNodes, BitSet[] neighbors, int[] weight)
    Constructs a MISP problem with a given state, adjacency lists, and weights.
    MispProblem(BitSet remainingNodes, BitSet[] neighbors, int[] weight, double optimal)
    Constructs a MISP problem with a given state, adjacency lists, weights, and known optimal value.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(BitSet state, int var)
    Returns the domain of possible values for a given variable when applied to a specific state.
    double
    evaluate(int[] solution)
    Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.
    BitSet
    initialState()
    Returns the initial state of the problem.
    double
    initialValue()
    Returns the initial objective value associated with the initial state.
    int
    nbVars()
     
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    String
    toString()
     
    BitSet
    transition(BitSet state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(BitSet state, Decision decision)
    Computes the change in objective value resulting from applying a decision to a given state.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • remainingNodes

      public final BitSet remainingNodes
      The remaining nodes that can be selected in the current independent set. Considered as the state of the decision diagram.

    • neighbors

      public final BitSet[] neighbors
      For each node i, neighbors[i] contains the adjacency list of i.

    • weight

      public final int[] weight
      For each node i, weight[i] contains the weight associated with i.

  • Constructor Details

    • MispProblem

      public MispProblem(BitSet remainingNodes, BitSet[] neighbors, int[] weight, double optimal)
      Constructs a MISP problem with a given state, adjacency lists, weights, and known optimal value.
      Parameters:
      remainingNodes - the initial set of selectable nodes
      neighbors - adjacency lists for each node
      weight - weights of each node
      optimal - known optimal solution value

    • MispProblem

      public MispProblem(BitSet remainingNodes, BitSet[] neighbors, int[] weight)
      Constructs a MISP problem with a given state, adjacency lists, and weights. The optimal solution is unknown.
      Parameters:
      remainingNodes - the initial set of selectable nodes
      neighbors - adjacency lists for each node
      weight - weights of each node

    • MispProblem

      public MispProblem(String fname) throws IOException
      Loads a MISP problem from a DOT file.

      The file must contain the list of nodes and edges. Node weights can be specified with [weight=w] (default weight is 1). If known, the optimal solution should be specified in the second line as optimal=x.

      Parameters:
      fname - path to the DOT file describing the graph
      Throws:
      IOException - if an error occurs while reading the file

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

      public int nbVars()
      Specified by:
      nbVars in interface Problem<BitSet>
      Returns:
      the total number of decision variables in this problem

    • initialState

      public BitSet initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<BitSet>
      Returns:
      the state representing the starting point of the optimization

    • initialValue

      public double initialValue()
      Description copied from interface: Problem
      Returns the initial objective value associated with the initial state.
      Specified by:
      initialValue in interface Problem<BitSet>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(BitSet state, int var)
      Description copied from interface: Problem
      Returns the domain of possible values for a given variable when applied to a specific state.
      Specified by:
      domain in interface Problem<BitSet>
      Parameters:
      state - the current state
      var - the variable index whose domain is queried
      Returns:
      an iterator over all feasible values for the variable in this state

    • transition

      public BitSet transition(BitSet state, Decision decision)
      Description copied from interface: Problem
      Applies a decision to a state, computing the next state according to the problem's transition function.
      Specified by:
      transition in interface Problem<BitSet>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the resulting state after applying the decision

    • transitionCost

      public double transitionCost(BitSet state, Decision decision)
      Description copied from interface: Problem
      Computes the change in objective value resulting from applying a decision to a given state.
      Specified by:
      transitionCost in interface Problem<BitSet>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the incremental objective cost/value associated with this decision

    • optimalValue

      public Optional<Double> optimalValue()
      Description copied from interface: Problem
      Returns the known optimal value of the problem, if available.

      Note: This value should correspond to the expected output of the solver. For maximization problems, be careful with negative values.

      Specified by:
      optimalValue in interface Problem<BitSet>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<BitSet>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.