org.jamesframework.core.problems

Class GenericProblem<SolutionType extends Solution,DataType>

java.lang.Object

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

Type Parameters:

SolutionType - type of solutions to the problem, required to extend Solution

DataType - type of underlying data

All Implemented Interfaces:

Problem<SolutionType>

Direct Known Subclasses:

SubsetProblem

public class GenericProblem<SolutionType extends Solution,DataType>
extends Object
implements Problem<SolutionType>

A generic problem is fully based on delegation of its responsabilities, by separating data from the objective, constraints (if any) and random solution generation. The problem contains data of a specific type (parameter DataType) and solutions are evaluated and validated based on a combination of an objective and constraints, which use the underlying data. Two types of constraints can be specified:

• Mandatory constraints: a solution is valid only if it satisfies all mandatory constraints. If not, it is discarded regardless of its evaluation. It is guaranteed that the best solution found by a search will always satisfy all mandatory constraints. In a neighbourhood search, only those neighbours of the current solution that satisfy all mandatory constraints are considered.

• Penalizing constraints: if a solution does not pass validation by a penalizing constraint, a penalty is assigned to its evaluation. The solution is not discarded. Penalties are usually chosen to reflect the severeness of the violation. Solutions closer to satisfaction are then favoured over solutions that violate the constraints more severely. In case of maximization, penalties are subtracted from the evaluation, while they are added to it in case of minimization. Depending on the interaction between the evaluation and penalties, the best found solution might not satisfy all penalizing constraints (which may or may not be desired).

The problem uses an external, customizable random solution generator to create random instances of the solution type.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
GenericProblem(DataType data, Objective<? super SolutionType,? super DataType> objective, RandomSolutionGenerator<? extends SolutionType,? super DataType> randomSolutionGenerator) Creates a new generic problem with given data, objective and random solution generator.

Method Summary

Modifier and Type	Method and Description
void	addMandatoryConstraint(Constraint<? super SolutionType,? super DataType> constraint) Add a mandatory constraint to the problem.
void	addPenalizingConstraint(PenalizingConstraint<? super SolutionType,? super DataType> constraint) Add a penalizing constraint to the problem.
SolutionType	createRandomSolution(Random rnd) Delegates to the contained random solution generator.
Evaluation	evaluate(Move<? super SolutionType> move, SolutionType curSolution, Evaluation curEvaluation) Evaluate a move (delta evaluation) by taking into account both the evaluation of the modified solution and the penalizing constraints (if any).
Evaluation	evaluate(SolutionType solution) Evaluates a solution by taking into account both the evaluation calculated by the objective function and the penalizing constraints (if any).
DataType	getData() Get the underlying data.
List<Constraint<? super SolutionType,? super DataType>>	getMandatoryConstraints() Get mandatory constraints (unmodifiable view).
Objective<? super SolutionType,? super DataType>	getObjective() Get the objective function.
List<PenalizingConstraint<? super SolutionType,? super DataType>>	getPenalizingConstraints() Get penalizing constraints (unmodifiable view).
RandomSolutionGenerator<? extends SolutionType,? super DataType>	getRandomSolutionGenerator() Get the random solution generator.
Collection<Constraint<? super SolutionType,? super DataType>>	getViolatedConstraints(SolutionType solution) Returns a collection of all violated constraints (both mandatory and penalizing).
boolean	isMinimizing() Indicates whether the underlying objective is minimizing.
boolean	removeMandatoryConstraint(Constraint<? super SolutionType,? super DataType> constraint) Remove a mandatory constraint.
boolean	removePenalizingConstraint(PenalizingConstraint<? super SolutionType,? super DataType> constraint) Remove a penalizing constraint.
void	setData(DataType data) Set new underlying data.
void	setObjective(Objective<? super SolutionType,? super DataType> objective) Set the objective function.
void	setRandomSolutionGenerator(RandomSolutionGenerator<? extends SolutionType,? super DataType> randomSolutionGenerator) Set random solution generator.
Validation	validate(Move<? super SolutionType> move, SolutionType curSolution, Validation curValidation) Validate a move by checking all mandatory constraints (delta validation).
Validation	validate(SolutionType solution) Validate a solution by checking all mandatory constraints.

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

