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

All Methods
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

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

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