Package org.ddolib.examples.maximumcoverage

Class MaxCoverProblem

java.lang.Object
org.ddolib.examples.maximumcoverage.MaxCoverProblem
All Implemented Interfaces:
Problem<MaxCoverState>
public class MaxCoverProblem extends Object implements Problem<MaxCoverState>
Represents an instance of the Maximum Coverage (MaxCover) problem.

This class implements the Problem interface and provides:

  • Creation of random or file-based problem instances
  • Evaluation of solutions and state transitions for Decision Diagram Optimization (DDO)
  • Computation of centralities for each item, used in heuristics
  • Support for reading/writing instances in a standard text format

The problem is defined by:

  • nbItems: the total number of items to cover
  • nbSubSets: the total number of available subsets
  • nbSubSetsToChoose: the number of subsets allowed to select
  • subSets: the array of BitSets representing the items covered by each subset
  • centralities: the relative frequency of each item appearing in subsets
  • optimal: optionally, the optimal solution value (for benchmarking)

  • Field Details

    • nbItems

      public final int nbItems
      Number of items in the instance.

    • nbSubSets

      public final int nbSubSets
      Number of subsets in the instance.

    • nbSubSetsToChoose

      public final int nbSubSetsToChoose
      Number of subsets that can be selected.

    • subSets

      public final BitSet[] subSets
      Array of subsets represented as BitSets, where each BitSet indicates the items it covers.

    • centralities

      public final double[] centralities
      Relative frequency (centrality) of each item in all subsets.

    • name

      public Optional<String> name
      Optional instance name.

    • optimal

      public Optional<Double> optimal
      Optional optimal solution value.

  • Constructor Details

    • MaxCoverProblem

      public MaxCoverProblem(Optional<String> name, int nbItems, int nbSubSets, int nbSubSetsToChoose, BitSet[] subSets, Optional<Double> optimal)
      Constructs a MaxCover instance with full specification.
      Parameters:
      name - optional instance name
      nbItems - number of items
      nbSubSets - number of subsets
      nbSubSetsToChoose - number of subsets allowed to select
      subSets - array of subsets represented as BitSets
      optimal - optional optimal solution value

    • MaxCoverProblem

      public MaxCoverProblem(int nbItems, int nbSubSets, int nbSubSetsToChoose, BitSet[] subSets, Optional<Double> optimal)
      Constructs a MaxCover instance without a name.
      Parameters:
      nbItems - number of items
      nbSubSets - number of subsets
      nbSubSetsToChoose - number of subsets allowed to select
      subSets - array of subsets represented as BitSets
      optimal - optional optimal solution value

    • MaxCoverProblem

      public MaxCoverProblem(int nbItems, int nbSubSets, int nbSubSetsToChoose, BitSet[] subSets)
      Constructs a MaxCover instance without name or optimal value.
      Parameters:
      nbItems - number of items
      nbSubSets - number of subsets
      nbSubSetsToChoose - number of subsets allowed to select
      subSets - array of subsets represented as BitSets

    • MaxCoverProblem

      public MaxCoverProblem(int n, int m, int k, double maxR, int seed)
      Generates a random MaxCover instance using coordinates and a distance threshold.
      Parameters:
      n - number of items
      m - number of subsets
      k - number of subsets to select
      maxR - maximum coverage radius
      seed - random seed

    • MaxCoverProblem

      public MaxCoverProblem(String fname) throws IOException
      Loads a MaxCover instance from a file.

      The file should contain the number of items, number of subsets, budget, optional optimal value, and the item indices for each subset.

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

  • Method Details

    • instanceFormat

      public String instanceFormat()
      Returns a formatted string representing the instance for writing to a file.
      Returns:
      the formatted instance as a string

    • nbVars

      public int nbVars()
      Returns the number of decision variables in the problem.
      Specified by:
      nbVars in interface Problem<MaxCoverState>
      Returns:
      number of variables (subsets to select)

    • initialState

      public MaxCoverState initialState()
      Returns the initial state for the DDO search.
      Specified by:
      initialState in interface Problem<MaxCoverState>
      Returns:
      a state with no items covered

    • initialValue

      public double initialValue()
      Returns the initial objective value for the initial state.
      Specified by:
      initialValue in interface Problem<MaxCoverState>
      Returns:
      0 (no items covered yet)

    • domain

      public Iterator<Integer> domain(MaxCoverState state, int var)
      Returns an iterator over the domain of values for a given variable in a state.
      Specified by:
      domain in interface Problem<MaxCoverState>
      Parameters:
      state - the current state
      var - the variable index
      Returns:
      an iterator over feasible subset indices (or -1 if no options)

    • transition

      public MaxCoverState transition(MaxCoverState state, Decision decision)
      Applies a decision to a state to produce a new state.
      Specified by:
      transition in interface Problem<MaxCoverState>
      Parameters:
      state - the current state
      decision - the decision to apply
      Returns:
      a new state reflecting the added subset

    • transitionCost

      public double transitionCost(MaxCoverState state, Decision decision)
      Returns the cost of applying a decision to a state.

      Cost is defined as the negative number of newly covered items.

      Specified by:
      transitionCost in interface Problem<MaxCoverState>
      Parameters:
      state - the current state
      decision - the decision to apply
      Returns:
      the transition cost

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the optimal value of the instance, if known.
      Specified by:
      optimalValue in interface Problem<MaxCoverState>
      Returns:
      the negative of the optimal value (for minimization DDO)

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Evaluates a complete solution.
      Specified by:
      evaluate in interface Problem<MaxCoverState>
      Parameters:
      solution - array of selected subset indices
      Returns:
      negative number of items covered
      Throws:
      InvalidSolutionException - if the solution length is incorrect

    • toString

      public String toString()
      Returns a string representation of the instance.
      Overrides:
      toString in class Object
      Returns:
      instance name, parameters, and subsets