org.jamesframework.core.subset.algo

Class LRSubsetSearch

java.lang.Object

org.jamesframework.core.search.Search<SolutionType>

org.jamesframework.core.search.LocalSearch<SubsetSolution>

org.jamesframework.core.subset.algo.LRSubsetSearch

All Implemented Interfaces:

Runnable

public class LRSubsetSearch
extends LocalSearch<SubsetSolution>

LR subset search is a greedy local search heuristic for subset selection. Its specific execution depends on the value of two parameters \(L \ge 0\) and \(R \ge 0\), \(L \ne R\). If \(L \gt R\), the search first performs the best \(L\) additions followed by the best \(R\) removals of a single item, in every step. Else, if \(R \gt L\), every step consists of performing the \(R\) best removals followed by the \(L\) best additions of a single item. After every step, the subset size has changed with a value of \(\Delta = |L-R|\).

The search only considers additions and deletions that yield valid solutions without checking the current subset size as this size is actively brought into the valid range during search. By default, in case of an increasing subset size, the search starts with an empty subset, and in case of a decreasing subset size all items are initially selected. Alternatively, a custom initial solution can be set by calling LocalSearch.setCurrentSolution(Solution) before starting the search.

The search terminates as soon as the entire valid subset size range has been explored or when there are no valid additions/removals.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
LRSubsetSearch(String name, SubsetProblem<?> problem, int l, int r) Create an LR subset search, given the subset problem to solve, a value for \(L \ge 0\) and \(R \ge 0\), \(L \ne R\), and a custom search name.
LRSubsetSearch(SubsetProblem<?> problem, int l, int r) Create an LR subset search, given the subset problem to solve and a value for \(L \ge 0\) and \(R \ge 0\), \(L \ne R\).

Method Summary

Modifier and Type	Method and Description
int	getL() Get \(L\): the number of additions performed in every search step.
SubsetProblem<?>	getProblem() Returns the subset problem that is being solved.
int	getR() Get \(R\): the number of deletions performed in every search step.
void	init() When the search is initialized, and no custom initial solution has been set, an empty or full subset solution is created depending on whether \(L \gt R\) or \(R \gt L\), respectively.
protected void	searchStep() In every search step, the \(L\) best additions and \(R\) best deletions of a single item are performed.

Methods inherited from class org.jamesframework.core.search.LocalSearch

generateRandomInitialSolution, getCurrentSolution, getCurrentSolutionEvaluation, getCurrentSolutionValidation, setCurrentSolution, setCurrentSolution, updateCurrentAndBestSolution, updateCurrentAndBestSolution, updateCurrentSolution, updateCurrentSolution

Methods inherited from class org.jamesframework.core.search.Search

addSearchListener, addStopCriterion, assertIdle, clearSearchListeners, clearStopCriteria, computeDelta, dispose, getBestSolution, getBestSolutionEvaluation, getBestSolutionValidation, getID, getMinDelta, getName, getRandom, getRuntime, getSearchListeners, getStatus, getStatusLock, getSteps, getStepsWithoutImprovement, getTimeWithoutImprovement, removeSearchListener, removeStopCriterion, run, searchDisposed, searchStarted, searchStopped, setRandom, setStopCriterionCheckPeriod, start, stop, toString, updateBestSolution, updateBestSolution

Methods inherited from class java.lang.Object

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

Constructor Detail

LRSubsetSearch

public LRSubsetSearch(SubsetProblem<?> problem,
                      int l,
                      int r)

Create an LR subset search, given the subset problem to solve and a value for \(L \ge 0\) and \(R \ge 0\), \(L \ne R\). Note that problem can not be null and that both l and r should be positive and distinct. The search name is set to the default name "LRSubsetSearch".

Parameters:

problem - subset problem to solve

l - number of additions per search step

r - number of deletions per search step

Throws:

NullPointerException - if problem is null

IllegalArgumentException - if l or r are negative or equal

LRSubsetSearch

public LRSubsetSearch(String name,
                      SubsetProblem<?> problem,
                      int l,
                      int r)

Create an LR subset search, given the subset problem to solve, a value for \(L \ge 0\) and \(R \ge 0\), \(L \ne R\), and a custom search name. Note that problem can not be null and that both l and r should be positive and distinct. The search name can be null in which case it is set to the default name "LRSubsetSearch".

Parameters:

name - custom search name

problem - subset problem to solve

l - number of additions per search step

r - number of deletions per search step

Throws:

NullPointerException - if problem is null

IllegalArgumentException - if l or r are negative or equal

Method Detail

getL

public int getL()

Get \(L\): the number of additions performed in every search step.

Returns:

number of additions per step

getR

public int getR()

Get \(R\): the number of deletions performed in every search step.

Returns:

number of deletions per step

getProblem

public SubsetProblem<?> getProblem()

Returns the subset problem that is being solved.

Overrides:

getProblem in class Search<SubsetSolution>

Returns:

subset problem being solved

init

public void init()

When the search is initialized, and no custom initial solution has been set, an empty or full subset solution is created depending on whether \(L \gt R\) or \(R \gt L\), respectively.

Overrides:

init in class LocalSearch<SubsetSolution>

searchStep

protected void searchStep()

In every search step, the \(L\) best additions and \(R\) best deletions of a single item are performed. If \(L \gt R\), additions are performed first, else, deletions are performed first.

Specified by:

searchStep in class Search<SubsetSolution>