Branch-and-Bound Tree Search

For many MIPs, only running heuristics and applying cuts is insufficient to solve the problem to proven optimality. Therefore, the Xpress Optimizer will have to enter the branch-and-bound search. This process recursively selects a single undecided variable and splits the current problem into two easier subproblems by forcing the variable either up or down.

The most important aspect of this search is the selection of the branching variable. Good choices here can lead to solution times orders of magnitude faster than bad choices. If the focus is on finding good solutions quickly, then the order in which the two subproblems are searched is also important.

The Xpress Optimizer uses a wide variety of information in order to guide the choice of a branching variable. This includes the outcomes of past branching choices, some strong branching, and some quick estimates based on the local subproblem.

By default, the Optimizer will use pseudo costs as its main criteria for selecting the branch entity. This is an estimated cost of moving a variable either up or down by a unit amount. This cost is multiplied by the distance a variable has to move to reach the next integer value, which provides an estimated change in the objective function. Strong branching is used to initialize these pseudo costs.

The basic procedure for selecting a branching variable, and the controls that affect each step are as follows:

1. Pre-filter the set of candidate variables using very cheap estimates.
   SBSELECT: determine filter size
2. Evaluate and rank selected candidates.
   SBESTIMATE: local ranking function
3. Initialize pseudo costs using strong branching
   SBBEST: Number of variables to strong branch on.
   SBITERLIMIT: LP iteration limit for strong branching.
4. Select the best candidates using a combination of pseudo costs and the local ranking function.

The overall amount of effort put into this process can be adjusted using the SBEFFORT control. The default value is 1.0, and a value of 2.0 tells the Xpress Optimizer to put in twice the default effort.

Strong branching can be turned off completely by setting either SBBEST=0 or SBITERLIMIT=0. This also disables the use of pseudo costs, which causes step 3 above to be skipped. In that case, only the local ranking function determined by SBESTIMATE will be used.

There are six choices for the SBESTIMATE local ranking function:

1

Transformed distance measure (expensive)

2

Simplex tableau based (expensive)

3

Use probing/logical implications to create cost estimates.

4

Count probing/logical implications.

5

Simple cost estimates (quick)

6

Row influence measure (quick)

If pseudo costs are not working well, it is recommended to turn off strong branching (set SBBEST=0) and try at least SBESTIMATE = 1, 2 or 3. It is usually sufficient to let the Xpress Optimizer complete a couple of dives in order to get a good idea of which ranking function works best. Look e.g. for the function that raises the Best Bound the most after a fixed number of nodes.

If the focus is on finding good solutions quickly, then setting SBBEST=0 and SBESTIMATE=5 or 6 will provide the quickest dives.

The other aspect of the branch-and-bound search is how to select the next node to work with. This choice can have a considerable impact on the time when improving solutions are found. The time to proven optimality, however, is often not affected much by node selection. The Xpress Optimizer performs the search in dives, whereby it picks a single active node from the node pool and then performs a dive on it. In a dive it creates two new subproblems by branching on a variable, picks one of the subproblems and repeats by branching on another variable. This process continues until it reaches a subproblem without any fractional variables to branch on, or for which no improved solutions exist. The selection of an active node is also referred to as a global backtrack. During a dive, the Xpress Optimizer might also perform local backtracks, where it switches between sibling nodes.

The main controls for selecting the next active node to work on is BACKTRACK. The default value of 3 (best bound) will work best on almost all problems. The related control BACKTRACKTIE will be used to break ties if two nodes have the same ranking according to BACKTRACK. Possible values range from 2 to 12 and it is mostly a matter of experimentation to find which works best.

The control BRANCHCHOICE can be used to select which of the two new child subproblems is explored first.

Finally, it is possible to use directives to directly guide the Xpress Optimizer when selecting a branching variable or when deciding on the branch to follow during a dive. It is possibly to give each variable a priority value such that a variable with the lowest priority value is always branched on before one with a higher value. This can be very useful if you already know what the most important decision variables in your problem are. Please refer to the Xpress Optimizer Reference Manual for more information about the use of directives.

Another aspect of the tree search are restarts. These can already be triggered during the initial root cutting but may also happen in the tree. Restarts are triggered when the solver does not make enough progress or new solutions promise a faster solve when performing a full root presolve again. In this case, the current tree will be reset to the root, a full presolve will be performed again, and some internal settings may change:

    1945  56503433.22  55132652.45     10   1550     80    2.43%      31    190
    2049  56503433.22  55132652.45     10   1724     51    2.43%     321    193
Resetting tree to root.

Performing root presolve...

Reduced problem has:    3503 rows   15977 columns    118643 elements
Presolve dropped   :       0 rows       0 columns       185 elements
Will try to keep branch and bound tree memory usage below 9.0GB
Starting concurrent solve with dual, primal and barrier (6 threads)

                           Concurrent-Solve, 195s
...

Starting root cutting & heuristics

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
R         56488350.97  55132652.45     11                  2.40%       0    203
...
M         56107415.55  55132652.45     19                  1.74%       0    224

Cuts in the matrix         : 25
Cut elements in the matrix : 75552

Starting tree search.
Deterministic mode with up to 8 running threads and up to 16 tasks.
Heap usage: 39MB (peak 517MB, 1295KB system)
Heap usage: 39MB (peak 517MB, 1295KB system)
B&B tree size: 100k total

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
    2084  56107415.55  55132652.45     19      2      1    1.74%     682    231

In this case, as can be observed from the log, the restart managed to drop more non-zero elements. More importantly, the additional cutting rounds reduced the gap significantly. On the other hand, if this was not the case, restarting can be expensive since the previous progress is mostly thrown away, so if the restart did not manage to reduce the problem further or accelerate the progress of the tree search, it might be worthwhile to try disabling restarts by setting MIPRESTART=0.

Branch-and-Bound Controls Summary

SBBEST, SBITERLIMIT

Limit on number of strong branches and strong branch LP iterations.

SBESTIMATE

Local ranking function for selecting branching variables.

SBEFFORT

Multiplier on the effort spent on selecting a branching variable.

BACKTRACK, BACKTRACKTIE

How to select the next active node to perform a dive on.

BRANCHCHOICE

How to select the child problem to continue a dive on.

MIPRESTART

Whether restarts are allowed.