org.jamesframework.core.subset

Class SubsetProblem<DataType extends IntegerIdentifiedData>

java.lang.Object

org.jamesframework.core.problems.GenericProblem<SubsetSolution,DataType>

org.jamesframework.core.subset.SubsetProblem<DataType>

Type Parameters:

DataType - underlying data type, should implement the interface IntegerIdentifiedData

All Implemented Interfaces:

Problem<SubsetSolution>

public class SubsetProblem<DataType extends IntegerIdentifiedData>
extends GenericProblem<SubsetSolution,DataType>

High-level subset problem consisting of data, an objective and possibly some constraints (see GenericProblem). All items in the data set are identified using a unique integer ID so that any subset selection problem comes down to selection of a subset of these IDs. The solution type is fixed to SubsetSolution and the data type can be set to any implementation of the IntegerIdentifiedData interface. When creating the problem, the minimum and maximum allowed subset size are specified. A default random solution generator is used, which generates random subsets within the imposed size limits, based on the IDs of the items as retrieved from the underlying data. An additional method is provided to generate subset solutions with an empty selection.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
SubsetProblem(DataType data, Objective<? super SubsetSolution,? super DataType> objective) Creates a subset problem without subset size limits.
SubsetProblem(DataType data, Objective<? super SubsetSolution,? super DataType> objective, int fixedSubsetSize) Creates a subset problem with fixed subset size.
SubsetProblem(DataType data, Objective<? super SubsetSolution,? super DataType> objective, int minSubsetSize, int maxSubsetSize) Creates a new subset problem with given data, objective and minimum/maximum subset size.
SubsetProblem(DataType data, Objective<? super SubsetSolution,? super DataType> objective, int minSubsetSize, int maxSubsetSize, boolean orderIDs) Creates a new subset problem with given data, objective and minimum/maximum subset size.
SubsetProblem(DataType data, Objective<? super SubsetSolution,? super DataType> objective, int minSubsetSize, int maxSubsetSize, Comparator<Integer> orderOfIDs) Creates a new subset problem with given data, objective and minimum/maximum subset size.

Method Summary

Modifier and Type	Method and Description
SubsetSolution	createEmptySubsetSolution() Creates an empty subset solution in which no IDs are selected.
int	getMaxSubsetSize() Get the maximum subset size.
int	getMinSubsetSize() Get the minimum subset size.
void	setData(DataType data) Set new data.
void	setMaxSubsetSize(int maxSubsetSize) Set the maximum subset size.
void	setMinSubsetSize(int minSubsetSize) Set the minimum subset size.
SubsetValidation	validate(Move<? super SubsetSolution> move, SubsetSolution curSolution, Validation curValidation) Validate a move to be applied to the current subset solution of a local search (delta validation).
SubsetValidation	validate(SubsetSolution solution) Validate a subset solution.

Methods inherited from class org.jamesframework.core.problems.GenericProblem

addMandatoryConstraint, addPenalizingConstraint, createRandomSolution, evaluate, evaluate, getData, getMandatoryConstraints, getObjective, getPenalizingConstraints, getRandomSolutionGenerator, getViolatedConstraints, isMinimizing, removeMandatoryConstraint, removePenalizingConstraint, setObjective, setRandomSolutionGenerator

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.problems.Problem

createRandomSolution

Constructor Detail

SubsetProblem

public SubsetProblem(DataType data,
                     Objective<? super SubsetSolution,? super DataType> objective,
                     int minSubsetSize,
                     int maxSubsetSize,
                     Comparator<Integer> orderOfIDs)

Creates a new subset problem with given data, objective and minimum/maximum subset size. Both objective and data are not allowed to be null, an exception will be thrown if they are. Any objective designed to evaluate subset solutions (or more general solutions) using the specified data type (or more general data) is accepted. The minimum and maximum subset size should be contained in [0,n] where n is the number of items in the given data from which a subset is to be selected. Also, the minimum size should be smaller than or equal to the maximum size.

The given comparator orderOfIDs is used to impose an ordering on the IDs in generated subset solutions. This argument may be null in which case no ordering is imposed.

Parameters:

data - underlying data, can not be null

objective - objective function, can not be null

minSubsetSize - minimum subset size (should be ≥ 0 and ≤ maximum subset size)

maxSubsetSize - maximum subset size (should be ≥ minimum subset size and ≤ number of items in underlying data)

orderOfIDs - the order that is imposed on the IDs in any generated subset solution, may be null in case no order is to be imposed

Throws:

NullPointerException - if objective or data is null

IllegalArgumentException - if an invalid minimum or maximum subset size is specified

SubsetProblem

public SubsetProblem(DataType data,
                     Objective<? super SubsetSolution,? super DataType> objective,
                     int minSubsetSize,
                     int maxSubsetSize,
                     boolean orderIDs)

Creates a new subset problem with given data, objective and minimum/maximum subset size. Both objective and data are not allowed to be null, an exception will be thrown if they are. Any objective designed to evaluate subset solutions (or more general solutions) using the specified data type (or more general data) is accepted. The minimum and maximum subset size should be contained in [0,n] where n is the number of items in the given data from which a subset is to be selected. Also, the minimum size should be smaller than or equal to the maximum size.

If orderIDs is true, subset solutions generated by this problem will order IDs in ascending order (according to the natural integer ordering).

Parameters:

