JaCoP.search
Class SimpleMatrixSelect<T extends Var>

java.lang.Object
  JaCoP.search.SimpleMatrixSelect<T>

Type Parameters:

T - type of variable being used in the Search.

All Implemented Interfaces:

SelectChoicePoint<T>

public class SimpleMatrixSelect<T extends Var>
extends java.lang.Object
implements SelectChoicePoint<T>

SimpleMatrixSelect selects first a row in the matrix based on metric of the variable at pivotPosition. As soon as a row is choosen, variables starting from the beginning of the row which are not assigned yet are selected. The row selection is done with the help of variable comparators. Two comparators can be employed main and tiebreaking one. If two are not sufficient to differentiate two rows than the lexigraphical ordering is used. Default values: pivotPosition = 0, mainComparator = InputOrder, tieBreakingComparator = InputOrder.

Version:

3.1

Author:

Radoslaw Szymanek and Krzysztof Kuchcinski

Field Summary

boolean	inputOrderTieBreaking It decides if input order tiebreaking is used.
int	pivotPosition It specifies the pivot position (first element has index 0).
java.util.IdentityHashMap<T,java.lang.Integer>	position It stores the original positions of variables to be used for input order tie-breaking.
java.util.ArrayList<java.util.ArrayList<T>>	searchVariables It stores variables which need to be labelled.

Constructor Summary

SimpleMatrixSelect(T[][] vars, ComparatorVariable<T> mainComparator, ComparatorVariable<T> tieBreakingComparator, Indomain<T> indomain)
It constructs a MatrixSelection variable ordering.

SimpleMatrixSelect(T[][] vars, ComparatorVariable<T> mainComparator, ComparatorVariable<T> tieBreakingComparator, Indomain<T> indomain, int pivotPosition)
This constructor allows to specify all parameters for the selection mechanism.

SimpleMatrixSelect(T[][] vars, ComparatorVariable<T> mainComparator, Indomain<T> indomain)
It constructs a MatrixSelection variable ordering.

SimpleMatrixSelect(T[][] vars, Indomain<T> indomain)
This constructor uses default values for all parameters.

Method Summary

PrimitiveConstraint	getChoiceConstraint(int index) It always returns null as choice point is obtained by getChoiceVariable and getChoiceValue.
int	getChoiceValue() It returns a value which is the base of the next choice point.
T	getChoiceVariable(int firstVariable) It returns the variable which is the base on the next choice point.
int	getIndex() It returns the current index.
int	getPivotPosition() It returns the position of the pivot variable.
java.util.IdentityHashMap<T,java.lang.Integer>	getVariablesMapping() It returns the variables for which assignment in the solution is given.
void	setDynamicLexTieBreaking() It uses cheap method of breaking the ties.
void	setInputOrderTieBreaking() It chooses input order tiebreaking if the supplied comparators can not distinguish between matrix rows.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

inputOrderTieBreaking

public boolean inputOrderTieBreaking

It decides if input order tiebreaking is used. If input tiebreaking is not used than the current arrangement of row, variables within rows decides on the priority. The arrangement of the rows, variables within rows depends on the search history. Setting it to false makes the final tiebreaking a mixture of input-order/search history influenced tie breaking. It is faster to compute tiebreaking and it may give interesting search history based tiebreaking.

pivotPosition

public int pivotPosition

It specifies the pivot position (first element has index 0).

position

public java.util.IdentityHashMap<T extends Var,java.lang.Integer> position

It stores the original positions of variables to be used for input order tie-breaking.

searchVariables

public java.util.ArrayList<java.util.ArrayList<T extends Var>> searchVariables

It stores variables which need to be labelled.

Constructor Detail

SimpleMatrixSelect

public SimpleMatrixSelect(T[][] vars,
                          Indomain<T> indomain)

This constructor uses default values for all parameters. The size of the sublist is equal to two. The pivot position points to the first element. The tiebreaking delete used is DeleteMostConstrainedStatic.

