Package org.ddolib.examples.talentscheduling

Class TSProblem

java.lang.Object
org.ddolib.examples.talentscheduling.TSProblem
All Implemented Interfaces:
Problem<TSState>
public class TSProblem extends Object implements Problem<TSState>
The Talent Scheduling Problem (TSP) instance.

In the Talent Scheduling Problem, we have a set of scenes to shoot, each requiring a subset of actors, and each actor has an associated cost per day. The objective is to schedule the scenes to minimize the total cost of actors while respecting scene requirements.

This class implements the Problem interface for use with search algorithms (ACS, A*, DDO, etc.). It provides methods to get the initial state, compute transition costs, and define the domain for each state variable.

The problem can be constructed either:

  • From explicit data arrays (number of scenes, number of actors, actor costs, scene durations, and actor requirements),
  • Or by reading a data file in the format used in the Talent Scheduling Problem dataset (source).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final Optional<Double>
    optimal
    The optimal solution value if known (optional, used for testing and benchmarking).

  • Constructor Summary

    Constructors
    Constructor
    Description
    TSProblem(int nbScene, int nbActors, int[] costs, int[] duration, BitSet[] actors, Optional<Double> optimal)
    Constructs a TSP instance from explicit parameters.
    TSProblem(String fname)
    Constructs a TSP instance by reading a file in the standard dataset format.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(TSState 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.
    TSState
    initialState()
    Returns the initial state of the problem.
    double
    initialValue()
    Returns the initial objective value associated with the initial state.
    int
    nbVars()
     
    BitSet
    onLocationActors(BitSet remainingScenes, BitSet maybeScenes)
     
    BitSet
    onLocationActors(TSState state)
    Returns the set of actors already present on location at the current state, i.e., actors involved in past scenes and needed for future scenes.
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    int
    sceneCost(int scene)
     
    String
    toString()
     
    TSState
    transition(TSState state, Decision decision)
    Applies a decision to a state, computing the next state according to the problem's transition function.
    double
    transitionCost(TSState 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

    • optimal

      public final Optional<Double> optimal
      The optimal solution value if known (optional, used for testing and benchmarking).

  • Constructor Details

    • TSProblem

      public TSProblem(int nbScene, int nbActors, int[] costs, int[] duration, BitSet[] actors, Optional<Double> optimal)
      Constructs a TSP instance from explicit parameters.
      Parameters:
      nbScene - Number of scenes.
      nbActors - Number of actors.
      costs - Array containing the cost of each actor per day.
      duration - Array containing the duration of each scene.
      actors - Array of BitSets representing the actors required for each scene.
      optimal - Optional value of the optimal solution, if known.

    • TSProblem

      public TSProblem(String fname) throws IOException
      Constructs a TSP instance by reading a file in the standard dataset format.
      Parameters:
      fname - Path to the input file.
      Throws:
      IOException - If an I/O error occurs while reading the file.

  • Method Details

    • nbVars

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

    • initialState

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

    • domain

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

    • sceneCost

      public int sceneCost(int scene)

    • onLocationActors

      public BitSet onLocationActors(TSState state)
      Returns the set of actors already present on location at the current state, i.e., actors involved in past scenes and needed for future scenes.
      Parameters:
      state - Current state of the MDD.
      Returns:
      BitSet of actors currently on location.

    • onLocationActors

      public BitSet onLocationActors(BitSet remainingScenes, BitSet maybeScenes)

    • toString

      public String toString()
      Overrides:
      toString in class Object