Package org.ddolib.modeling

Interface Problem<T>

Type Parameters:
T - the type representing a state in the problem
All Known Implementing Classes:
ALPProblem, BKSProblem, GRProblem, KSProblem, LCSProblem, Max2SatProblem, MaxCoverProblem, MCPProblem, MispProblem, MKSProblem, MSCTProblem, PDPProblem, PSProblem, SMICProblem, SRFLPProblem, TSPProblem, TSProblem, TSPTWProblem
public interface Problem<T>
Represents an optimization problem formulated as a labeled transition system, following the semantics of dynamic programming.

A Problem defines the state space, the transitions between states induced by decisions, and the objective values associated with those transitions. Implementations provide the essential operations required by solvers such as SequentialSolver or ExactSolver.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(T 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.
    T
    initialState()
    Returns the initial state of the problem.
    double
    initialValue()
    Returns the initial objective value associated with the initial state.
    int
    nbVars()
     
    default Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    T
    transition(T state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(T state, Decision decision)
    Computes the change in objective value resulting from applying a decision to a given state.

  • Method Details

    • nbVars

      int nbVars()
      Returns:
      the total number of decision variables in this problem

    • initialState

      T initialState()
      Returns the initial state of the problem.
      Returns:
      the state representing the starting point of the optimization

    • initialValue

      double initialValue()
      Returns the initial objective value associated with the initial state.
      Returns:
      the starting value of the objective function

    • domain

      Iterator<Integer> domain(T state, int var)
      Returns the domain of possible values for a given variable when applied to a specific state.
      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

      T transition(T state, Decision decision)
      Applies a decision to a state, computing the next state according to the problem's transition function.
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the resulting state after applying the decision

    • transitionCost

      double transitionCost(T state, Decision decision)
      Computes the change in objective value resulting from applying a decision to a given state.
      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

      default Optional<Double> optimalValue()
      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.

      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • evaluate

      double evaluate(int[] solution) throws InvalidSolutionException
      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.

      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.