Skip navigation links
org.jamesframework.core.subset.algo

## Class 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

All Methods
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>
Skip navigation links

Copyright © 2016. All rights reserved.