1. Home
  2. Docs
  3. Math blog
  4. Branching strategies
  5. Introduction

Introduction

Branch-and-bound is fundamentally a divide-and-conquer approach.

We select a variable and split its range into several parts. In doing so, we reduce the problem size as it is now divided into a few several smaller problems.

Therefore, the relaxation of each new sub-problem is tighter compared to the parent problem’s. This process also organically creates starting point variations for the primal heuristics.

A branching strategy is basically a set of rules on how to select a single variable to branch every time. This is an option that is very strongly correlated with performance. The trend of the correlation is often chaotic, hence hard to predict, but the coupling is often very strong.

Since there’s no known strategy that just works amazingly well all of the time, Octeract Engine will by default automatically decide what strategy to use for your math on runtime. It will also dynamically change the strategy depending on performance metrics.

The snag is that once a branch-and-bound tree has been created, it’s sometimes too late to change the strategy, even if it’s obvious it’s not working out.

For this reason, on top of the automatic dynamic strategy we provide precise control of branching behaviour.

Note that if you set a BRANCHING_STRATEGY to something other than automatic, you will also switch of the solver’s dynamic branching behaviour. That’s ok though – if you’re tweaking this it means something is not working out for you to begin with.

These strategies are:

  1. AUTOMATIC (default)
  2. MOST_VIOLATED_TERM
  3. HYBRID_INTEGER_LEAST_REDUCED_AXIS
  4. MAX_SEPARATION_DISTANCE
  5. STRONG_BRANCHING
  6. MOST_FRACTIONAL_VARIABLE
  7. MODIFIED_MOST_NONCONVEX_VARIABLE