The routine CPXstrongbranch computes information for selecting a branching variable in an integer-programming branch & cut search.

To describe this routine, let's assume that an LP has been solved and that the optimal solution is resident. Let goodlist[] be the list of variable indices for this problem and goodlen be the length of that list. Then goodlist[] gives rise to 2*goodlen different LPs in which each of the listed variables in turn is fixed to the greatest integer value less than or equal to its value in the current optimal solution, and then each variable is fixed to the least integer value greater than or equal to its value in the current optimal solution. CPXstrongbranch performs at most itlim dual steepest-edge iterations on each of these 2*goodlen LPs, starting from the current optimal solution of the base LP. The values that these iterations yield are placed in the arrays downpen[] for the downward fix and uppen[] for the upward fix. Setting CPX_PARAM_DGRADIENT to 2 may give more informative values for the arguments downpen[] and uppen[] for a given number of iterations itlim.

For a given j = goodlist[i], upratio[i] has the following meaning. Let xj be the name of the basic variable with index j, and suppose that xj is fixed to some value t' > t. Then in a subsequent call to CPXdualopt, the leaving variable in the first iteration of this call is uniquely determined. It must be xj.

There are then two possibilities. Either an entering variable is determined, or it is concluded (in the first iteration) that the changed model is dual unbounded (primal infeasible). In the latter case, upratio[i] is set equal to a large positive value (this number is system dependent, but is usually 1.0E+75). In the former case, where r is the value of the objective function after this one iteration, upratio[i] is determined by |r| = (t' - t) * upratio[i].

A user might use other routines of the ILOG CPLEX Callable Library directly to build a function that computes the same values as CPXstrongbranch. However, CPXstrongbranch should be faster because it takes advantage of direct access to internal ILOG CPLEX data structures.