Package org.ddolib.examples.gruler

Class GRRelax

java.lang.Object

org.ddolib.examples.gruler.GRRelax

All Implemented Interfaces:

Relaxation<GRState>

public class GRRelax
extends Object
implements Relaxation<GRState>

Relaxation operator for the Golomb Ruler (GR) problem.

This class defines how multiple search states (GRState) can be merged to create a relaxed (i.e., aggregated) state during search algorithms such as DDO (Decision Diagram Optimization) or Anytime Column Search.

The relaxation used here computes the intersection of the sets of marks and distances present in the input states. This ensures that only marks and distances common to all states are kept in the merged state. The resulting state represents a conservative approximation that does not introduce new distances, preserving feasibility.

The last mark in the merged state is the minimum of all last marks across the input states, ensuring consistency with the most constrained (shortest) partial ruler.

Example:

 GRRelax relax = new GRRelax();
 GRState merged = relax.mergeStates(List.of(state1, state2).iterator());
 

See Also:

• GRState
• Relaxation

Constructor Summary

Constructors

Constructor	Description
GRRelax()

Method Summary

Modifier and Type	Method	Description
GRState	mergeStates(Iterator<GRState> states)	Merges several GRState objects into a single relaxed state.
double	relaxEdge(GRState from, GRState to, GRState merged, Decision d, double cost)	Computes the relaxed cost of transitioning between two states in the relaxed problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

GRRelax

public GRRelax()

Method Details

mergeStates

public GRState mergeStates(Iterator<GRState> states)

Merges several GRState objects into a single relaxed state.

The resulting state contains:

• The intersection of all mark sets (only marks present in all states are kept).
• The intersection of all distance sets (only distances present in all states are kept).
• The smallest lastMark value among all merged states.

Specified by:

mergeStates in interface Relaxation<GRState>

Parameters:

states - an iterator over the states to merge.

Returns:

a new GRState representing the relaxed (merged) state.

relaxEdge

public double relaxEdge(GRState from,
 GRState to,
 GRState merged,
 Decision d,
 double cost)

Computes the relaxed cost of transitioning between two states in the relaxed problem.

In this implementation, the relaxation does not modify the cost — it simply returns the same value as the original transition cost.

Specified by:

relaxEdge in interface Relaxation<GRState>

Parameters:

from - the source state before the transition.

to - the destination state after the transition.

merged - the merged relaxed state (unused in this relaxation).

d - the decision made for the transition.

cost - the original transition cost.

Returns:

the relaxed transition cost (equal to cost).