ApproximationControl

Controls for functions related to state space approximation

IsApplyStateFiltering

public override bool IsApplyStateFiltering()

Definition

Defines whether to filter the state to be explored. There are two types of logic for filtering states:

• Global filtering: filters on states in stages.

• Local filtering: filters on state transitions.

Return

Type	Description	Default
Boolean	Whether to apply state filtering logic.	False

Example (Default Logic)

public override bool IsApplyStateFiltering()
{
    return false;
}

IsApplyApproximation

public override bool IsApplyApproximation()

Definition

Whether to apply the approximation method to filter the states during global filtering.

Return

Type	Description	Default
Boolean	Whether to apply approximation logic to global filtering.	False

Example (Default Logic)

public override bool IsApplyApproximation()
{
    return false;
}

IsUseEstimationValue

public override bool IsUseEstimationValue()

Definition

Set whether to calculate and utilize value estimates in states.

Return

Type	Description	Default
Boolean	True: Apply False: Do not apply	False

Example (Default Logic)

public override bool IsUseEstimationValue()
{
    return false;
}

GetEstimationValueUpdatePeriod

public override int GetEstimationValueUpdatePeriod()

Definition

Sets the frequency at which the value estimate is calculated for a state. In other words, if that frequency is n, then every nth state, the value estimate for the state is calculated.

Return

Type	Description	Default
Integer	The frequency at which the value estimate of the state is calculated.	1

Example (Default Logic)

public override int GetEstimationValueUpdatePeriod()
{
    return 1;
}

GetEstimationValueStopStageIndex

public override int GetEstimationValueStopStageIndex()

Definition

Set the stage index at which to stop calculating the estimated value of the state. In other words, if the value is n and the stage Index is greater than n, the state value estimate is not calculated.

Return

Type	Description	Default
Integer	The stage index at which to start calculating the estimated value of the state.	Int32.MaxValue

Example (Default Logic)

public override int GetEstimationValueStopStageIndex()
{
    return Int32.MaxValue;
}

GetStateFilteringType

public override StateFilteringType GetStateFilteringType()

Definition

Set up logic to filter the states to explore.

Return

Type	Description	Default
StateFilteringType	State filtering type.	Default Logic

Example (Default Logic)

public override StateFilteringType GetStateFilteringType()
{
    return StateFilteringType.Global;
}

GetGlobalTransitionCount

public override int GetGlobalTransitionCount()

Definition

Sets the number of states to explore when applying global filtering. For example, if you set the value to 1000, only 1000 states will remain in the stage, and the remaining states will be excluded.

Definition

Type	Description	Default
Integer	The number of states to explore after global filtering.	1000

Example (Default Logic)

public override int GetGlobalTransitionCount()
{
    return 1000;
}

GetApproximationTransitionCount

public override int GetApproximationTransitionCount() 

Definition

Sets the number of states to explore when applying global filtering using the approximation method. For example, if you set the value to 1000, only 1000 states will remain in the stage, and the remaining states will be excluded.

Return

Type	Description	Default
Integer	The number of states to explore after global filtering using the approximation method.	10

Example (Default Logic)

public override int GetApproximationTransitionCount() 
{
    return 10;
}

GetClusterTransitionCount

public override int GetClusterTransitionCount()

Definition

Sets the number of states to explore when applying global filtering using the state clustering method. For example, if you set the value to 10, only 10 states will remain in the stage, and the remaining states will be excluded.

Return

Type	Description	Default
Integer	The number of states to explore after global filtering using the state clustering method.	2

Example (Default Logic)

public override int GetClusterTransitionCount() 
{
    return 2;
}

GetLocalTransitionCount

public override int GetLocalTransitionCount()

Definition

Sets the number of states to explore when applying local filtering. For example, if you set the value to 1, only 1 of the state transitions from a state will be selected to navigate to the next state defined in that transition.

Return

Type	Description	Default
Integer	The number of states to explore after local filtering.	1

Example (Default Logic)

public override int GetLocalTransitionCount()
{
    return 1;
}

GetGlobalFilteringStartStageIndex

public override int GetGlobalFilteringStartStageIndex()

Definition

Sets the stage index to start applying the global filtering logic. For example, if you set this value to 0, the global filtering logic will be applied to all stages with an Index greater than or equal to 0.

Return

Type	Description	Default
Integer	The stage index to start applying the global filtering logic.	0

Example (Default Logic)

public override int GetGlobalFilteringStartStageIndex()
{
    return 0;
}

GetLocalFilteringStartStageIndex

public override int GetLocalFilteringStartStageIndex()

Definition

Sets the stage index to start applying the local filtering logic. For example, if you set this value to 0, the local filtering logic will be applied to all stages with an Index greater than or equal to 0.

Return

Type	Description	Default
Integer	The stage index to start applying the local filtering logic.	0

Example (Default Logic)

public override int GetLocalFilteringStartStageIndex()
{
    return 0;
}

GetApproximationStartStageIndex

public override int GetApproximationStartStageIndex()

Definition

Sets the stage index to start applying the global filtering logic using approximation method. For example, if you set this value to 0, the approximation method will be applied to all stages with an Index greater than or equal to 0.

Return

Type	Description	Default
Integer	The stage index to start applying the global filtering logic using approximation method.	0

Example (Default Logic)

public override int GetApproximationStartStageIndex()
{
    return 0;
}

GetMinimumTransitionCost

public override double GetMinimumTransitionCost()

Definition

Sets the smallest transition cost for all possible transitions. This value is a parameter used to filter the states to be explored by the approximation method.

Return

Type	Description	Default
Integer	The smallest possible transition cost.	0

Example (Default Logic)

