// main() function.
// It initiates the search for the optimal solution.
main()
// Create the root node.
create(root_node)
root_node.Type := LEAF
root_node.Offspring_List := EMPTY
// evaluate() returns the U pper Bound as the OFV of the root
// node.
root_node.OFV := evaluate(root_node.Type,root_node.Sequence,AP)
optimal_node := root_node
find_an_optimum(root_node)
// An optimal solution has been found.
Optimal_Sequence := optimal_node.Sequence
end main()
// find_optimum() recursive function.
// Examines its argument-node and updates the optimal solution if
// applicable.
find_an_optimum(parent_node)
// Create the parent node's children.
// The number of children generated depends on the parent's
// sequence.
parent_node.Offspring_List := create_list(parent_node.Sequence)
// First node-screening loop.
// It will be determined which children are worth of further
// examination.
for each child_node in Offspring_List
child_node.Type :=determine_type(child_node.Sequence)
child_node.Offspring_List := EMPTY
// If the child is a leaf node, then evaluate() returns the
// Lower Bound associated with the child's sequence.
// Otherwise, If the child is a
// terminal node, then it returns the child's actual OFV.
child_node.OFV :=
evaluate(child_node.Type,child_node.Sequence,AP)
if child_node.Type is not TERMINAL and
child_node.OFV < optimal_node.OFV
Then
continue with next child_node
elseif child_node.Type is TERMINAL and
child_node.OFV < optimal_node.OFV
Then
optimal_node := child_node
end if
remove_from(parent_node.Offspring_List,child_node)
end if
end for
// If the parent gave birth only to terminal nodes,
// the next while loop will not execute.
// Second node-screening loop.
// If any children survived, examine the one promising a better
// solution.
// After each examination eliminate from the parent's Offspring
// List all these children that would lead to a worse solution;
// then repeat the process until no child is left in the parent's
// Offspring List.
while parent_node.Offspring_List is not EMPTY
// Indentify the child with the lowest Lower Bound.
minimum_LB := PLUS_INFINITY
for each child_node in parent_node.Offspring_List
if child_node.OFV < minimum_LB
Then
chosen_child_node := child_node
end if
end for
// Examine the selected child
find_an_optimum(chosen_child_node)
remove_from(parent_node.Offspring_List,chosen_child_node)
// Eliminate children that would lead the B&B to a worse
// solution.
for each child_node in parent_node.Offspring_List
if child_node.OFV >= optimal_node.OFV
Then
remove_from(parent_node.Offspring_List,child_node)
end if
end for
end while
end find_an_optimum()
Can someone help me to get a good start on this. I just need some direction.
