user_select_candidates

int user_select_candidates(void *user, double lpetol, int cutnum, 
                           int slacks_in_matrix_num,
                           cut_data **slacks_in_matrix,
                           int slack_cut_num, cut_data **slack_cuts,
                           int varnum, var_desc **vars, double *x, 
                           char *status, int *cand_num, 
                           branch_obj ***candidates, int *action,
                           int bc_level)

Description:

The purpose of this function is to generate branching candidates. Note that *action from user_shall_we_branch() is passed on to this function (but its value can be changed here, see notes at the previous function), as well as the candidates in **candidates and their number in *cand_num if there were any.

Violated cuts found among the slack cuts (not in the matrix) can be added to the candidate list. These violated cuts will be added to the LP relaxation regardless of the value of *action.

The branch_obj structure contains fields similar to the cut_data data structure. Branching is accomplished by imposing inequalities which divide the current subproblem while cutting off the corresponding fractional solution. Branching on cuts and variables is treated symmetrically and branching on a variable can be thought of as imposing a constraint with a single unit entry in the appropriate column. Following is a list of the fields of the branch_obj data structure which must be set by the user.

char type

Can take five values:

CANDIDATE_VARIABLE

The object is a variable.

CANDIDATE_CUT_IN_MATRIX

The object is a cut (it must be slack) which is in the current formulation.

CANDIDATE_CUT_NOT_IN_MATRIX

The object is a cut (it must be slack) which has been deleted from the formulation and is listed among the slack cuts.

VIOLATED_SLACK

The object is not offered as a candidate for branching, but rather it is selected because it was among the slack cuts but became violated again.

SLACK_TO_BE_DISCARDED

The object is not selected as a candidate for branching rather it is selected because it is a slack cut which should be discarded even from the list of slack cuts.

int position

The position of the object in the appropriate array (which is one of vars, slacks_in_matrix, or slack_cuts.

waiting_row *row

Used only if the type is CANDIDATE_CUT_NOT_IN_MATRIX or VIOLATED_SLACK. In these cases this field holds the row extension corresponding to the cut. This structure can be filled out easily using a call to user_unpack_cuts().

int child_num

The number of children of this branching object.

char *sense, double *rhs, double *range, int *branch

The description of the children. These arrays determine the sense, rhs, etc. for the cut to be imposed in each of the children. These are defined and used exactly as in the cut_data data structure. Note: If a limit is defined on the number of children by defining the MAX_CHILDREN_NUM macro to be a number (it is pre-defined to be 4 as a default), then these arrays will be statically defined to be the correct length and don't have to be allocated. This option is highly recommended. Otherwise, the user must allocate them to be of length child_num.

double lhs

The activity level for the row (for branching cuts). This field is purely for the user's convenience. SYMPHONY doesn't use it so it need not be filled out.

double *objval, int *termcode, int *iterd, int *feasible

The objective values, termination codes, number of iterations and feasibility stati of the children after pre-solving them. These are all filed out by SYMPHONY during strong branching. The user may access them in user_compare_candidates() (see below).

There are three default options (see below), each chooses a few variables (the number is determined by the strong branching parameters.

Arguments:

Same as for user_shall_we_branch(), except that *action must be either USER__DO_BRANCH or USER__DO_NOT_BRANCH, and if branching is asked for, there must be a real candidate in the candidate list (not only VIOLATED_SLACKs and SLACK_TO_BE_DISCARDEDs). Also, the argument bc_level is the level in the tree. This could be used in deciding how many strong branching candidates to use.

Return values:

USER_ERROR	Error. DEFAULT is used.
USER_SUCCESS	User generated branching candidates.
USER_DEFAULT	Regulated by the select_candidates_default parameter, but set to USER__CLOSE_TO_HALF unless overridden by the user.
USER__CLOSE_TO_HALF	Choose variables with values closest to half.
USER__CLOSE_TO_HALF_AND_EXPENSIVE	Choose variables with values close to half and with high objective function coefficients.
USER__CLOSE_TO_ONE_AND_CHEAP	Choose variables with values close to one and with low objective function coefficients.

Wrapper invoked from:

select_branching_object().

Notes:

See the notes at user_shall_we_branch().