Contains all the execution settings. More...

#include <stdio.h>
#include <limits.h>
#include <float.h>
#include <string.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <errno.h>
#include <pthread.h>

Macros
#define	INFINITE DBL_MAX
	The maximum number to set the initial value of Problem and SubProblem.

#define	PRIM 1
	The maximum number of Node in the Graph.

#define	MAX_EDGES_NUM (MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2)
	The maximum number of edges in the Graph.

#define	GHOSH_UB (sqrt(MAX_VERTEX_NUM) * 1.27f)
	The first upper bound for the problem, see: https://www.semanticscholar.org/paper/Expected-Travel-Among-Random-Points-in-a-Region-Ghosh/4c395ab42054f4312ad24cb500fb8ca6f7ad3a6c.

#define	TRACE() fprintf(stderr, "%s (%d): %s\n", __FILE__, __LINE__, __func__)
	Used to debug the code, to check if the execution reaches a certain point.

#define	EPSILON (GHOSH_UB / 1000)
	The first constant used to compare two SubProblem in the branch and bound algorithm.

#define	EPSILON2 (0.1f * EPSILON)
	The second constant used to compare two SubProblem in the branch and bound algorithm.

#define	BETTER_PROB 0.05f
	The third constant used to compare two SubProblem in the branch and bound algorithm.

#define	PROB_BRANCH 0.5f
	The way with generate the children of a SubProblem.

#define	TIME_LIMIT_SECONDS 600
	The maximum time to run the algorithm. Default: 10 minutes.

#define	NUM_HK_INITIAL_ITERATIONS (((((float) MAX_VERTEX_NUM * MAX_VERTEX_NUM)/50) + 0.5f) + MAX_VERTEX_NUM + 15)
	The maximum number of dual iterations for the root of the branch and bound tree.

#define	NUM_HK_ITERATIONS (((float) MAX_VERTEX_NUM / 4) + 5)
	The maximum number of dual iterations for nodes of the branch and bound tree that are not the root.

Detailed Description

Contains all the execution settings.

Author: Lorenzo Sciandra

Not only MACROs for branch-and-bound, but also for testing and debugging. The two MACROs MAX_VERTEX_NUM and HYBRID that are used to set the maximum number of Node in the Graph and to choose the algorithm to use are now in the CMakeLists.txt file, so that they can be changed from the command line.

Version: 1.0.0 @data 2024-05-1

Copyright: Copyright (c) 2024, license MIT

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

Definition in file problem_settings.h.

Macro Definition Documentation

◆ BETTER_PROB

#define BETTER_PROB 0.05f

The third constant used to compare two SubProblem in the branch and bound algorithm.

If two SubProblem are within EPSILON2 (and therefore equal), the one that has a greater probability than the other of at least BETTER_PROB is considered better.

See also: branch_and_bound.c::compare_subproblems()

Definition at line 82 of file problem_settings.h.

◆ EPSILON

#define EPSILON (GHOSH_UB / 1000)

The first constant used to compare two SubProblem in the branch and bound algorithm.

Two SubProblem are considered equal if their lower bound is within EPSILON of each other.

See also: branch_and_bound.c::compare_subproblems()

Definition at line 65 of file problem_settings.h.

◆ EPSILON2

#define EPSILON2 (0.1f * EPSILON)

The second constant used to compare two SubProblem in the branch and bound algorithm.

If two SubProblem are equal and their lower bound is within EPSILON2 of each other, their probability is compared.

See also: branch_and_bound.c::compare_subproblems()

Definition at line 73 of file problem_settings.h.

◆ GHOSH_UB

#define GHOSH_UB (sqrt(MAX_VERTEX_NUM) * 1.27f)

The first upper bound for the problem, see: https://www.semanticscholar.org/paper/Expected-Travel-Among-Random-Points-in-a-Region-Ghosh/4c395ab42054f4312ad24cb500fb8ca6f7ad3a6c.

Definition at line 53 of file problem_settings.h.

◆ INFINITE

#define INFINITE DBL_MAX

The maximum number to set the initial value of Problem and SubProblem.

Definition at line 33 of file problem_settings.h.

◆ MAX_EDGES_NUM

#define MAX_EDGES_NUM (MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2)

The maximum number of edges in the Graph.

Definition at line 49 of file problem_settings.h.

◆ NUM_HK_INITIAL_ITERATIONS

#define NUM_HK_INITIAL_ITERATIONS (((((float) MAX_VERTEX_NUM * MAX_VERTEX_NUM)/50) + 0.5f) + MAX_VERTEX_NUM + 15)

The maximum number of dual iterations for the root of the branch and bound tree.

Definition at line 100 of file problem_settings.h.

◆ NUM_HK_ITERATIONS

#define NUM_HK_ITERATIONS (((float) MAX_VERTEX_NUM / 4) + 5)

The maximum number of dual iterations for nodes of the branch and bound tree that are not the root.

Definition at line 104 of file problem_settings.h.

◆ PRIM

#define PRIM 1

The maximum number of Node in the Graph.

The parameter to choose the algorithm to use, 0 for Classic B&B, 1 for Hybrid B&B. 1 if the MST is solved with the Prim algorithm using Fibonacci Heap, 0 if it is solved with the Kruskal algorithm using MFSets.

Definition at line 45 of file problem_settings.h.

◆ PROB_BRANCH

#define PROB_BRANCH 0.5f

The way with generate the children of a SubProblem.

If the probability of a SubProblem is greater than PROB_BRANCH, the children are generated by first imposing the constraint that the edge (i, j) is in the solution and then the constraint that it is not. Otherwise, the children are generated by imposing the constraint that the edge (i, j) is not in the solution and then the constraint that it is.

See also: branch_and_bound.c::branch()

Definition at line 92 of file problem_settings.h.

◆ TIME_LIMIT_SECONDS

#define TIME_LIMIT_SECONDS 600

The maximum time to run the algorithm. Default: 10 minutes.

Definition at line 96 of file problem_settings.h.

◆ TRACE

#define TRACE ( ) fprintf(stderr, "%s (%d): %s\n", __FILE__, __LINE__, __func__)

Used to debug the code, to check if the execution reaches a certain point.

Definition at line 57 of file problem_settings.h.

Macros