BCP Modifications

If you are using BCP for Branch-and-Cut exclusively, some modifications of the code might yield big performance improvement. However, some of these modifications assume that the branching rule is the standard "branch on a variable" scheme (the default in BCP) and might not work for an arbitrary branching rule. The following modifications are described below:

The instructions below assume that you are working with the SHELL example. The path to the main directory of this example will be denoted by SHELL on this page. Adapting to your own situation should be straightforward.

Using Cplex and Cgl Cut generators

Some of the cut generators in Cgl require that an optimal simplex basis is available. For Cplex, any change in the current formulation invalidates the optimal solution and basis of the last solved Lp. This implies that reoptimization of the current Lp should be performed before generating cuts if the optimal basis is no longer available.

Modification: In BCP_lp_main_loop.cpp, around line 185: Add
|| (!p.lp_solver->basisIsAvailable()) in the condition to get:

if (fix_vars_while_external_processes_working) {
    if ((BCP_lp_fix_vars(p) || (!p.lp_solver->basisIsAvailable()))) {

No branching on a Single Child

The default branching scheme in BCP, based on strong branching, is rather primitive. It favors branching resulting in the minimum number of non-fathomable children. When this number is 0, the node is fathomed and the rule makes sense. However, when branching on a variable by changing its bounds (the default branching rule of BCP), if the actual number of non-fathomable children is 1, it is better to adjust the bounds on the corresponding variable xi according to its bounds in the unique child and continue looking for another branching variable than to branch on xi.

Note that this modification might prevent BCP to do a true Best-Bound node selection, even if BCP_MaxPresolveIter and BCP_IneffectiveBeforeDelete are both set to infinity. It is indeed possible that the chosen candidate is "strong-branched on" before some of the variable bounds are changed. The Lp relaxation value of the children might thus be larger than the value obtained during the strong branching solve of a candidate.

Modifications: Then If NO_BRANCH_ON_SINGLE is not set in the USER_DEFINES line, then the code behaves like the original, except that the choice of the branching candidate is slightly different. To get the original code, remove BB_lp::compare_branching_candidates().

No Deletion of Constraints Useful in Children

The default loop at a node updates the row effectiveness, then does strong branching to pick a variable to branch on, and then removes ineffective rows from the formulation. This sometimes removes an inequality ineffective in the father but effective in the children. To make sure that all inequalities deemed effective in the children are kept, do the following.

Modifications: Then If USE_CHILDREN_EFFECTIV is not set in the USER_DEFINES line, then the code behaves like the original.

Fake Objective Values

During strong branching, Lp are solved and, depending on their return code, their objective value is adjusted. If no generation of variables occur, then if the iteration limit is reached during the dual simplex pivot for reoptimizing, it is possible to use the current Lp value as a lower bound on the optimal value.

Modification:
Last modified: 6/28/06

Back to main page