16#ifndef BRANCHANDBOUND1TREE_B_AND_B_DATA_H
17#define BRANCHANDBOUND1TREE_B_AND_B_DATA_H
void add_elem_SubProblemList_index(SubProblemsList *list, SubProblem *element, size_t index)
Add a SubProblem at a specific index of a SubProblem List.
bool is_SubProblemList_iterator_valid(SubProblemsListIterator *iterator)
Check if a SubProblem List iterator is valid.
SubProblem * get_SubProblemList_elem_index(SubProblemsList *list, size_t index)
Get a SubProblem from a specific index of a SubProblem List.
ConstraintType
The enum used to identify the type of Edge constraints.
@ FORBIDDEN
The Edge is forbidden.
@ MANDATORY
The Edge is mandatory.
@ NOTHING
The Edge has no constraints.
void delete_SubProblemList_iterator(SubProblemsListIterator *iterator)
Delete a SubProblem List iterator.
BBNodeType
The labels used to identify the type of a SubProblem.
@ OPEN
The SubProblem is a feasible 1Tree, with a value lower than the best solution found so far.
@ CLOSED_NN
The SubProblem is a feasible 1Tree founded with the Nearest Neighbor algorithm, it is the first feasi...
@ CLOSED_1TREE
The SubProblem is closed by calculating the 1Tree.
@ CLOSED_NN_HYBRID
The SubProblem is a feasible 1Tree founded with the Hybrid version of Nearest Neighbor algorithm,...
@ CLOSED_BOUND
The SubProblem is a feasible 1Tree, with a value greater than the best solution found so far.
@ CLOSED_UNFEASIBLE
The SubProblem is not a feasible 1Tree, and so discarded.
@ CLOSED_SUBGRADIENT
The SubProblem is closed in the subgradient algorithm, the ascending dual.
size_t get_SubProblemList_size(SubProblemsList *list)
Get the size of a SubProblem List.
void delete_SubProblemList_elem_index(SubProblemsList *list, size_t index)
Remove a SubProblem from a specific index of a SubProblem List.
void add_elem_SubProblemList_bottom(SubProblemsList *list, SubProblem *element)
Add a SubProblem to the bottom of a SubProblem List.
SubProblemsListIterator * create_SubProblemList_iterator(SubProblemsList *list)
Create a new SubProblem List iterator on a SubProblem List.
void new_SubProblemList(SubProblemsList *list)
Create a new SubProblem List.
bool is_SubProblemList_empty(SubProblemsList *list)
Check if a SubProblem List is empty.
void delete_SubProblemList(SubProblemsList *list)
Delete a SubProblem List.
SubProblem * SubProblemList_iterator_get_next(SubProblemsListIterator *iterator)
Get the next element of a SubProblem List iterator.
This file contains the declaration of the Minimum Spanning Tree datastructure.
A reduced form of an Edge in the Graph, with only the source and destination Nodes.
Minimum Spanning Tree, or MST, and also a 1-Tree.
The struct used to represent the overall problem.
Graph reformulationGraph
The Graph used to perform the dual reformulation of Edge weights.
bool interrupted
True if the algorithm has been interrupted by timeout.
SubProblem bestSolution
The best solution found so far.
clock_t end
The time when the algorithm ended.
clock_t start
The time when the algorithm started.
Graph graph
The Graph of the problem.
unsigned short candidateNodeId
The id of the candidate node.
unsigned int num_fixed_edges
The number of fixed edges in the Branch and Bound tree.
unsigned int generatedBBNodes
The number of nodes generated in the Branch and Bound tree.
unsigned short totTreeLevels
The total number of levels in the Branch and Bound tree.
double bestValue
The cost of the best solution found so far.
unsigned int exploredBBNodes
The number of nodes explored in the Branch and Bound tree.
The element of the list of SubProblems.
SubProblem subProblem
The SubProblem.
struct SubProblemElem * next
The next element of the list.
struct SubProblemElem * prev
The previous element of the list.
The struct used to represent a SubProblem or node of the Branch and Bound tree.
ConstraintType constraints[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
The constraints of the edges in the SubProblem.
ConstrainedEdge mandatoryEdges[MAX_VERTEX_NUM]
The mandatory edges in the SubProblem.
float timeToReach
The time needed to reach the SubProblem, in seconds.
ConstrainedEdge cycleEdges[MAX_VERTEX_NUM]
The edges in the cycle of the SubProblem.
unsigned short num_forbidden_edges
The number of forbidden edges in the SubProblem.
double prob
The probability of the SubProblem to be the best tour.
unsigned int id
The id of the SubProblem, an incremental number.
double value
The cost of the SubProblem.
unsigned int fatherId
The id of the father of the SubProblem.
int edge_to_branch
The id of the edge to branch in the SubProblem.
BBNodeType type
The label of the SubProblem.
MST oneTree
The 1Tree of the SubProblem.
unsigned short treeLevel
The level of the SubProblem in the Branch and Bound tree.
unsigned short num_mandatory_edges
The number of mandatory edges in the SubProblem.
unsigned short num_edges_in_cycle
The number of edges in the cycle of the SubProblem.
The iterator of the list of SubProblems.
size_t index
The index of the current element of the list.
SubProblemsList * list
The list to iterate.
SubProblemElem * curr
The current element of the list.
The list of open SubProblems.
SubProblemElem * tail
The tail of the list.
SubProblemElem * head
The head of the list.
size_t size
The size of the list.