Parameters:

vars - variables to choose from.

indomain - value ordering heuristic used to choose a value for a given variable.

SimpleMatrixSelect

public SimpleMatrixSelect(T[][] vars,
                          ComparatorVariable<T> mainComparator,
                          Indomain<T> indomain)

It constructs a MatrixSelection variable ordering.

Parameters:

vars - matrix of variables to be selected from.

mainComparator - the variable comparator to choose the proper vector.

indomain - variable ordering value to be used to determine value for a given variable.

SimpleMatrixSelect

public SimpleMatrixSelect(T[][] vars,
                          ComparatorVariable<T> mainComparator,
                          ComparatorVariable<T> tieBreakingComparator,
                          Indomain<T> indomain)

It constructs a MatrixSelection variable ordering.

Parameters:

vars - matrix of variables to be selected from.

mainComparator - the variable comparator to choose the proper vector.

tieBreakingComparator - the variable comparator used if the main comparator can not distinguish between vectors.

indomain - variable ordering value to be used to determine value for a given variable.

SimpleMatrixSelect

public SimpleMatrixSelect(T[][] vars,
                          ComparatorVariable<T> mainComparator,
                          ComparatorVariable<T> tieBreakingComparator,
                          Indomain<T> indomain,
                          int pivotPosition)

This constructor allows to specify all parameters for the selection mechanism. Specifying mainComparator or tieBreaking to value null do not use that functionality of the selection mechanims.

Parameters:

vars - variables from which the base of the choice point is choosen.

mainComparator - the main variable comparator used to compare variables.

tieBreakingComparator - the secondary variable comparator used to break ties.

indomain - the value ordering heuristic used to assign value to a chosen variable.

pivotPosition - the position of the variable which is used to rank the rows.

Method Detail

getChoiceVariable

public T getChoiceVariable(int firstVariable)

It returns the variable which is the base on the next choice point. Only if choice is of an X = C type. This function returns null if all variables have a value assigned or a choice point based on other type of constraint is being selected. The parameter index is the last value which have been return by this SelectChoicePoint object which has not been backtracked upon yet.

Specified by:

getChoiceVariable in interface SelectChoicePoint<T extends Var>

Parameters:

firstVariable - the position of the last variable in selection choice point heuristic.

Returns:

variable based on which the choice needs to be created.

getChoiceValue

public int getChoiceValue()

It returns a value which is the base of the next choice point. Only if choice is of an X = C type.

Specified by:

getChoiceValue in interface SelectChoicePoint<T extends Var>

Returns:

value used in the choice point (value).

getChoiceConstraint

public PrimitiveConstraint getChoiceConstraint(int index)

It always returns null as choice point is obtained by getChoiceVariable and getChoiceValue.

Specified by:

getChoiceConstraint in interface SelectChoicePoint<T extends Var>

Parameters:

index - the position of the last variable returned by selection choice point heuristic.

Returns:

primitive constraint which is a base of a choice point.

getVariablesMapping

public java.util.IdentityHashMap<T,java.lang.Integer> getVariablesMapping()

It returns the variables for which assignment in the solution is given.

Specified by:

getVariablesMapping in interface SelectChoicePoint<T extends Var>

Returns:

mapping of variables to the positions in the variables array.

getIndex

public int getIndex()

It returns the current index. Supplying this value in the next invocation of select will make search for next variable faster without comprimising efficiency.

Specified by:

getIndex in interface SelectChoicePoint<T extends Var>

Returns:

internal position of the last variable chosen to be the base of the choice point.

getPivotPosition

public int getPivotPosition()

It returns the position of the pivot variable.

Returns:

the position of the pivot variable.

setDynamicLexTieBreaking

public void setDynamicLexTieBreaking()

It uses cheap method of breaking the ties. It is based on input order influenced by the search history.

setInputOrderTieBreaking

public void setInputOrderTieBreaking()

It chooses input order tiebreaking if the supplied comparators can not distinguish between matrix rows.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object