Package org.jacop.constraints.knapsack
Class Tree
- java.lang.Object
-
- org.jacop.constraints.knapsack.Tree
-
public class Tree extends java.lang.Object
This tree is a main data structure used and required by Knapsack constraint.- Version:
- 4.8
-
-
Field Summary
Fields Modifier and Type Field Description int
alreadyObtainedProfit
It specifies the already obtained profit due to the items which are already included in the solution.int
alreadyUsedCapacity
It specifies the already used capacity due to the items which are already included in the solution.int
availableWeightOfCriticalItem
It specifies the fraction of the critical item which has been not included in the optimal non-integral solution.TreeLeaf
criticalLeaf
It specifies the leaf containing the critical item.int
criticalLeftLeaf
It specifies the leaf containing the left most item which is being used during computeForbidden().int
criticalRightLeaf
It specifies the leaf containing the last right item which is being used during computeMandatory().(package private) TreeNode
currentNode
It specifies the current right item of the tree which have been yet included in computation of replaceable weight.(package private) int
currentProfit
It specifies the current profit obtained by all already traversed right items.(package private) int
currentWeight
It specifies the currentWeight from which searching for next mandatory item starts from.boolean
exhaustedLeftItems
It specifies that computeForbidden part of the consistency function has run out of left mandatory items.boolean
exhaustedRightItems
It specifies if the mandatory check has run out of right items to complement mandatory items.TreeLeaf
first
It specifies the first (counting from left to right), the most efficient item in the tree.TreeLeaf
last
It specifies the last (counting from left to right), the least efficient item in the tree.double
optimalProfit
It specifies the optimalProfit of possibly non-integral solution generated by LP relaxation.(package private) double
profitFromCriticalLeft
It specifies the profit obtained from the remaining part of the critical item.(package private) double
profitFromCriticalTaken
It specifies the profit obtained from the remaining part of the critical item.TreeNode
root
It specifies the root of the tree.int
takenWeightOfCriticalItem
It specifies how much weight is used by an optimal non-fractional solution.
-
Constructor Summary
Constructors Constructor Description Tree(KnapsackItem[] items, java.util.Map<IntVar,TreeLeaf> varPositionMaping, TreeLeaf[] leaves, IntVar zero)
It constructs a tree out of the list of items and creates proper supporting structures.Tree(Tree tree)
It creates a tree by making a shallow copy.Tree(TreeNode node)
Create a single node tree.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
computeIntrusionWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
It returns the amount of weight of a given item being checked which can be replaced by Right items given the amount of profitSlack.int
computeMinProfit(int minWeight)
It computes the minimum of capacity variable for knapsack constraint given the minimum requirement for profit.int
computeMinWeight(int minProfit)
It computes the minimum of capacity variable for knapsack constraint given the minimum requirement for profit.int
computeReplacableWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
It returns the amount of weight of a given item being checked which can be replaced by Right items given the amount of profitSlack.TreeLeaf
findNextLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
It finds next leaf of a maximum weight of at least weight, so it can have some parts of it mandatory.TreeLeaf
findPreviousLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
It finds previous leaf of a maximum weight of at least weight, so it can have some parts of it forbidden.int
getCriticalPosition(int capacity)
It finds a leaf which reaches the limit of the given capacity.TreeLeaf
getFirst()
Used to search for mandatoryTreeLeaf
getLast()
It returns the last (the least efficient) item in the tree.void
initializeComputeForbidden()
It initializes the private variables required by computation of how much weight we can replace for any Left item.void
initializeComputeMandatory()
It initializes the private variables required by computation of how much weight we can replace for any Left item.Tree
merge(Tree that)
A merge method for trees, it added a new root from the ancientsvoid
recompute()
It recomputes all the attributes of the internal nodes of the knapsack tree.java.lang.String
toString()
void
updateCritical(int capacity)
It updates information about the critical item, as well as information about fraction of critical item which is not taken.void
updateFromList(java.util.List<TreeLeaf> list, int startingPosition)
Used for updating the tree using a list of nodes that have changed.
-
-
-
Field Detail
-
root
public final TreeNode root
It specifies the root of the tree.
-
criticalLeaf
public TreeLeaf criticalLeaf
It specifies the leaf containing the critical item. The critical item is the one used partially by Linear Programming approach.
-
criticalRightLeaf
public int criticalRightLeaf
It specifies the leaf containing the last right item which is being used during computeMandatory(). if max() of the right item after criticalRight is changed then it can be safely ignored.
-
criticalLeftLeaf
public int criticalLeftLeaf
It specifies the leaf containing the left most item which is being used during computeForbidden(). if min() of the left item before criticalLeft is changed then it can be safely ignored.
-
first
public TreeLeaf first
It specifies the first (counting from left to right), the most efficient item in the tree.
-
last
public TreeLeaf last
It specifies the last (counting from left to right), the least efficient item in the tree.
-
optimalProfit
public double optimalProfit
It specifies the optimalProfit of possibly non-integral solution generated by LP relaxation.
-
availableWeightOfCriticalItem
public int availableWeightOfCriticalItem
It specifies the fraction of the critical item which has been not included in the optimal non-integral solution.
-
takenWeightOfCriticalItem
public int takenWeightOfCriticalItem
It specifies how much weight is used by an optimal non-fractional solution.
-
alreadyObtainedProfit
public int alreadyObtainedProfit
It specifies the already obtained profit due to the items which are already included in the solution.
-
alreadyUsedCapacity
public int alreadyUsedCapacity
It specifies the already used capacity due to the items which are already included in the solution.
-
currentNode
TreeNode currentNode
It specifies the current right item of the tree which have been yet included in computation of replaceable weight.
-
currentWeight
int currentWeight
It specifies the currentWeight from which searching for next mandatory item starts from. Only items with weight greater or equal to currentWeight can be (partially) mandatory.
-
currentProfit
int currentProfit
It specifies the current profit obtained by all already traversed right items.
-
profitFromCriticalLeft
double profitFromCriticalLeft
It specifies the profit obtained from the remaining part of the critical item.
-
profitFromCriticalTaken
double profitFromCriticalTaken
It specifies the profit obtained from the remaining part of the critical item.
-
exhaustedRightItems
public boolean exhaustedRightItems
It specifies if the mandatory check has run out of right items to complement mandatory items.
-
exhaustedLeftItems
public boolean exhaustedLeftItems
It specifies that computeForbidden part of the consistency function has run out of left mandatory items.
-
-
Constructor Detail
-
Tree
public Tree(TreeNode node)
Create a single node tree.- Parameters:
node
- a root of this one-node tree.
-
Tree
public Tree(Tree tree)
It creates a tree by making a shallow copy.- Parameters:
tree
- tree to be constructed
-
Tree
public Tree(KnapsackItem[] items, java.util.Map<IntVar,TreeLeaf> varPositionMaping, TreeLeaf[] leaves, IntVar zero)
It constructs a tree out of the list of items and creates proper supporting structures. It assumes the list of items is greater than 1.- Parameters:
items
- knapsack items used to create the tree.varPositionMaping
- mapping of variables into positions within the tree.leaves
- array of leaves of the created tree.zero
- it specifies a variable equal to value 0.
-
-
Method Detail
-
merge
public Tree merge(Tree that)
A merge method for trees, it added a new root from the ancients- Parameters:
that
- A tree that is being merged with this tree.- Returns:
- The tree resulting of the merge of this and that
-
updateCritical
public void updateCritical(int capacity)
It updates information about the critical item, as well as information about fraction of critical item which is not taken.- Parameters:
capacity
- available capacity to be used by knapsack.
-
getCriticalPosition
public int getCriticalPosition(int capacity)
It finds a leaf which reaches the limit of the given capacity. Items weight is added from the most efficient to the least efficient.- Parameters:
capacity
- available capacity to be used by knapsack.- Returns:
- the position of the item.
-
getFirst
public TreeLeaf getFirst()
Used to search for mandatory- Returns:
- The first item
-
getLast
public TreeLeaf getLast()
It returns the last (the least efficient) item in the tree. It is a starting leaf for computeForbidden() part.- Returns:
- The last item
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
updateFromList
public void updateFromList(java.util.List<TreeLeaf> list, int startingPosition)
Used for updating the tree using a list of nodes that have changed.- Parameters:
list
- list of leaves that needs to be updated.startingPosition
- it specifies the first leaf in the array which has not been updated before.
-
recompute
public void recompute()
It recomputes all the attributes of the internal nodes of the knapsack tree.
-
initializeComputeMandatory
public void initializeComputeMandatory()
It initializes the private variables required by computation of how much weight we can replace for any Left item.
-
computeReplacableWeight
public int computeReplacableWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
It returns the amount of weight of a given item being checked which can be replaced by Right items given the amount of profitSlack.- Parameters:
weightOfItemChecked
- the weight of item being checked.maxNoOfItems
- the maximum number which can be taken of checked items.profitOfItemChecked
- the profit of the item being checked.efficiencyOfItemChecked
- the efficiency of the item being checked.profitSlack
- the amount of reserve profit which can be sacrificed before violating the constraint.- Returns:
- the amount of weight of a given item that can be replaced by Right items without violating the constraint.
-
findNextLeafAtLeastOfWeight
public TreeLeaf findNextLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
It finds next leaf of a maximum weight of at least weight, so it can have some parts of it mandatory.- Parameters:
leaf
- starting leaf, the result must be to the right of this leaf.weight
- weight condition which must be satisfied by the found leaf.- Returns:
- tree leaf on the right to the supplied leaf with at least specified weight.
-
initializeComputeForbidden
public void initializeComputeForbidden()
It initializes the private variables required by computation of how much weight we can replace for any Left item.
-
computeIntrusionWeight
public int computeIntrusionWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
It returns the amount of weight of a given item being checked which can be replaced by Right items given the amount of profitSlack.- Parameters:
weightOfItemChecked
- the weight of item being checked.maxNoOfItems
- the maximum number which can be taken of checked items.profitOfItemChecked
- the profit of the item being checked.efficiencyOfItemChecked
- the efficiency of the item being checked.profitSlack
- the amount of reserve profit which can be sacrificed before violating the constraint.- Returns:
- the amount of weight of a given item that can be replaced by Right items without violating the constraint.
-
findPreviousLeafAtLeastOfWeight
public TreeLeaf findPreviousLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
It finds previous leaf of a maximum weight of at least weight, so it can have some parts of it forbidden.- Parameters:
leaf
- starting leaf, the result must be to the left of this leaf.weight
- weight condition which must be satisfied by the found leaf.- Returns:
- tree leaf on the left to the supplied leaf with at least specified weight.
-
computeMinWeight
public int computeMinWeight(int minProfit)
It computes the minimum of capacity variable for knapsack constraint given the minimum requirement for profit.- Parameters:
minProfit
- minimum profit obtained by the knapsack.- Returns:
- it returns the minimum required weight to satisfy min profit requirements.
-
computeMinProfit
public int computeMinProfit(int minWeight)
It computes the minimum of capacity variable for knapsack constraint given the minimum requirement for profit.- Parameters:
minWeight
- - the minimum of weight within a knapsack.- Returns:
- it returns the minimum required weight to satisfy min profit requirements.
-
-