Need Help Converting Pseudocode to C++ to find Branch-and-Bound for the Early/Tardy Problem with a Common Due-Date

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 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
else
if 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.
Write a node class.
There are some functions in pseudocode. Define these functions.
Then convert main function, loops and if conditions to c++ code.
Topic archived. No new replies allowed.