Package org.ddolib.ddo.core.frontier

Class SimpleFrontier<T>

java.lang.Object

org.ddolib.ddo.core.frontier.SimpleFrontier<T>

Type Parameters:

T - the type of state in the subproblems

All Implemented Interfaces:

Frontier<T>

public final class SimpleFrontier<T>
extends Object
implements Frontier<T>

A simple implementation of a Frontier for a solver, based on a plain priority queue.

The SimpleFrontier maintains a collection of SubProblem instances, which are pushed and popped by the solver according to their priority determined by a StateRanking. This frontier supports cutset-based compilation strategies.

Constructor Summary

Constructors

Constructor	Description
SimpleFrontier(StateRanking<T> ranking, CutSetType cutSetType)	Constructs a new SimpleFrontier.

Method Summary

Modifier and Type	Method	Description
double	bestInFrontier()	Returns the best (lowest) lower bound among the subproblems in the frontier.
void	clear()	Clears all subproblems from the frontier.
CutSetType	cutSetType()	Returns the type of cutset used in the frontier.
SubProblem<T>	pop()	Removes and returns the most promising subproblem from the frontier.
void	push(SubProblem<T> sub)	Adds a subproblem to the frontier.
int	size()	Returns the number of subproblems currently in the frontier.
String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.ddolib.ddo.core.frontier.Frontier

isEmpty

Constructor Details

SimpleFrontier

public SimpleFrontier(StateRanking<T> ranking,
 CutSetType cutSetType)

Constructs a new SimpleFrontier.

Parameters:

ranking - the ordering used to determine which subproblem is most promising and should be explored first

cutSetType - the type of cutset to use: CutSetType.LastExactLayer or CutSetType.Frontier

Method Details

push

public void push(SubProblem<T> sub)

Adds a subproblem to the frontier.

Specified by:

push in interface Frontier<T>

Parameters:

sub - the subproblem to add

pop

public SubProblem<T> pop()

Removes and returns the most promising subproblem from the frontier.

Specified by:

pop in interface Frontier<T>

Returns:

the subproblem with highest priority, or null if the frontier is empty

clear

public void clear()

Clears all subproblems from the frontier.

Specified by:

clear in interface Frontier<T>

size

public int size()

Returns the number of subproblems currently in the frontier.

Specified by:

size in interface Frontier<T>

Returns:

the size of the frontier

cutSetType

public CutSetType cutSetType()

Returns the type of cutset used in the frontier.

Specified by:

cutSetType in interface Frontier<T>

Returns:

the cutset type

toString

public String toString()

Overrides:

toString in class Object

bestInFrontier

public double bestInFrontier()

Returns the best (lowest) lower bound among the subproblems in the frontier.

Specified by:

bestInFrontier in interface Frontier<T>

Returns:

the lower bound of the most promising subproblem