• All Implemented Interfaces:
Neighbourhood<SubsetSolution>

public class MultiAdditionNeighbourhood
extends SubsetNeighbourhood

A subset neighbourhood that generates moves which simultaneously add up to $$k$$ items to the selection, where $$k$$ is specified at construction (or unlimited). Generated moves are of type GeneralSubsetMove, which is a subtype of SubsetMove, and always only add IDs to the selection. If desired, a set of fixed IDs can be provided which are not allowed to be added. Also, a size limit can be imposed so that it is guaranteed that the subset solution will not exceed this size after application of a move generated by this neighbourhood.

Note that a very large amount of moves may be generated when the dataset size increases. Therefore, this advanced neighbourhood should be used with care, especially in combination with searches that inspect all moves in every step. Furthermore, searches that inspect random moves may have few chances to find an improvement in case of a huge amount of possible neighbours.

This neighbourhood is thread-safe: it can be safely used to concurrently generate moves in different searches running in separate threads.

Author:
Herman De Beukelaer
• ### Constructor Summary

Constructors
Constructor and Description
MultiAdditionNeighbourhood()
Creates a multi addition neighbourhood that may add an unlimited number of IDs to the selection.
MultiAdditionNeighbourhood(int maxAdditions)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection.
MultiAdditionNeighbourhood(int maxAdditions, int maxSubsetSize)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection, taking into account that the given maximum subset size can not be exceeded.
MultiAdditionNeighbourhood(int maxAdditions, int maxSubsetSize, Set<Integer> fixedIDs)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection, taking into account that the given maximum subset size can not be exceeded and that the given set of fixed IDs are not allowed to be selected.
• ### Method Summary

All Methods
Modifier and Type Method and Description
List<SubsetMove> getAllMoves(SubsetSolution solution)
Generates the list of all possible moves that perform 1 up to $$k$$ additions, where $$k$$ is the maximum number of additions specified at construction.
int getMaxAdditions()
Get the maximum number of additions performed by generated moves.
int getMaxSubsetSize()
Get the maximum subset size specified at construction.
SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
Generates a move for the given subset solution that adds a random subset of currently unselected IDs to the selection.
• ### Methods inherited from class org.jamesframework.core.subset.neigh.SubsetNeighbourhood

getAddCandidates, getRemoveCandidates
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Methods inherited from interface org.jamesframework.core.search.neigh.Neighbourhood

getRandomMove
• ### Constructor Detail

public MultiAdditionNeighbourhood()
Creates a multi addition neighbourhood that may add an unlimited number of IDs to the selection. The actual number of performed additions is then only limited by the number of unselected items, as it is impossible to add more items.

public MultiAdditionNeighbourhood(int maxAdditions)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection. If maxAdditions is 1, this neighbourhood generates exactly the same moves as the SingleAdditionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxAdditions - maximum number of added IDs (> 0)
Throws:
IllegalArgumentException - if maxAdditions is not strictly positive

public MultiAdditionNeighbourhood(int maxAdditions,
int maxSubsetSize)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection, taking into account that the given maximum subset size can not be exceeded. If maxAdditions is 1, this neighbourhood generates exactly the same moves as the SingleAdditionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxAdditions - maximum number of added IDs (> 0)
maxSubsetSize - maximum subset size (> 0)
Throws:
IllegalArgumentException - if maxAdditions or maxSubsetSize are not strictly positive

public MultiAdditionNeighbourhood(int maxAdditions,
int maxSubsetSize,
Set<Integer> fixedIDs)
Creates a multi addition neighbourhood that may simultaneously add up to the specified number of IDs to the selection, taking into account that the given maximum subset size can not be exceeded and that the given set of fixed IDs are not allowed to be selected. If maxAdditions is 1, this neighbourhood generates exactly the same moves as the SingleAdditionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxAdditions - maximum number of added IDs (> 0)
maxSubsetSize - maximum subset size (> 0)
fixedIDs - set of fixed IDs which are not allowed to be added to the selection
Throws:
IllegalArgumentException - if maxAdditions or maxSubsetSize are not strictly positive
• ### Method Detail

public int getMaxAdditions()
Get the maximum number of additions performed by generated moves. If no limit has been set this method returns Integer.MAX_VALUE.
Returns:
• #### getMaxSubsetSize

public int getMaxSubsetSize()
Get the maximum subset size specified at construction. If no maximum size has been set this method returns Integer.MAX_VALUE.
Returns:
maximum subset size
• #### getRandomMove

public SubsetMove getRandomMove(SubsetSolution solution,
Random rnd)

Generates a move for the given subset solution that adds a random subset of currently unselected IDs to the selection. Possible fixed IDs are not considered to be selected. The maximum number of additions $$k$$ and maximum allowed subset size are respected. If no items can be added, null is returned.

Note that first, a random number of additions is picked (uniformly distributed) from the valid range and then, a random subset of this size is sampled from the currently unselected IDs, to be added (again, all possible subsets are uniformly distributed, within the fixed size). Because the amount of possible moves increases with the number of performed additions, the probability of generating each specific move thus decreases with the number of additions. In other words, randomly generated moves are not uniformly distributed across different numbers of performed additions, but each specific move performing fewer additions is more likely to be selected than each specific move performing more additions.

Parameters:
solution - solution for which a random multi addition move is generated
rnd - source of randomness used to generate random move
Returns:
random multi addition move, null if no items can be added
• #### getAllMoves

public List<SubsetMove> getAllMoves(SubsetSolution solution)

Generates the list of all possible moves that perform 1 up to $$k$$ additions, where $$k$$ is the maximum number of additions specified at construction. Possible fixed IDs are not considered to be added and the maximum allowed subset size is respected.

May return an empty list if no moves can be generated.

Parameters:
solution - solution for which all possible multi addition moves are generated
Returns:
list of all multi addition moves, may be empty