The implementation of all the methods used by the Branch and Bound algorithm. More...

#include "branch_and_bound.h"

Functions
void	dfs (SubProblem *subProblem)
	A Depth First Search algorithm on a Graph.

bool	check_hamiltonian (SubProblem *subProblem)
	Function that checks if the 1Tree of a SubProblem is a tour.

BBNodeType	mst_to_one_tree (SubProblem currentSubproblem, Graph graph)
	Transforms a MST into a 1Tree.

void	initialize_matrix (SubProblem *subProblem)

bool	infer_constraints (SubProblem *subProblem)
	Infer the values of some edge variables of a SubProblem.

void	copy_constraints (SubProblem subProblem, const SubProblem otherSubProblem)
	Copy the matrix of constraints of a SubProblem into another.

void	branch (SubProblemsList openSubProblems, SubProblem currentSubProblem)
	The Shutler's branching rule.

double	max_edge_path_1Tree (SubProblem currentSubProb, double replacement_costs, unsigned short start_node, unsigned short end_node)

int	variable_fixing (SubProblem *currentSubProb)
	The function used to fix the edge variables to be mandatory or forbidden.

void	constrained_kruskal (Graph graph, SubProblem subProblem, unsigned short candidateId)

void	constrained_prim (Graph graph, SubProblem subProblem, unsigned short candidateId)

bool	compare_subproblems (const SubProblem a, const SubProblem b)
	Compare two OPEN SubProblems.

void	bound (SubProblem *currentSubProb)
	The Held-Karp bound function with the subgradient algorithm.

bool	time_limit_reached (void)
	Check if the time limit has been reached.

void	nearest_prob_neighbour (unsigned short start_node)
	This function is used to find the first feasible tour.

bool	compare_candidate_node (SubProblem a, SubProblem b)

unsigned short	find_candidate_node (void)
	Select the candidate Node, i.e. the starting vertex of the tour.

bool	check_feasibility (Graph *graph)
	Check if the Graph associated to the Problem is feasible.

void	branch_and_bound (Problem *current_problem)
	The Branch and Bound algorithm.

void	set_problem (Problem *current_problem)
	Define the problem to solve.

void	print_subProblem (const SubProblem *subProblem)
	Get all metrics of a certain SubProblem.

void	print_problem (void)
	Get all metrics of the problem.

Detailed Description

The implementation of all the methods used by the Branch and Bound algorithm.

Author: Lorenzo Sciandra

This file contains all the methods used by the Hybrid and Classic Branch and Bound solver.

Version: 1.0.0 @data 2024-05-1

Copyright: Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file branch_and_bound.c.

Function Documentation

◆ bound()

void bound ( SubProblem * currentSubProb )

The Held-Karp bound function with the subgradient algorithm.

This function has a primal and dual behaviour: after the minimal 1Tree is found, a subgradient algorithm is used to do a dual ascent of the Lagrangian relaxation. More details at https://www.sciencedirect.com/science/article/abs/pii/S0377221796002147?via%3Dihub.

Parameters

current_problem The pointer to the SubProblem or branch-and-bound Node in the tree.

Definition at line 657 of file branch_and_bound.c.

◆ branch()

void branch	(	SubProblemsList *	openSubProblems,
		SubProblem *	subProblem
	)

The Shutler's branching rule.

Every SubProblem is branched into 2 new SubProblems, one including the "edge_to_branch" and the other not. More details at http://www.jstor.org/stable/254144.

Parameters

openSubProblems	The list of open SubProblems, to which the new SubProblems will be added.
subProblem	The SubProblem to branch.

Definition at line 256 of file branch_and_bound.c.

◆ branch_and_bound()

void branch_and_bound ( Problem * current_problem )

The Branch and Bound algorithm.

This is the main function of the Branch and Bound algorithm. It stores all the open SubProblems in a SubProblemsList and analyzes them one by one with the branch() and held_karp_bound() functions.

Parameters

current_problem The pointer to the problem to solve.

Definition at line 1012 of file branch_and_bound.c.

◆ check_feasibility()

bool check_feasibility ( Graph * graph )

Check if the Graph associated to the Problem is feasible.

A Graph is feasible if every Node has at least degree 2.

Parameters

graph The Graph to check.

Returns: true if the Graph is feasible, false otherwise.

Definition at line 997 of file branch_and_bound.c.

◆ check_hamiltonian()

bool check_hamiltonian ( SubProblem * subProblem )

Function that checks if the 1Tree of a SubProblem is a tour.

This is done by simply check if all the edges are in the cycle passing through the candidate Node.

Parameters

subProblem The SubProblem to check.

Returns: true if the SubProblem is a Hamiltonian cycle, false otherwise.

Definition at line 82 of file branch_and_bound.c.

◆ compare_candidate_node()

bool compare_candidate_node	(	SubProblem *	a,
		SubProblem *	b
	)

Definition at line 951 of file branch_and_bound.c.

◆ compare_subproblems()

bool compare_subproblems	(	const SubProblem *	a,
		const SubProblem *	b
	)

Compare two OPEN SubProblems.

This function is used to sort the SubProblems in the open list to define its order.

Parameters

a	The first SubProblem to compare.
b	The second SubProblem to compare.

Returns: true if the first SubProblem is better than the second, false otherwise.

Definition at line 647 of file branch_and_bound.c.

◆ constrained_kruskal()

void constrained_kruskal	(	Graph *	graph,
		SubProblem *	subProblem,
		unsigned short	candidateId
	)

