Package org.tweetyproject.math.opt.problem

Class CombinatoricsProblem

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<E>

java.util.HashSet<OptProbElement>

org.tweetyproject.math.opt.problem.GeneralConstraintSatisfactionProblem

org.tweetyproject.math.opt.problem.CombinatoricsProblem

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<OptProbElement>, java.util.Collection<OptProbElement>, java.util.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
java.util.List<ElementOfCombinatoricsProb>	elements
static int	MAXIMIZE	Static constant for the type "maximization"
static int	MINIMIZE	Static constant for the type "minimization"

Constructor Summary

Constructors

Constructor	Description
CombinatoricsProblem(java.util.List<ElementOfCombinatoricsProb> elements, int[][] graphRepresantation)

Method Summary

Modifier and Type	Method	Description
java.util.ArrayList<ElementOfCombinatoricsProb>	createDifference(java.util.ArrayList<ElementOfCombinatoricsProb> c)
abstract java.util.ArrayList<ElementOfCombinatoricsProb>	createRandomNewSolution(java.util.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(java.util.ArrayList<ElementOfCombinatoricsProb> sol)	evaluates the solution
java.util.ArrayList<java.util.ArrayList<ElementOfCombinatoricsProb>>	formNeighborhood(java.util.ArrayList<ElementOfCombinatoricsProb> currSol, int minIterations, int maxIteration, double threshold)
int[][]	getGraphrepresentation()
abstract java.lang.Double	getHeuristicValue(ElementOfCombinatoricsProb solutionComponent, java.lang.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(java.util.ArrayList<ElementOfCombinatoricsProb> sol)	checks if a given solution is valid under all constraints
abstract double	sumOfWeights(java.util.ArrayList<ElementOfCombinatoricsProb> sol)

Methods inherited from class java.util.HashSet

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

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray, 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, toArray, toArray

Field Detail

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 java.util.List<ElementOfCombinatoricsProb> elements

Constructor Detail

CombinatoricsProblem

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

Method Detail

createDifference

public java.util.ArrayList<ElementOfCombinatoricsProb> createDifference(java.util.ArrayList<ElementOfCombinatoricsProb> c)

Parameters:

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

Returns:

the differnece of the lists

sumOfWeights

public abstract double sumOfWeights(java.util.ArrayList<ElementOfCombinatoricsProb> sol)

Parameters:

sol - is the solution to be viewd

Returns:

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

formNeighborhood

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

getGraphrepresentation

public int[][] getGraphrepresentation()

createRandomNewSolution

public abstract java.util.ArrayList<ElementOfCombinatoricsProb> createRandomNewSolution(java.util.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(java.util.ArrayList<ElementOfCombinatoricsProb> sol)

evaluates the solution

Parameters:

sol - some solution

Returns:

the target function for sol

isValid

public abstract boolean isValid(java.util.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 java.lang.Double getHeuristicValue(ElementOfCombinatoricsProb solutionComponent,
                                                   java.lang.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