Package org.ddolib.examples.srflp

Class SRFLPProblem

java.lang.Object
org.ddolib.examples.srflp.SRFLPProblem
All Implemented Interfaces:
Problem<SRFLPState>
public class SRFLPProblem extends Object implements Problem<SRFLPState>
A Single-Row Facility Layout Problem (SRFLP) instance.

This class implements the Problem interface and provides methods to:

Instances can be created either from raw arrays of lengths and flows, or by reading from a file with a specific format. The flows matrix must be symmetric.

This class is intended to be used with solvers such as A*, Decision Diagrams (DDO), or other combinatorial optimization frameworks that support the Problem interface.

See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    SRFLPProblem(int[] lengths, int[][] flows)
    Constructs a new SRFLP instance with given lengths and flows.
    SRFLPProblem(int[] lengths, int[][] flows, Optional<Double> optimal)
    Constructs a new SRFLP instance with given lengths, flows, and optional known optimal.
    SRFLPProblem(String fname)
    Reads an SRFLP instance from a file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(SRFLPState 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.
    SRFLPState
    initialState()
    Computes a constant initial value accounting for half the contribution of each department pair.
    double
    initialValue()
    Returns a constant accounting for all contributions of half department lengths.
    int
    nbVars()
     
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    String
    toString()
     
    SRFLPState
    transition(SRFLPState state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(SRFLPState 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

  • Constructor Details

    • SRFLPProblem

      public SRFLPProblem(int[] lengths, int[][] flows, Optional<Double> optimal)
      Constructs a new SRFLP instance with given lengths, flows, and optional known optimal.
      Parameters:
      lengths - The lengths of the departments.
      flows - The traffic flow matrix between departments (must be symmetric).
      optimal - Optional known optimal value for the instance.
      Throws:
      IllegalArgumentException - if flows is not symmetric.

    • SRFLPProblem

      public SRFLPProblem(int[] lengths, int[][] flows)
      Constructs a new SRFLP instance with given lengths and flows.
      Parameters:
      lengths - The lengths of the departments.
      flows - The traffic flow matrix between departments (must be symmetric).

    • SRFLPProblem

      public SRFLPProblem(String fname) throws IOException
      Reads an SRFLP instance from a file.

      The file should contain the number of departments on the first line, optionally followed by the known optimal value. The second line lists the department lengths, and subsequent lines provide the symmetric flow matrix.

      Parameters:
      fname - The filename to read.
      Throws:
      IOException - if the file cannot be read.

  • Method Details

    • nbVars

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

    • initialState

      public SRFLPState initialState()
      Computes a constant initial value accounting for half the contribution of each department pair.
      Specified by:
      initialState in interface Problem<SRFLPState>
      Returns:
      The root value of the problem.

    • initialValue

      public double initialValue()
      Returns a constant accounting for all contributions of half department lengths.
      Specified by:
      initialValue in interface Problem<SRFLPState>
      Returns:
      The problem's initial value

    • domain

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

    • toString

      public String toString()
      Overrides:
      toString in class Object