data - underlying data, can not be null

objective - objective function, can not be null

minSubsetSize - minimum subset size (should be ≥ 0 and ≤ maximum subset size)

maxSubsetSize - maximum subset size (should be ≥ minimum subset size and ≤ number of items in underlying data)

orderIDs - indicates whether IDs are ordered (ascending) in generated subset solutions

Throws:

NullPointerException - if objective or data is null

IllegalArgumentException - if an invalid minimum or maximum subset size is specified

SubsetProblem

public SubsetProblem(DataType data,
                     Objective<? super SubsetSolution,? super DataType> objective,
                     int minSubsetSize,
                     int maxSubsetSize)

Creates a new subset problem with given data, objective and minimum/maximum subset size. Both objective and data are not allowed to be null, an exception will be thrown if they are. Any objective designed to evaluate subset solutions (or more general solutions) using the specified data type (or more general data) is accepted. The minimum and maximum subset size should be contained in [0,n] where n is the number of items in the given data from which a subset is to be selected. Also, the minimum size should be smaller than or equal to the maximum size. Generated subset solutions do not impose any order on the IDs.

Parameters:

data - underlying data, can not be null

objective - objective function, can not be null

minSubsetSize - minimum subset size (should be ≥ 0 and ≤ maximum subset size)

maxSubsetSize - maximum subset size (should be ≥ minimum subset size and ≤ number of items in underlying data)

Throws:

NullPointerException - if objective or data is null

IllegalArgumentException - if an invalid minimum or maximum subset size is specified

SubsetProblem

public SubsetProblem(DataType data,
                     Objective<? super SubsetSolution,? super DataType> objective,
                     int fixedSubsetSize)

Creates a subset problem with fixed subset size. Equivalent to calling

 SubsetProblem p = new SubsetProblem(data, objective, fixedSubsetSize, fixedSubsetSize);

The fixed subset size should be contained in [0,n] where n is the number of items in the given data from which a subset is to be selected. Generated subset solutions do not impose any order on the IDs.

Parameters:

data - underlying data, can not be null

objective - objective function, can not be null

fixedSubsetSize - fixed subset size

Throws:

NullPointerException - if objective or data is null

IllegalArgumentException - if an invalid fixed subset size is specified

SubsetProblem

public SubsetProblem(DataType data,
                     Objective<? super SubsetSolution,? super DataType> objective)

Creates a subset problem without subset size limits. Equivalent to calling

 SubsetProblem p = new SubsetProblem(data, objective, 0, data.getIDs().size());

Generated subset solutions do not impose any order on the IDs.

Parameters:

data - underlying data, can not be null

objective - objective function, can not be null

Throws:

NullPointerException - if objective or data is null

IllegalArgumentException - if an invalid fixed subset size is specified

Method Detail

setData

public void setData(DataType data)

Set new data.

Overrides:

setData in class GenericProblem<SubsetSolution,DataType extends IntegerIdentifiedData>

Parameters:

data - new data (can not be null)

Throws:

NullPointerException - if data is null

createEmptySubsetSolution

public SubsetSolution createEmptySubsetSolution()

Creates an empty subset solution in which no IDs are selected. The set of all IDs is obtained from the underlying data and passed to the created empty solution.

Returns:

empty subset solution with no selected IDs

validate

public SubsetValidation validate(SubsetSolution solution)

Validate a subset solution. The returned validation object separately indicates whether the solution passed general mandatory constraint validation and whether it has a valid size.

Specified by:

validate in interface Problem<SubsetSolution>

Overrides:

validate in class GenericProblem<SubsetSolution,DataType extends IntegerIdentifiedData>

Parameters:

solution - solution to validate

Returns:

subset validation

validate

public SubsetValidation validate(Move<? super SubsetSolution> move,
                                 SubsetSolution curSolution,
                                 Validation curValidation)

Validate a move to be applied to the current subset solution of a local search (delta validation). A subset problem can only perform delta validation for moves of type SubsetMove. If the received move has a different type an IncompatibleDeltaValidationException is thrown.

Specified by:

validate in interface Problem<SubsetSolution>

Overrides:

validate in class GenericProblem<SubsetSolution,DataType extends IntegerIdentifiedData>

Parameters:

move - subset move to be validated

curSolution - current solution

curValidation - current validation

Returns:

subset validation of modified subset solution

Throws:

IncompatibleDeltaValidationException - if the received move is not of type SubsetMove or if the delta validation of any mandatory constraint is not compatible with the received move type

getMinSubsetSize

public int getMinSubsetSize()

Get the minimum subset size.

Returns:

minimum subset size

setMinSubsetSize

public void setMinSubsetSize(int minSubsetSize)

Set the minimum subset size. Specified size should be ≥ 1 and ≤ the current maximum subset size.

Parameters:

minSubsetSize - new minimum subset size

Throws:

IllegalArgumentException - if an invalid minimum size is given

getMaxSubsetSize

public int getMaxSubsetSize()

Get the maximum subset size.

Returns:

maximum subset size

setMaxSubsetSize

public void setMaxSubsetSize(int maxSubsetSize)

Set the maximum subset size. Specified size should be ≥ the current minimum subset size and ≤ the number of items in the underlying data.

Parameters:

maxSubsetSize - new maximum subset size

Throws:

IllegalArgumentException - if an invalid maximum size is given