2.3.2 Heuristic timing

The heuristic function is called during the execution of the branch-and-bound algorithm:

1. at the beginning of the algorithm;
2. during the computation of the bound of each node of the branch-and-bound tree;
3. after the evaluation of each node of the branch-and-bound tree.

This information is saved in the function parameter heuristic_code, which can take three different values:

PRIMAL_HEUR:

if the function is called at the beginning of the algorithm;

SDP_HEUR:

if the function is called during the evaluation of the bound;

ROUNDING_HEUR:

if the function is called after the evaluation of a node.

A simple use of this information is shown in the Code 2.1 taken from heur.c.

 
double BC_runHeuristic(Problem *P0, Problem *P, BobNode *node, int *x, 
                        int heuristic_code) 
{ 
    double heur_val; 
 
    switch (heuristic_code) { 
        case PRIMAL_HEUR: 
            heur_val = primalHeuristic(P0, x); 
            break; 
        case SDP_BOUND_HEUR: 
            heur_val = sdpBoundHeuristic(P0, node, x); 
            break; 
        case ROUNDING_HEUR: 
            heur_val = roundingHeuristic(P0, node, x); 
            break; 
        default: 
            printf("Choosen␣heuristic␣doesn’t␣exist\n"); 
            exit(1); 
    } 
 
    // If x is feasible, perform a local search around x for a better solution 
    if (params.local_search && BC_isFeasibleSolution(x)) { 
        local_search(node, x, &heur_val, P0); 
    } 
 
    return heur_val; 
}