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_SLACK`s.

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 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.

- The user has to allocate the pointer array for the
candidates and place the pointer for the array into
**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()`.

2007-06-12