public class Tree extends Object
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 nonintegral 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 nonintegral 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
nonfractional solution.

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.

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.

public final TreeNode root
public TreeLeaf criticalLeaf
public int criticalRightLeaf
public int criticalLeftLeaf
public TreeLeaf first
public TreeLeaf last
public double optimalProfit
public int availableWeightOfCriticalItem
public int takenWeightOfCriticalItem
public int alreadyObtainedProfit
public int alreadyUsedCapacity
public boolean exhaustedRightItems
public boolean exhaustedLeftItems
public Tree(TreeNode node)
node
 a root of this onenode tree.public Tree(Tree tree)
tree
 tree to be constructedpublic Tree(KnapsackItem[] items, Map<IntVar,TreeLeaf> varPositionMaping, TreeLeaf[] leaves, IntVar zero)
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.public Tree merge(Tree that)
that
 A tree that is being merged with this tree.public void updateCritical(int capacity)
capacity
 available capacity to be used by knapsack.public int getCriticalPosition(int capacity)
capacity
 available capacity to be used by knapsack.public TreeLeaf getFirst()
public TreeLeaf getLast()
public void updateFromList(List<TreeLeaf> list, int startingPosition)
list
 list of leaves that needs to be updated.startingPosition
 it specifies the first leaf in the array which has not been updated before.public void recompute()
public void initializeComputeMandatory()
public int computeReplacableWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
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.public TreeLeaf findNextLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
leaf
 starting leaf, the result must be to the right of this leaf.weight
 weight condition which must be satisfied by the found leaf.public void initializeComputeForbidden()
public int computeIntrusionWeight(int weightOfItemChecked, int maxNoOfItems, int profitOfItemChecked, double efficiencyOfItemChecked, double profitSlack)
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.public TreeLeaf findPreviousLeafAtLeastOfWeight(TreeLeaf leaf, int weight)
leaf
 starting leaf, the result must be to the left of this leaf.weight
 weight condition which must be satisfied by the found leaf.public int computeMinWeight(int minProfit)
minProfit
 minimum profit obtained by the knapsack.public int computeMinProfit(int minWeight)
minWeight
  the minimum of weight within a knapsack.Copyright © 2022. All rights reserved.