GenericProblem

public GenericProblem(DataType data,
                      Objective<? super SolutionType,? super DataType> objective,
                      RandomSolutionGenerator<? extends SolutionType,? super DataType> randomSolutionGenerator)

Creates a new generic problem with given data, objective and random solution generator. Any objective designed for the solution and data types of the problem, or supertypes thereof, is accepted. The random solution generator may produce subtypes of the problem's solution type, requiring any supertype of the problem's data type.

The objective and random solution generator can not be null.

Parameters:

data - underlying data

objective - objective function

randomSolutionGenerator - random solution generator

Throws:

NullPointerException - if objective or randomSolutionGenerator are null

Method Detail

getObjective

public Objective<? super SolutionType,? super DataType> getObjective()

Get the objective function.

Returns:

objective function

setObjective

public void setObjective(Objective<? super SolutionType,? super DataType> objective)

Set the objective function. Any objective designed for the solution and data types of the problem, or more general types, is accepted. The objective can not be null.

Parameters:

objective - objective function

Throws:

NullPointerException - if objective is null

getRandomSolutionGenerator

public RandomSolutionGenerator<? extends SolutionType,? super DataType> getRandomSolutionGenerator()

Get the random solution generator.

Returns:

random solution generator

setRandomSolutionGenerator

public void setRandomSolutionGenerator(RandomSolutionGenerator<? extends SolutionType,? super DataType> randomSolutionGenerator)

Set random solution generator. It is allowed for the generator to produce subtypes of the problem's solution type, requiring any supertype of the problem's data type. The generator can not be null.

Parameters:

randomSolutionGenerator - random solution generator

Throws:

NullPointerException - if randomSolutionGenerator is null

getData

public DataType getData()

Get the underlying data.

Returns:

underlying data

setData

public void setData(DataType data)

Set new underlying data.

Parameters:

data - new underlying data

addMandatoryConstraint

public void addMandatoryConstraint(Constraint<? super SolutionType,? super DataType> constraint)

Add a mandatory constraint to the problem. Only those solutions that satisfy all mandatory constraints will pass validation (see validate(Solution)). Other solutions are discarded regardless of their evaluation.

Only constraints designed for the solution and data type of the problem (or more general) are accepted. Constraints should not be added while a search is solving this problem; doing so may lead to exceptions and/or undefined search behaviour.

Parameters:

constraint - mandatory constraint to add

removeMandatoryConstraint

public boolean removeMandatoryConstraint(Constraint<? super SolutionType,? super DataType> constraint)

Remove a mandatory constraint. Returns true if the constraint has been successfully removed.

Constraints should not be removed while a search is solving this problem; doing so may lead to exceptions and/or undefined search behaviour.

Parameters:

constraint - mandatory constraint to be removed

Returns:

true if the constraint is successfully removed

getMandatoryConstraints

public List<Constraint<? super SolutionType,? super DataType>> getMandatoryConstraints()

Get mandatory constraints (unmodifiable view).

Returns:

list of mandatory constraints

addPenalizingConstraint

public void addPenalizingConstraint(PenalizingConstraint<? super SolutionType,? super DataType> constraint)

Add a penalizing constraint to the problem. For a solution that violates a penalizing constraint, a penalty will be assigned to the objective score. Only penalizing constraints designed for the solution and data type of the problem (or more general) are accepted.

Constraints should not be added while a search is solving this problem; doing so may lead to exceptions and/or undefined search behaviour.

Parameters:

constraint - penalizing constraint to add

removePenalizingConstraint

public boolean removePenalizingConstraint(PenalizingConstraint<? super SolutionType,? super DataType> constraint)

Remove a penalizing constraint. Returns true if the constraint has been successfully removed.

Constraints should not be removed while a search is solving this problem; doing so may lead to exceptions and/or undefined search behaviour.

Parameters:

constraint - penalizing constraint to be removed

Returns:

true if the constraint is successfully removed

getPenalizingConstraints

