BiqCrunch offers generic heuristics which are useful when the user prefers not writing their own specific heuristic. These generic heuristics can be used for any binary quadratic problem and can be found in src/rounding.c (as well as the simple one-opt local search algorithm). During the computation of the bound of the node (heur_2), and after the evaluation of each node (heur_3), BiqCrunch uses the celebrated Goemans-Williamson heuristic.
By adding the corresponding calls in heur.c file, the user can also use a variant of the classical randomized rounding heuristic [9, 10] that rounds to 0 or 1 the variables according to the probability provided by the fractional SDP solution. Indeed one has 0 ≤ xi ≤ 1 for any feasible solution of the SDP relaxation (see [8] for details about the relaxations used). The rounding is done by comparing each xi to a fixed α = xj, for j = 1,…,n. Then BiqCrunch tests if the resulting 0-1 vector is feasible for the combinatorial problem, and updates the best current feasible solution if a better feasible solution is found. Afterwards, BiqCrunch generates an additional 100 random binary vectors by comparing each fractional xi to a different random value γ, and again updates the best current feasible solution if a better feasible solution is found.
At the root node we generate a random vector of values in the interval [0,1] and then we apply the variant of randomized algorithm described before. To call or create new heuristics for a specific problem, one has to modify the heur.c source file in the corresponding subdirectory in problems (e.g., problems/max-cut/heur.c).