Package org.tweetyproject.math.opt.problem

Class CombinatoricsProblem

java.lang.Object

java.util.AbstractCollection<OptProbElement>

java.util.AbstractSet<OptProbElement>

java.util.HashSet<OptProbElement>

org.tweetyproject.math.opt.problem.GeneralConstraintSatisfactionProblem

org.tweetyproject.math.opt.problem.CombinatoricsProblem

All Implemented Interfaces:

Serializable, Cloneable, Iterable<OptProbElement>, Collection<OptProbElement>, Set<OptProbElement>

Direct Known Subclasses:

KnapSack, TravelingSalesman

public abstract class CombinatoricsProblem
extends GeneralConstraintSatisfactionProblem

This class implements a combinatorial optimization problem

Author:

Sebastian Franke

See Also:

• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
List<ElementOfCombinatoricsProb>	elements	elements
static final int	MAXIMIZE	Static constant for the type "maximization"
static final int	MINIMIZE	Static constant for the type "minimization"

Constructor Summary

Constructors

Constructor	Description
CombinatoricsProblem(List<ElementOfCombinatoricsProb> elements, int[][] graphRepresantation)	constructor

Method Summary

Modifier and Type	Method	Description
ArrayList<ElementOfCombinatoricsProb>	createDifference(ArrayList<ElementOfCombinatoricsProb> c)	Return the differnece of the lists
abstract ArrayList<ElementOfCombinatoricsProb>	createRandomNewSolution(ArrayList<ElementOfCombinatoricsProb> currSol)	create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solution
abstract double	evaluate(ArrayList<ElementOfCombinatoricsProb> sol)	evaluates the solution
ArrayList<ArrayList<ElementOfCombinatoricsProb>>	formNeighborhood(ArrayList<ElementOfCombinatoricsProb> currSol, int minIterations, int maxIteration, double threshold)	Return neighborhood
int[][]	getGraphrepresentation()	Return Graph representation
abstract Double	getHeuristicValue(ElementOfCombinatoricsProb solutionComponent, Integer getCurrentIndex, ElementOfCombinatoricsProb initialReference, ElementOfCombinatoricsProb[] sol)	for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution sol
abstract double[][]	getRepresentation()	for Ant optimization: represent the problem as an adjacence matrix
abstract boolean	isValid(ArrayList<ElementOfCombinatoricsProb> sol)	checks if a given solution is valid under all constraints
abstract double	sumOfWeights(ArrayList<ElementOfCombinatoricsProb> sol)	Return if the solution sol is valid under the constraints of the problem

Methods inherited from class java.util.HashSet

add, clear, clone, contains, isEmpty, iterator, newHashSet, remove, size, spliterator, toArray, toArray

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toString

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, removeAll, retainAll

Field Details

MINIMIZE

public static final int MINIMIZE

Static constant for the type "minimization"

See Also:

• Constant Field Values

MAXIMIZE

public static final int MAXIMIZE

Static constant for the type "maximization"

See Also:

• Constant Field Values

elements

public List<ElementOfCombinatoricsProb> elements

elements

Constructor Details

CombinatoricsProblem

public CombinatoricsProblem(List<ElementOfCombinatoricsProb> elements,
 int[][] graphRepresantation)

constructor

Parameters:

elements - elements

graphRepresantation - problem

Method Details

createDifference

public ArrayList<ElementOfCombinatoricsProb> createDifference(ArrayList<ElementOfCombinatoricsProb> c)

Return the differnece of the lists

Parameters:

c - the List to be subtracted from "this" List

Returns:

the differnece of the lists

sumOfWeights

public abstract double sumOfWeights(ArrayList<ElementOfCombinatoricsProb> sol)

Return if the solution sol is valid under the constraints of the problem

Parameters:

sol - is the solution to be viewd

Returns:

if the solution sol is valid under the constraints of the problem

formNeighborhood

public ArrayList<ArrayList<ElementOfCombinatoricsProb>> formNeighborhood(ArrayList<ElementOfCombinatoricsProb> currSol,
 int minIterations,
 int maxIteration,
 double threshold)

Return neighborhood

Parameters:

currSol - current solution

minIterations - minimum iterations

maxIteration - maximum iterations

threshold - threshold

Returns:

neighborhood

getGraphrepresentation

public int[][] getGraphrepresentation()

Return Graph representation

Returns:

Graph representation

createRandomNewSolution

public abstract ArrayList<ElementOfCombinatoricsProb> createRandomNewSolution(ArrayList<ElementOfCombinatoricsProb> currSol)

create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solution

Parameters:

currSol - the current solution

Returns:

the solution

evaluate

public abstract double evaluate(ArrayList<ElementOfCombinatoricsProb> sol)

evaluates the solution

Parameters:

sol - some solution

Returns:

the target function for sol

isValid

public abstract boolean isValid(ArrayList<ElementOfCombinatoricsProb> sol)

checks if a given solution is valid under all constraints

Parameters:

sol - some solution

Returns:

true iff the solution is valid

getHeuristicValue

public abstract Double getHeuristicValue(ElementOfCombinatoricsProb solutionComponent,
 Integer getCurrentIndex,
 ElementOfCombinatoricsProb initialReference,
 ElementOfCombinatoricsProb[] sol)

for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution sol

Parameters:

solutionComponent - : Element to be checked *

getCurrentIndex - : the length of the solution

initialReference - : default starting point for the solution (the first Element in the solution)

sol - : array representation of a solution (needed for Ant optimization)

Returns:

the heuristic value

getRepresentation

public abstract double[][] getRepresentation()

for Ant optimization: represent the problem as an adjacence matrix

Returns:

representation