Package org.ddolib.examples.maximumcoverage

Class MaxCoverRelax

java.lang.Object
org.ddolib.examples.maximumcoverage.MaxCoverRelax
All Implemented Interfaces:
Relaxation<MaxCoverState>
public class MaxCoverRelax extends Object implements Relaxation<MaxCoverState>
Relaxation operator for MaxCoverState in the Maximum Coverage problem.

This class implements Relaxation and defines how multiple states can be merged into a single relaxed state. It is typically used in Decision Diagram Optimization (DDO) to reduce the size of the diagram while maintaining an admissible relaxation.

The relaxation merges states by computing the intersection of their covered items. Additional statistics (total intersection size, number of merges, and number of zero intersections) are tracked for analysis or debugging purposes.

  • Constructor Details

    • MaxCoverRelax

      public MaxCoverRelax(MaxCoverProblem problem)
      Constructs a MaxCover relaxation operator for a given problem instance.
      Parameters:
      problem - the MaxCover problem instance

  • Method Details

    • mergeStates

      public MaxCoverState mergeStates(Iterator<MaxCoverState> states)
      Merges a collection of states into a single relaxed state.

      The merged state covers only the items that are common to all input states (intersection). This ensures the relaxation is admissible, as it does not overestimate coverage.

      Specified by:
      mergeStates in interface Relaxation<MaxCoverState>
      Parameters:
      states - an iterator over the states to merge
      Returns:
      a new MaxCoverState representing the intersection of the input states

    • relaxEdge

      public double relaxEdge(MaxCoverState from, MaxCoverState to, MaxCoverState merged, Decision d, double cost)
      Computes the relaxed cost of a transition between states.

      In this implementation, the cost is not modified by the relaxation and is returned as-is.

      Specified by:
      relaxEdge in interface Relaxation<MaxCoverState>
      Parameters:
      from - the source state
      to - the destination state
      merged - the merged state after relaxation
      d - the decision applied
      cost - the original transition cost
      Returns:
      the relaxed transition cost (same as input cost)