int QSopt_strongbranch (QSprob p, int ncand, int *candidatelist,
    double *xlist, double *down_vals, double *up_vals, int iterations,
    double objbound)

This function is used to implement the strong-branching rule used by Applegate, Bixby, Chvátal, and Cook in their TSP research. The idea is to use strong LP information to determine a choice of branching variable that is likely to increase the LP bound for each of the two children created by the branching operation.

For each of the column indices specified in the array candidatelist (this array is of length ncand), the function will gather information about the bounds that can be obtained by branching on the corresponding variable.

Let j be the ith index in candidatelist. In the branching test, variable j first has its upper bound set to floor(xlist[i]) and then variable j has its lower bound set to ceil(xlist[i]), and in both cases the dual steepest-edge simplex algorithm is called with an iteration limit of iterations pivots. The resulting objective values are returned in the arrays down_vals (for the values where the variables have their upper bounds modified) and up_vals (for the values where the variables have their lower bounds modified). If the argument xlist is not specified, then QSopt_strongbranch uses the x-vector in the current LP solution to determine the points where the branches occur. (Note that for 0-1 valued variables, the branches correspond to setting the variables equal to 0 for the down-branch and equal to 1 for the up-branch.)

The parameter objbound should be set by the calling routine to be an upper bound on the objective function value for minimization problems, and to a lower bound on the objective function value for maximization problems. (This can be used to terminate the optimization routines early, if the bound is obtained in less than iterations pivots. The value of objbound can be set to the value of the best available MIP solution.) The values returned in down_vals and up_vals will be no larger than objbound for minimization problems, and no smaller than objbound for maximization problems.

/* Assume p is a QSprob, a handle to an existing LP problem, that has */
/* been solved with one of the optimization routines.  All variables  */
/* in p will be considered as integer variables, and a candidate      */
/* for a branching variable will be determined using strong-          */
/* branching.  The index of the branching variable is the return      */
/* value of the code fragment.                                        */
/*                                                                    */
/* Assume x is an array containing the current solution to the LP;    */
/* it could be obtained using QSget_x_array ().                       */
/*                                                                    */
/* Assume ObjBound is the objective value of the best integer         */
/* solution known for the problem.                                    */

int rval, i, ncols, ncand, branch = -1;
int *candidatelist = (int *) NULL;
double *xlist, *down_vals, *up_vals;
double bestval;

ncols = QSget_colcount (p);

candidatelist = (int *) malloc (ncols * (sizeof(int));
xlist = (double *) malloc (ncols * (sizeof(double));

ncand = 0;
for (i = 0; i < ncols; i++) {
    t = x[i] - floor (x[i]);      /* t is the fractional part of x[i]  */
    if (t >= 0.1 && t <= 0.9) {   /* x[i] is at least 0.1 from integer */
        candidatelist[ncand] = i;
        xlist[ncand++] = x[i];
    }
}

if (ncand == 0) {
    free (candidatelist);
    free (xlist);
    return -1;     
}

down_vals = (double *) malloc (ncand * sizeof(double));
up_vals = (double *) malloc (ncand * sizeof(double));

rval = QSopt_strongbranch (p, ncand, candidatelist, xlist, down_vals,
                           up_vals, 50, ObjBound);
if (rval) {
    fprintf (stderr, "QSopt_strongbranch failed, error code %d\n", rval);
} else {
    /* Select as a branching variable the candidate that maximizes the */
    /* the function 10*min + max, where min is the smaller of          */
    /* down_vals and up_vals, and max is the larger.                   */

    bestval = -QS_MAXDOUBLE;
    for (i = 0; i < ncand; i++) {
        if (down_vals[i] < up_vals[i]) {
            val = 10 * down_vals[i] + up_vals[i];
        } else {
            val = 10 * up_vals[i] + down_vals[i];
        }
        if (val > bestval) {
            bestval = val;
            branch = candidatelist[i];
        }
    }
}

free (candidatelist);
free (xlist);
free (down_vals);
free (up_vals);

return branch;