BoFire Documentation

Greedy pruning is a feasibility-first optimization technique used to satisfy NChooseK constraints (cardinality constraints) and semi-continuity constraints (e.g., allow_zero = True with a lower bound lb).

Unlike the standard BONSAI algorithm which prioritizes minimizing acquisition loss, this implementation prioritizes finding a feasible candidate that exactly satisfies the constraints. It works by starting with an acquisition function maximization on a convex relaxation and then iteratively applying greedy actions to resolve violations.

The Pruning Process

1. Step 0: Initial Optimization: Perform acquisition function maximization on the convex relaxation of the problem.
2. Step 1: Greedy Pruning Loop: While constraints (like max_count or semi-continuity) are violated:
   • Evaluate potential actions (e.g., zero(x_i) or active(x_i)).
   • Project candidates onto the mixture/equality constraints.
   • Select the action with the highest acquisition value (smallest acquisition reduction).
   • The min_count guard prevents actions that would violate the minimum required active features.
3. Step 2: Termination: The loop terminates when all features are non-fractional and the active count a satisfies min_count <= a <= max_count.
4. Step 3: Local Reoptimization (Optional): If final_local_reopt is enabled, a final local optimization is run with the pruned features fixed to zero to refine the remaining active values.

Branch-and-Bound (B&B) is proposed as the most advanced search strategy for pruning, moving beyond the fixed-width exploration of beam search to a priority-queue-driven tree search.

Key Components:

• Branching: Uses the same expand(state) function as beam search to generate successors.
• Bounding: Uses a function L(state) to provide a lower bound on the AF reduction of any feasible descendant. Subtrees where accumulated + L(state) >= incumbent are pruned.
• Incumbent: The current best feasible solution found. The greedy algorithm is intended to serve as the initial incumbent and a primal heuristic at every interior node to provide high-quality bounds early.
• Node Budget: A hyperparameter to limit search time. If the budget is exceeded, the algorithm returns the current best incumbent along with the gap (incumbent - best_open_bound) as a quality metric.

Relationship to existing features: B&B is not a replacement but an evolution. It reuses the greedy algorithm as a heuristic, the action machinery (eligibility, guards, variant builders) for branching, and the existing greedy logic as a runtime fallback.

A planned extension to the greedy pruning mechanism is the introduction of swap(j, k) actions. Currently, the greedy pruning algorithm can only change the cardinality of the support set (adding or removing features). Once a feature is committed as active, it remains active unless a max_count violation occurs.

The Swap Action: An atomic move defined as swap(j, k) = zero(j) + activate(k), where j is in the active_set and k is in the zero_set, and both belong to at least one shared NChooseK group. This allows rebalancing the support set without changing the total cardinality.

Use Case: This is particularly useful for mixture + NChooseK problems with tight min_count = max_count constraints. In these cases, the current greedy approach might lock in a suboptimal support set because it cannot move mass from one feature to another without temporarily violating cardinality constraints. A swap action bypasses this by performing the zeroing and activation in a single step.

NChooseK (cardinality) constraints require that a specific number of features (between min_count and max_count) take strictly positive values. Because these constraints are non-convex and turn optimization into an expensive mixed-integer program, BoFire uses a Greedy Pruning post-processing step instead of encoding them directly in the optimizer.

The Mental Model

Instead of forcing the optimizer to respect cardinality, BoFire follows a two-step process:

1. Convex Relaxation: Optimize the acquisition function on a relaxed version of the problem where the NChooseK and semi-continuity constraints are ignored. This results in a "dense candidate" x* where features might be fractional (violating semi-continuity) or too numerous (violating max_count).
2. Greedy Pruning: Iteratively apply "actions" to the dense candidate to resolve violations. At each step, the algorithm selects the action that results in the smallest loss to the acquisition value.

Feature States during Pruning

After the initial optimization, every feature x_j is in one of three states:

• zero: x*_j = 0. No action needed.
• fractional: x*_j ∈ (0, lb_j). Violates semi-continuity; must be either zeroed or snapped to [lb_j, ub_j].
• cleanly active: x*_j ∈ [lb_j, ub_j]. No semi-continuity issue, but may still need to be zeroed to satisfy max_count.

Supported Feature Types

• Semi-continuous features: Defined by having allow_zero=True and lb_j > 0. The feasible set is the disconnected union {0} ∪ [lb_j, ub_j]. The algorithm treats these as a special case of a one-feature NChooseK constraint.
• Linear constraints: The algorithm supports linear equality and inequality constraints that overlap the NChooseK feature set. Note: Nonlinear or interpoint constraints overlapping the NChooseK set are not supported and will trigger a fallback to standard nonlinear-constrained optimization.

BoFire uses specific terminology for the optimization lifecycle:

• Candidates: Suggested parameter sets from the domain.
• Experiments: Candidates that have been evaluated to obtain actual output values.

To initialize a loop, you can sample initial candidates from the domain:

candidates = domain.inputs.sample(10, seed=13)

To convert Candidates into Experiments, apply your evaluation function (e.g., a physical experiment or a simulation) to the candidate rows and add the results as a new column:

# Assuming 'himmelblau' is your evaluation function
experimental_output = candidates.apply(
    lambda row: himmelblau(row["x1"], row["x2"]), axis=1
)

experiments = candidates.copy()
experiments["y"] = experimental_output

candidates = domain.inputs.sample(10, seed=13)

# Evaluate candidates to create experiments
experimental_output = candidates.apply(
    lambda row: himmelblau(row["x1"], row["x2"]), axis=1
)

experiments = candidates.copy()
experiments["y"] = experimental_output

The greedy pruning loop resolves semi-continuity and cardinality violations through three types of actions. At each iteration, the algorithm evaluates variants for each available action and commits the one with the highest acquisition value.

Available Actions

1. Zero action zero(j): Pins x_j = 0 and re-establishes feasibility. This decrements the active count a. Available for any feature that is currently active (fractional or cleanly active).
2. Active action active(j): Only available for fractional features. Sets the bounds of j to [lb_j, ub_j] and re-establishes feasibility. This resolves semi-continuity without changing the active count a.
3. Activate action activate(j): Only available for zero features when an "under-budget" violation occurs (a < min_count). It snaps x_j into a positive band ([lb_j, ub_j] for semi-continuous, or [ε, ub_j] otherwise). This increments the active count a.

Termination and the min_count Guard

The loop terminates when no features are fractional AND the active count a satisfies min_count ≤ a ≤ max_count.

To prevent the greedy rule from dropping the active count below the required minimum, a min_count guard is applied. This guard filters the action set: a zero(j) action is removed if it would result in a - 1 < min_count. (If none_also_valid = True, the guard allows a = 0 as a special case).

If the filtered action set becomes empty (e.g., because all remaining variants are infeasible), the algorithm raises an error rather than returning an infeasible candidate.