public List<PenalizingConstraint<? super SolutionType,? super DataType>> getPenalizingConstraints()

Get penalizing constraints (unmodifiable view).

Returns:

list of penalizing constraints

validate

public Validation validate(SolutionType solution)

Validate a solution by checking all mandatory constraints. The solution will only pass validation if all mandatory constraints are satisfied.

In case there are no mandatory constraints, this method always returns SimpleValidation.PASSED. If a single mandatory constraint has been specified, the corresponding validation is returned. In case of two or more constraints, an aggregated validation is constructed that only passes if all constraints are satisfied. Short-circuiting is applied: as soon as one violated constraint is found, the remaining constraints are not checked.

Specified by:

validate in interface Problem<SolutionType extends Solution>

Parameters:

solution - solution to validate

Returns:

aggregated validation

validate

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

Validate a move by checking all mandatory constraints (delta validation). The move will only pass validation if all mandatory constraints are satisfied.

In case there are no mandatory constraints, this method always returns SimpleValidation.PASSED. If a single mandatory constraint has been specified, the corresponding delta validation is returned. In case of two or more constraints, an aggregated validation is constructed that only passes if all constraints are satisfied. Short-circuiting is applied: as soon as one violated constraint is found, the remaining constraints are not checked.

Specified by:

validate in interface Problem<SolutionType extends Solution>

Parameters:

move - move to validate

curSolution - current solution of a local search

curValidation - validation of current solution

Returns:

aggregated delta validation

Throws:

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

getViolatedConstraints

public Collection<Constraint<? super SolutionType,? super DataType>> getViolatedConstraints(SolutionType solution)

Returns a collection of all violated constraints (both mandatory and penalizing).

Parameters:

solution - solution for which all violated constraints are determined

Returns:

collection of all violated constraints (mandatory and penalizing); possibly empty

evaluate

public Evaluation evaluate(SolutionType solution)

Evaluates a solution by taking into account both the evaluation calculated by the objective function and the penalizing constraints (if any). Penalties are assigned for any violated penalizing constraint, which are subtracted from the evaluation in case of maximization, and added to it in case of minimization.

If there are no penalizing constraints, this method returns the evaluation object obtained from applying the objective function to the given solution. If one or more penalizing constraints have been specified, a penalized evaluation is constructed taking into account both the main objective function evaluation and assigned penalties.

Specified by:

evaluate in interface Problem<SolutionType extends Solution>

Parameters:

solution - solution to be evaluated

Returns:

aggregated evaluation taking into account both the objective function and penalizing constraints

evaluate

public Evaluation evaluate(Move<? super SolutionType> move,
                           SolutionType curSolution,
                           Evaluation curEvaluation)

Evaluate a move (delta evaluation) by taking into account both the evaluation of the modified solution and the penalizing constraints (if any). Penalties are assigned for any violated penalizing constraint, which are subtracted from the evaluation in case of maximization, and added to it in case of minimization.

If there are no penalizing constraints, this method returns the delta evaluation obtained from the objective function. If one or more penalizing constraints have been specified, a penalized delta evaluation is constructed taking into account both the main objective function evaluation and assigned penalties.

Specified by:

evaluate in interface Problem<SolutionType extends Solution>

Parameters:

move - move to evaluate

curSolution - current solution

curEvaluation - current evaluation

Returns:

aggregated evaluation of modified solution, taking into account both the objective function and penalizing constraints

Throws:

IncompatibleDeltaEvaluationException - if the provided delta evaluation of the objective is not compatible with the received move type

IncompatibleDeltaValidationException - if the provided delta validation of any penalizing constraint is not compatible with the received move type

createRandomSolution

public SolutionType createRandomSolution(Random rnd)

Delegates to the contained random solution generator.

Specified by:

createRandomSolution in interface Problem<SolutionType extends Solution>

Parameters:

rnd - source of randomness

Returns:

random solution

isMinimizing

public boolean isMinimizing()

Indicates whether the underlying objective is minimizing.

Specified by:

isMinimizing in interface Problem<SolutionType extends Solution>

Returns:

true if the objective is minimizing