Branching

Strategy for Exploring the Search Space

In Constraint Programming, finding a solution involves navigating a vast search space of potential variable assignments. When logical propagation (inference) alone is insufficient to reduce all variable domains to a single value, the solver must actively search for a solution. This process is known as branching.

Branching effectively decomposes the problem into smaller sub-problems. It constructs a search tree where each node represents a decision—typically assigning a specific value to a variable or splitting a variable’s domain.

The Branching Process

When the solver reaches a state where no further constraints can be propagated but the solution is not yet fully determined, it executes a branching step:

  • Decision: The solver tentatively enforces a new constraint (e.g., assigning variable x=5).
  • Propagation: It runs the propagation engine again to see if this decision forces other variables to take specific values or leads to a conflict.
  • Backtracking: If the decision leads to a conflict (a “dead end” where no solution is possible), the solver reverses the decision and explores the alternative branch (e.g., x!=5).

Strategic Importance

The efficiency of the solver is heavily dependent on the branching strategy. A naive strategy may result in an exhaustive search that is computationally tough. Conversely, an intelligent strategy acts as a heuristic guide, prioritizing decisions that are likely to fail quickly (pruning the tree early) or even lead directly to a solution.

Once a variable is selected, this heuristic determines which value from its domain to attempt first.

  • Common Strategies: Attempting the minimum value (min), the maximum value (max), or splitting the domain in half (split).

Configuration in Qaekwy

In Qaekwy, branching strategies are not an afterthought; they are configured explicitly when you define your variables. This allows you to tailor the search strategy to the specific structure of your data.

You configure branching using three main parameters (variables and array):

  • branch_val: Determines which value from a domain is attempted first (Value Selection).
  • branch_var (arrays only): Determines which variable within an array is chosen next (Variable Selection).
  • branch_order: Determines priorities when a group of variables is processed relative to others.

Configuring Variables (Value Selection)

When defining a single integer_variable, you define Value Selection: once a variable is chosen, which value do we try first? This is controlled by the branch_val argument using the qaekwy.BranchIntegerVal enum. Each variable type has its own set of branchers.

import qaekwy as qw

m = qw.Model()

# A variable where we suspect the solution is likely a small number
x = m.integer_variable(
    name="x",
    domain=(1, 100),
    branch_val=qw.BranchIntegerVal.VAL_MIN
)

The BranchVal class represents strategies for selecting brancher values during the search process. These strategies determine how values for variables are chosen when branching decisions are made.

The following strategies are available:

  • VAL_RND: Select a value randomly.
  • VAL_MIN: Select the minimum value.
  • VAL_MED: Select the median value.
  • VAL_MAX: Select the maximum value.
  • VALUES_MIN: Select the value with the smallest domain.
  • VALUES_MAX: Select the value with the largest domain.
  • VAL_RANGE_MIN: Select the value with the smallest range.
  • VAL_RANGE_MAX: Select the value with the largest range.
  • VAL_SPLIT_MIN: Select a value by splitting the domain into two halves and choosing from the smaller half.
  • VAL_SPLIT_MAX: Select a value by splitting the domain into two halves and choosing from the larger half.

Configuring Arrays (Variable Selection)

When working with an integer_array, the most critical decision is Variable Selection: determining which index in the array the solver should try to fix next. This is controlled by the branch_var argument using the BranchIntegerVar enum.

import qaekwy as qw

m = qw.Model()

# Create a grid where the solver always picks the variable 
# with the smallest remaining domain.
grid = m.integer_array(
    name="grid",
    length=81,
    domain=(1, 9),
    branch_var=qw.BranchIntegerVar.VAR_SIZE_MIN
)

The BranchVar class represents strategies for selecting brancher variables during the search process. These strategies determine which variables are chosen for branching decisions.

The available strategies are as follows:

  • VAR_NONE: No variable is selected (termination strategy).
  • VAR_RND: Select a variable randomly.
  • VAR_SIZE_MIN: Select the variable with the smallest domain.
  • VAR_SIZE_MAX: Select the variable with the largest domain.
  • VAR_REGRET_MIN_MIN: Select the variable with the smallest minimum regret.
  • VAR_REGRET_MIN_MAX: Select the variable with the largest minimum regret.
  • VAR_DEGREE_MIN: Select the variable with the minimum degree.
  • VAR_DEGREE_MAX: Select the variable with the maximum degree.
  • VAR_MIN_MIN: Select the variable with the smallest minimum value.
  • VAR_MIN_MAX: Select the variable with the largest minimum value.
  • VAR_MAX_MIN: Select the variable with the smallest maximum value.
  • VAR_MAX_MAX: Select the variable with the largest maximum value.
  • VAR_DEGREE_SIZE_MIN: Select the variable with the smallest degree and smallest domain.
  • VAR_DEGREE_SIZE_MAX: Select the variable with the largest degree and largest domain.

Controlling Search Priority (branch_order)

The branch_order parameter is an integer available in both integer_variable and integer_array. It acts as a sorting key for the solver.

  • Lower numbers are processed first.
  • Default: -1 (Standard priority).

You should assign a lower branch_order to important decision variables to ensure the solver focuses on them first.

# The solver will try to fix 'primary_inputs' before touching 'derived_stats'
primary_inputs = m.integer_array("primary_inputs", ..., branch_order=1)
derived_stats  = m.integer_array("derived_stats", ..., branch_order=2)

Example

Here is how you might combine these strategies in a scheduling problem. We prioritize the schedule assignments (branch_order=1) using a VAR_SIZE_MIN and try to assign the earliest possible slots first (VAL_MIN inferred or set if dealing with scalars).

import qaekwy as qw

m = qw.Model()

# 1. The main schedule: Solve this FIRST.
# Use 'VAR_SIZE_MIN' to target the most constrained slots (bottlenecks).
schedule = m.integer_array(
    name="schedule",
    length=10,
    domain=(1, 24),
    branch_var=qw.BranchIntegerVar.VAR_SIZE_MIN,
    branch_order=1
)

# 2. The cost variable: Solve this SECOND.
# If we branch on this, try to split the domain to narrow down the cost range quickly.
total_cost = m.integer_variable(
    name="total_cost",
    domain=(0, 1000),
    branch_val=qw.BranchIntegerVal.VAL_SPLIT_MIN,
    branch_order=2
)

# ...

m.solve_one()