user_shall_we

user_shall_we_branch

int user_shall_we_branch(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)

Description:

There are two user-written functions invoked from select_candidates_u. The first one (user_shall_we_branch()) decides whether to branch at all, the second one (user_select_candidates()) chooses the branching objects. The argument lists of the two functions are the same, and if branching occurs (see discussion below) then the contents of *cand_num and *candidates will not change between the calls to the two functions.

The first of these two functions is invoked in each iteration after solving the LP relaxation and (possibly) generating cuts. Therefore, by the time it is called, some violated cuts might be known. Still, the user might decide to branch anyway. The second function is invoked only when branching is decided on.

Given (1) the number of known violated cuts that can be added to the problem when this function is invoked, (2) the constraints that are slack in the LP relaxation, (3) the slack cuts not in the matrix that could be branched on (more on this later), and (4) the solution to the current LP relaxation, the user must decide whether to branch or not. Branching can be done either on variables or slack cuts. A pool of slack cuts which has been removed from the problem and kept for possible branching is passed to the user. If any of these happen to actually be violated (it is up to the user to determine this), they can be passed back as branching candidate type VIOLATED_SLACK and will be added into the current relaxation. In this case, branching does not have to occur (the structure of the *candidates array is described below in user_select_candidates()).

This function has two outputs. The first output is *action which can take four values: USER__DO_BRANCH if the user wants to branch, USER__DO_NOT_BRANCH if he doesn't want to branch, USER__BRANCH_IF_MUST if he wants to branch only if there are no known violated cuts, or finally USER__BRANCH_IF_TAILOFF if he wants to branch in case tailing off is detected. The second output is the number of candidates and their description. In this function the only sensible “candidates” are VIOLATED_SLACKs.

There is no post processing, but in case branching is selected, the col_gen_before_branch() function is invoked before the branching would take place. If that function finds dual infeasible variables then (instead of branching) they are added to the LP relaxation and the problem is resolved. (Note that the behavior of the col_gen_before_branch() is governed by the colgen_strat[] TM parameters.)

Arguments:

void *user	IN	Pointer to the user-defined LP data structure.
double lpetol	IN	The $\epsilon$ tolerance of the LP solver.

int cutnum	IN	The number of violated cuts (known before invoking this function) that could be added to the problem (instead of branching).

int slacks_in_matrix_num	IN	Number of slack constraints in the matrix.
cut_data **slacks_in_matrix	IN	The description of the cuts corresponding to these constraints (see Section 6.3.2.1).

int slack_cut_num	IN	The number of slack cuts not in the matrix.
cut_data **slack_cuts	IN	Array of pointers to these cuts (see Section 6.3.2.1).
int varnum	IN	The number of variables in the current lp relaxation (the length of the following three arrays).
var_desc **vars	IN	Description of the variables in the relaxation.
double *x	IN	The corresponding solution values (in the optimal solution to the relaxation).
char *status	IN	The stati of the variables. There are five possible status values: NOT_FIXED, TEMP_FIXED_TO_UB, PERM_FIXED_TO_UB, TEMP_FIXED_TO_LB and PERM_FIXED_TO_LB.

int *cand_num	OUT	Pointer to the number of candidates returned (the length of *candidates).
candidate ***candidates	OUT	Pointer to the array of candidates generated (see description below).
int *action	OUT	What to do. Must be one of the four above described values unless the return code is USER_DEFAULT.

Return values:

USER_ERROR	Error. DEFAULT is used.
USER_SUCCESS	The user filled out action (and possibly cand_num and *candidates).
USER_DEFAULT	Action taken is controlled by the parameter shall_we_branch_default, which is initially USER__BRANCH_IF_MUST unless overridden by the user.

Notes:

The user has to allocate the pointer array for the candidates and place the pointer for the array into ***candidates (if candidates are returned).
Candidates of type VIOLATED_SLACK are always added to the LP relaxation regardless of what action is chosen and whether branching will be carried out or not.
Also note that the user can change his mind in user_select_candidates() and not branch after all, even if she chose to branch in this function. A possible scenario: cut_num is zero when this function is invoked and the user asks for USER__BRANCH_IF_MUST without checking the slack constraints and slack cuts. Afterward no columns are generated (no dual infeasible variables found) and thus SYMPHONY decides branching is called for and invokes user_select_candidates(). However, in that function the user checks the slack cuts, finds that some are violated, cancels the branching request and adds the violated cuts to the relaxation instead.

Warning:

The cuts the user unpacks and wants to be added to the problem (either because they are of type VIOLATED_SLACK or type CANDIDATE_CUT_NOT_IN_MATRIX) will be deleted from the list of slack cuts after this routine returns. Therefore the same warning applies here as in the function user_unpack_cuts().

Wrapper invoked from:
select_branching_object().