## Class MultiDeletionNeighbourhood

• All Implemented Interfaces:
Neighbourhood<SubsetSolution>

public class MultiDeletionNeighbourhood
extends SubsetNeighbourhood

A subset neighbourhood that generates moves which simultaneously remove up to $$k$$ items from 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 remove IDs from the selection. If desired, a set of fixed IDs can be provided which are not allowed to be removed. Also, a minimum size can be imposed so that it is guaranteed that the subset size will not drop below this minimum after application of a move generated by this neighbourhood.

Note that a very large amount of moves may be generated when the subset 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
MultiDeletionNeighbourhood()
Creates a multi deletion neighbourhood that may remove an unlimited number of IDs from the selection.
MultiDeletionNeighbourhood(int maxDeletions)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection.
MultiDeletionNeighbourhood(int maxDeletions, int minSubsetSize)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection, taking into account that the subset size may not drop below the given minimum.
MultiDeletionNeighbourhood(int maxDeletions, int minSubsetSize, Set<Integer> fixedIDs)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection, taking into account that the subset size may not drop below the given minimum and that the given set of fixed IDs are not allowed to be deselected.
• ### 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$$ deletions, where $$k$$ is the maximum number of deletions specified at construction.
int getMaxDeletions()
Get the maximum number of deletions performed by generated moves.
int getMinSubsetSize()
Get the minimum subset size specified at construction.
SubsetMove getRandomMove(SubsetSolution solution, Random rnd)
Generates a move for the given subset solution that deselects a random subset of currently selected IDs.
• ### 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

• #### MultiDeletionNeighbourhood

public MultiDeletionNeighbourhood()
Creates a multi deletion neighbourhood that may remove an unlimited number of IDs from the selection. The actual number of performed removals is then only limited by the number of selected items, as it is impossible to remove more items.
• #### MultiDeletionNeighbourhood

public MultiDeletionNeighbourhood(int maxDeletions)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection. If maxDeletions is 1, this neighbourhood generates exactly the same moves as the SingleDeletionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxDeletions - maximum number of removed IDs (> 0)
Throws:
IllegalArgumentException - if maxDeletions is not strictly positive
• #### MultiDeletionNeighbourhood

public MultiDeletionNeighbourhood(int maxDeletions,
int minSubsetSize)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection, taking into account that the subset size may not drop below the given minimum. If maxDeletions is 1, this neighbourhood generates exactly the same moves as the SingleDeletionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxDeletions - maximum number of removed IDs (> 0)
minSubsetSize - minimum subset size (≥ 0)
Throws:
IllegalArgumentException - if maxDeletions is not strictly positive or minSubsetSize is negative
• #### MultiDeletionNeighbourhood

public MultiDeletionNeighbourhood(int maxDeletions,
int minSubsetSize,
Set<Integer> fixedIDs)
Creates a multi deletion neighbourhood that may simultaneously remove up to the specified number of IDs from the selection, taking into account that the subset size may not drop below the given minimum and that the given set of fixed IDs are not allowed to be deselected. If maxDeletions is 1, this neighbourhood generates exactly the same moves as the SingleDeletionNeighbourhood so in such case it is advised to use the latter neighbourhood which has been optimized for this specific scenario.
Parameters:
maxDeletions - maximum number of removed IDs (> 0)
minSubsetSize - minimum subset size (≥ 0)
fixedIDs - set of fixed IDs which are not allowed to be removed from the selection
Throws:
IllegalArgumentException - if maxDeletions is not strictly positive or minSubsetSize is negative
• ### Method Detail

• #### getMaxDeletions

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

public int getMinSubsetSize()
Get the minimum subset size specified at construction. If no minimum size has been set this method returns 0.
Returns:
minimum subset size
• #### getRandomMove

public SubsetMove getRandomMove(SubsetSolution solution,
Random rnd)

Generates a move for the given subset solution that deselects a random subset of currently selected IDs. Possible fixed IDs are not considered to be deselected. The maximum number of deletions $$k$$ and minimum allowed subset size are respected. If no items can be removed, null is returned.

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

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

public List<SubsetMove> getAllMoves(SubsetSolution solution)

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

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

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