Package org.ddolib.examples.mcp

Class MCPProblem

java.lang.Object
org.ddolib.examples.mcp.MCPProblem
All Implemented Interfaces:
Problem<MCPState>
public class MCPProblem extends Object implements Problem<MCPState>
Represents an instance of the Maximum Cut Problem (MCP).

In the MCP, given a weighted undirected graph, the goal is to partition the nodes into two sets (S and T) such that the sum of the weights of edges between the sets is maximized.

This class implements the Problem interface and provides methods for:

  • Initializing the problem from a graph or a file.
  • Defining the decision domain (which partition a node belongs to).
  • Computing transitions and transition costs between states.
  • Accessing the initial state and value, and optional optimal value.

Constants S and T are used to model decisions: placing a node in partition S or T, respectively.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    Optional<Double>
    optimal
    Optional known optimal value for the problem instance.
    final int
    S
    Constant to model decision "put in partition S".
    final int
    T
    Constant to model decision "put in partition T".

  • Constructor Summary

    Constructors
    Constructor
    Description
    MCPProblem(String fname)
    Constructs an MCP problem by reading an instance from a file.
    MCPProblem(Graph graph)
    Constructs an MCP problem from a given graph.
    MCPProblem(Graph graph, Double optimal)
    Constructs an MCP problem from a given graph and known optimal value.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(MCPState 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.
    MCPState
    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()
     
    MCPState
    transition(MCPState state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(MCPState 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

    • S

      public final int S
      Constant to model decision "put in partition S".
      See Also:

    • T

      public final int T
      Constant to model decision "put in partition T".
      See Also:

    • optimal

      public Optional<Double> optimal
      Optional known optimal value for the problem instance.

  • Constructor Details

    • MCPProblem

      public MCPProblem(Graph graph)
      Constructs an MCP problem from a given graph.
      Parameters:
      graph - the graph representing the instance

    • MCPProblem

      public MCPProblem(Graph graph, Double optimal)
      Constructs an MCP problem from a given graph and known optimal value.
      Parameters:
      graph - the graph representing the instance
      optimal - the known optimal value of the instance

    • MCPProblem

      public MCPProblem(String fname) throws IOException
      Constructs an MCP problem by reading an instance from a file.

      The file should contain the number of nodes and the adjacency matrix of weights, optionally including the optimal solution value.

      Parameters:
      fname - the path to the file containing the instance
      Throws:
      IOException - if the file cannot be read

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

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

    • initialState

      public MCPState initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<MCPState>
      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<MCPState>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(MCPState 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<MCPState>
      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 MCPState transition(MCPState 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<MCPState>
      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(MCPState 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<MCPState>
      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<MCPState>
      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<MCPState>
      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.