Tree (JaCoP 4.9.0 API)

java.lang.Object
- org.jacop.constraints.knapsack.Tree

```
public class Tree
extends Object
```
This tree is a main data structure used and required by Knapsack constraint.

Version:

4.9

Author:

Radoslaw Szymanek and Wadeck Follonier

Field Summary

Fields
Modifier and Type	Field and 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().
`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.
`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 and Description
`Tree(KnapsackItem[] items, 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 and 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 mandatory
`TreeLeaf`	`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 ancients
`void`	`recompute()` It recomputes all the attributes of the internal nodes of the knapsack tree.
`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(List<TreeLeaf> list, int startingPosition)` Used for updating the tree using a list of nodes that have changed.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- 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.
  - 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,
            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 String toString()
```
    Overrides:
    
    toString in class Object
  - updateFromList
```
public void updateFromList(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.

Class Tree

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

root

criticalLeaf

criticalRightLeaf

criticalLeftLeaf

first

last

optimalProfit

availableWeightOfCriticalItem

takenWeightOfCriticalItem

alreadyObtainedProfit

alreadyUsedCapacity

exhaustedRightItems

exhaustedLeftItems

Constructor Detail

Tree

Tree

Tree

Method Detail

merge

updateCritical

getCriticalPosition

getFirst

getLast

toString

updateFromList

recompute

initializeComputeMandatory

computeReplacableWeight

findNextLeafAtLeastOfWeight

initializeComputeForbidden

computeIntrusionWeight

findPreviousLeafAtLeastOfWeight

computeMinWeight

computeMinProfit