public override double GetMinimumTransitionCost()
{
    return 0;
}

GetMultiplier

public override double GetMultiplier()

Definition

This parameter is used to filter the states to be explored by the approximation method. The higher the value, the more states will be explored, increasing computation time and potentially improving the objective function value.

Return

Type	Description	Default
Double	The value of the multiplier parameter.	2

Example (Default Logic)

public override double GetMultiplier() 
{
    return 2;
}

GetEstimatedValue

public override double GetEstimatedValue(State state)

Definition

Sets an estimate of the value function of a given state. This estimate is used to apply approximation method to reduce the number of states to explore.

Parameters

Type	Description
State	The state to compute the value function estimate.

Return

Type	Description	Default
Double	An estimate of the value function of the state.	Default Logic

Example (Default Logic)

public override double GetEstimatedValue(State state)
{
    double dualBound = BoundControl.Instance.GetDualBound(state);
    state.SetDualBound(dualBound);

    return state.BestValue + state.DualBound;
}

FilterGlobalStates

public override List<State> FilterGlobalStates(List<State> states, int maxTransitionCount, ObjectiveFunctionType objectiveFunctionType, double pruneTolerance, bool isApplyStateClustering)

Definition

Defines the global filtering logic and returns a list of states to explore.

Parameters

Type	Description
List<State>	The list of states before filtering.
Integer	The maximum number of states to explore after filtering.
ObjectiveFunctionType	The type of objective function in the problem. (Maximize, Minimize)
Double	The tolerance value that is applied when determining the state pruning condition.
Boolean	Whether to apply state clustering method.

Return

Type	Description	Default
List<State>	The list of states to explore after global filtering.	Default Logic

Example (Default Logic)

public override List<State> FilterGlobalStates(List<State> states, int maxTransitionCount, ObjectiveFunctionType objectiveFunctionType, double pruneTolerance, bool isApplyStateClustering)
{
    List<State> filtered = new List<State>();

    if (isApplyStateClustering)
    {
        Dictionary<int, List<State>> clusters = new Dictionary<int, List<State>>();
        foreach (State state in states)
        {
            if (clusters.TryGetValue(state.ClusterID, out List<State> list) == false)
            {
                clusters.Add(state.ClusterID, new List<State>() { state });
            }
            else 
            {
                list.Add(state);
            }
        }

        int clusterTransitionCount = this.GetClusterTransitionCount();
        foreach (KeyValuePair<int, List<State>> item in clusters)
        {
            List<State> list = item.Value.OrderBy(x => x.ClusterDistance).ToList();

            int maxCount = clusterTransitionCount;
            int count = 0;
            foreach (State st in list)
            {
                if (count > maxCount)
                    break;

                filtered.Add(st);

                count++;
            }
        }
    }
    else
    {
        foreach (State state in states)
        {
            if (state.IsFinal)
                continue;

            double estimatedValue = GetEstimatedValue(state);
            state.EstimationValue = estimatedValue;
        }

        if (objectiveFunctionType == ObjectiveFunctionType.Minimize)
            states = states.OrderBy(x => x.EstimationValue).ToList();
        else if (objectiveFunctionType == ObjectiveFunctionType.Maximize)
            states = states.OrderByDescending(x => x.EstimationValue).ToList();

        int count = 0;
        foreach (State state in states)
        {
            if (maxTransitionCount <= count)
                break;

            filtered.Add(state);
            count++;
        }
    }

    return filtered;
}

FilterLocalStates

public override List<State> FilterLocalStates(List<State> states, int maxTransitionCount)

Definition

Defines the local filtering logic and returns a list of states to explore.

Parameters

Type	Description
List<State>	The list of states before filtering.
Integer	The maximum number of states to explore after filtering.

Return

Type	Description	Default
List<State>	The list of states to explore after local filtering.	Default Logic

Example (Default Logic)

public override List<State> FilterLocalStates(List<State> states, int maxTransitionCount)
{
    states = states.OrderBy(x => x.PrevBestState.DualBound + (x.BestValue - x.PrevBestState.BestValue) + x.BestValue).ToList();

    List<State> filtered = new List<State>();

    int count = 0;
    foreach (State state in states)
    {
        if (maxTransitionCount <= count)
            break;

        filtered.Add(state);
        count++;
    }

    return filtered;
}

CanPruneByApproximation

public override bool CanPruneByApproximation(State state, ObjectiveFunctionType objFuncType, double minEstimationValue, double minTransitionCost, double multiplier, double pruneTolerance)

Definition

Sets whether a given state should be excluded from exploration when reducing the number of states to explore via approximation methods.

Parameters

Type	Description
State	The state to be evaluated.
ObjectiveFunctionType	The type of objective function in the problem. (Maximize, Minimize)
Double	The smallest of the value function estimates of the candidate states to explore.
Double	The smallest possible transition cost.
Double	The value of the multiplier parameter.
Double	The tolerance value that is applied when determining the state pruning condition.

Return

Type	Description	Default
Boolean	Whether to prune the state.	Default Logic

Example (Default Logic)

 public override bool CanPruneByApproximation(State state, ObjectiveFunctionType objFuncType, double minEstimationValue, double minTransitionCost, double multiplier, double pruneTolerance)
{
    if (state.IsFinal)
        return false;

    if (objFuncType == ObjectiveFunctionType.Minimize)
    {
        if (state.EstimationValue + pruneTolerance > minEstimationValue + (minTransitionCost * multiplier))
            return true;
        else
            return false;
    }
    else
    {
        if (state.EstimationValue + pruneTolerance < minEstimationValue + (minTransitionCost * multiplier))
            return true;
        else
            return false;
    }
}