Definition at line 503 of file branch_and_bound.c.

◆ constrained_prim()

void constrained_prim	(	Graph *	graph,
		SubProblem *	subProblem,
		unsigned short	candidateId
	)

Definition at line 565 of file branch_and_bound.c.

◆ copy_constraints()

void copy_constraints	(	SubProblem *	subProblem,
		const SubProblem *	otherSubProblem
	)

Copy the matrix of constraints of a SubProblem into another.

This function is used when a SubProblem is branched into two new SubProblems, and the constraints of the father SubProblem are copied into the sons.

Parameters

subProblem	The SubProblem to which the ConstraintType will be copied.
otherSubProblem	The SubProblem from which the ConstraintType will be copied.

Definition at line 234 of file branch_and_bound.c.

◆ dfs()

void dfs ( SubProblem * subProblem )

A Depth First Search algorithm on a Graph.

This function is used to find the cycle in the 1Tree SubProblem, passing through the candidate Node.

Parameters

subProblem The SubProblem to inspect.

Definition at line 18 of file branch_and_bound.c.

◆ find_candidate_node()

unsigned short find_candidate_node ( void )

Select the candidate Node, i.e. the starting vertex of the tour.

Every Node is tried and the one with the best lower bound is chosen. In the Hybrid mode, when two nodes have the same lower bound, the one with the best probability is chosen.

Returns: the candidate Node id.

Definition at line 961 of file branch_and_bound.c.

◆ infer_constraints()

bool infer_constraints ( SubProblem * subProblem )

Infer the values of some edge variables of a SubProblem.

According to the constraints of the father SubProblem and the one added to the son, we can infer new variables values in order to check if the SubProblem is still feasible or not.

Parameters

subProblem The SubProblem to which we want to infer the variables values.

Returns: true if the subproblem remains feasible, false otherwise.

Definition at line 185 of file branch_and_bound.c.

◆ initialize_matrix()

void initialize_matrix ( SubProblem * subProblem )

Definition at line 167 of file branch_and_bound.c.

◆ max_edge_path_1Tree()

double max_edge_path_1Tree	(	SubProblem *	currentSubProb,
		double *	replacement_costs,
		unsigned short	start_node,
		unsigned short	end_node
	)

Definition at line 342 of file branch_and_bound.c.

◆ mst_to_one_tree()

BBNodeType mst_to_one_tree	(	SubProblem *	currentSubproblem,
		Graph *	graph
	)

Transforms a MST into a 1Tree.

This is done by adding the two least-cost edges incident to the candidate Node in the MST.

Parameters

currentSubproblem	The SubProblem to which the MST belongs.
graph	The Graph of the Problem.

Returns: an enum value that indicates if the SubProblem is feasible or not.

Definition at line 88 of file branch_and_bound.c.

◆ nearest_prob_neighbour()

void nearest_prob_neighbour ( unsigned short start_node )

This function is used to find the first feasible tour.

If the Hybrid mode is disabled, it is the simple nearest neighbour algorithm. Otherwise, it also implements the Probabilistic Nearest Neighbour algorithm where, starting from a Node, the Edge with the best probability is chosen. This method is repeated by choosing every Node as the starting Node. The best tour found is stored as the best tour found so far.

Parameters

start_node The Node from which the tour will start.

Definition at line 844 of file branch_and_bound.c.

◆ print_problem()

void print_problem ( void )

Get all metrics of the problem.

It is used at the end of the algorithm to print the solution obtained. It calls the print_subProblem() function on the best SubProblem found.

Definition at line 1138 of file branch_and_bound.c.

◆ print_subProblem()

void print_subProblem ( const SubProblem * subProblem )

Get all metrics of a certain SubProblem.

It is used at the end of the algorithm to print the solution obtained.

Parameters

subProblem The SubProblem to print.

Definition at line 1073 of file branch_and_bound.c.

◆ set_problem()

void set_problem ( Problem * current_problem )

Define the problem to solve.

This function is used to set the pointer to the problem to solve.

Parameters

current_problem The pointer to the problem to solve.

Definition at line 1068 of file branch_and_bound.c.

◆ time_limit_reached()

bool time_limit_reached ( void )

Check if the time limit has been reached.

This function is used to check if the time limit has been reached.

Returns: true if the time limit has been reached, false otherwise.

Definition at line 839 of file branch_and_bound.c.

◆ variable_fixing()

int variable_fixing ( SubProblem * subProblem )

The function used to fix the edge variables to be mandatory or forbidden.

By calculating the calculating of marginal and replacement costs, the edge variables are fixed to be forbidden or mandatory. More details at https://link.springer.com/chapter/10.1007/978-3-642-13520-0_6.

Parameters

subProblem The SubProblem that we want to add the constraints to.

Returns: the num of variables fixed.

Definition at line 421 of file branch_and_bound.c.

Functions

Detailed Description

Function Documentation

◆ bound()

◆ branch()

◆ branch_and_bound()

◆ check_feasibility()

◆ check_hamiltonian()

◆ compare_candidate_node()

◆ compare_subproblems()

◆ constrained_kruskal()

◆ constrained_prim()

◆ copy_constraints()

◆ dfs()

◆ find_candidate_node()

◆ infer_constraints()

◆ initialize_matrix()

◆ max_edge_path_1Tree()

◆ mst_to_one_tree()

◆ nearest_prob_neighbour()

◆ print_problem()

◆ print_subProblem()

◆ set_problem()

◆ time_limit_reached()

◆ variable_fixing()