user_compare_candidates

[cf]user_compare_candidates
int user_compare_candidates(void *user, branch_obj *can1, branch_obj *can2,
                            double ub, double granularity, 
                            int *which_is_better)

Description:

By the time this function is invoked, the children of the current search tree node corresponding to each branching candidate have been pre-solved, i.e., the objval, termcode, iterd, and feasible fields of the can1 and can2 structures are filled out. Note that if the termination code for a child is LP_D_UNBOUNDED or LP_D_OBJLIM, i.e., the dual problem is unbounded or the objective limit is reached, then the objective value of that child is set to MAXDOUBLE / 2. Similarly, if the termination code is one of LP_D_ITLIM (iteration limit reached), LP_D_INFEASIBLE (dual infeasible) or LP_ABANDONED (because of numerical difficulties) then the objective value of that child is set to that of the parent's.

Based on this information the user must choose which candidate he considers better and whether to branch on this better one immediately without checking the remaining candidates. As such, there are four possible answers: FIRST_CANDIDATE_BETTER, SECOND_CANDIDATE_BETTER, FIRST_CANDIDATE_BETTER_AND_BRANCH_ON_IT and SECOND_CANDIDATE_BETTER_AND_BRANCH_ON_IT. An answer ending with _AND_BRANCH_ON_IT indicates that the user wants to terminate the strong branching process and select that particular candidate for branching.

There are several default options. In each of them, objective values of the pre-solved LP relaxations are compared.

Arguments:

void *user IN Pointer to the user-defined LP data structure.
     
branch_obj *can1 IN One of the candidates to be compared.
branch_obj *can2 IN The other candidate to be compared.
double ub IN The current best upper bound.
double granularity IN Defined tolerance
int *which_is_better OUT The user's choice. See the description above.

Return values:

USER_ERROR Error. DEFAULT is used.
USER_SUCCESS User filled out *which_is_better.
USER_DEFAULT Regulated by the compare_candidates_default parameter, initially set to LOWEST_LOW_OBJ unless overridden by the user.
BIGGEST_DIFFERENCE_OBJ Prefer the candidate with the biggest difference between highest and lowest objective function values.
LOWEST_LOW_OBJ Prefer the candidate with the lowest minimum objective function value. The minimum is taken over the objective function values of all the children.
HIGHEST_LOW_OBJ Prefer the candidate with the highest minimum objective function value.
LOWEST_HIGH_OBJ Prefer the candidate with the lowest maximum objective function value.
HIGHEST_HIGH_OBJ Prefer the candidate with the highest maximum objective function value .
LOWEST_LOW_FRAC Prefer the candidate with the lowest minimum number of fractional variables. The minimum is taken over the number of fractional variables in all the children. Fractional branching options are only available if the fractional branching compile-time option is set in the makefile.
HIGHEST_LOW_FRAC Prefer the candidate with the highest minimum number of fractional variables.
LOWEST_HIGH_FRAC Prefer the candidate with the lowest maximum number of fractional variables.
HIGHEST_HIGH_FRAC Prefer the candidate with the highest maximum number of fractional variables.

Wrapper invoked from:
select_branching_object() after the LP relaxations of the children have been pre-solved.



Ted Ralphs
2010-03-24