 |
 |
 |
 |
Purpose |
 |
 |
Compute values used with strong-branching.
|
 |
Synopsis |
 |
 |
int QSopt_strongbranch (QSprob p, int ncand, int *candidatelist,
double *xlist, double *down_vals, double *up_vals, int iterations,
double objbound)
|
 |
Arguments |
 |
p |
 |
a handle to an initialized problem. |
ncand |
 |
the number of variables to be tested. |
candidatelist |
 |
a list of the indices of the variables to be tested; the array of values must have length at least ncand . |
xlist |
 |
a list of values to use in determining branches, the down-branch to be tested is x[candidatelist[i]] = floor(xlist[i]) and the up-branch to be tested is x[candidatelist[i]] ≤ ceil(xlist[i]) . The argument xlist can be NULL ; if it is not NULL then the array of values should have length at least ncand . |
down_vals |
 |
returns the objective function values obtained by the down branches; this field should point to an array of length at least ncand . |
up_vals |
 |
returns the objective function values obtained by the up branches; this field should point to an array of length at least ncand . |
iterations |
 |
the number of iterations (pivots) of the dual steepest-edge simplex algorithm to use in the tests. |
objbound |
 |
a bound on the objective function (can be QS_MAXDOUBLE [for a minimization problem] or -QS_MAXDOUBLE [for a maximization problem] if no bound is known). |
|
 |
Returns |
 |
 |
A zero value if the function terminated correctly, and a non-zero value if an error occurred.
|
 |
Description |
 |
 |
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 i th 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.
|
 |
Example |
 |
 |
/* 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;
|
 |
|
|