Callbacks

What are Callbacks?

This section provides an overview of the callback system in BendersLib. Callbacks are functions executed at specific events during the Benders decomposition, allowing for monitoring and intervention.

The primary motivation for callbacks in BendersLib is to allow users to “hook into” the algorithm, making it a flexible and extensible framework. By providing hooks into the solver’s lifecycle, callbacks enable monitoring progress, extracting intermediate data, or customizing behavior without altering the core library. They are the primary mechanism for extending the Benders decomposition with advanced strategies like custom cut generation, problem-specific heuristics, and other acceleration techniques, which can significantly improve performance, stability, and convergence. See Enhancements for advanced acceleration techniques supported by BendersLib.

The callback system in BendersLib operates on an event-driven basis. The BendersSolver emits events at various stages of the decomposition process. When an event is emitted, the solver checks for any registered callbacks corresponding to that event and executes them sequentially. A callback can also terminate the Benders process prematurely by returning the constant TERMINATE; If a callback returns PROCEED or does not return anything, the Benders process continues as normal. Any TERMINATE signal is executed immediately after the current event completes, meaning that the subsequent steps in the current iteration will not be executed, with the status of the Benders process set to TERMINATED.

Timeline of Callback Triggers

The following pseudocode (solve()) illustrates the main stages of the Benders decomposition algorithm and the specific points at which each callback event is triggered.

// solve() method of BendersSolver is called

trigger on_master_build()
trigger on_sub_build()
trigger on_benders_start()

iteration counter = 0

while not converged:
    increment iteration counter
    trigger on_iteration_start()

    trigger on_before_master_solve()
    solve master problem
    trigger on_after_master_solve()

    if master problem is optimal:
        save current_comp_vals
        trigger on_before_sub_solve()
        solve subproblem with current_comp_vals
        trigger on_after_sub_solve()

        if subproblem is optimal:
            if new lower bound is found:
                trigger on_new_lower_bound()
            if new upper bound is found:
                // new best-known solution found
                trigger on_new_upper_bound()

            if converged:
                break

            generate optimality cut
            save current_opti_cuts
            trigger on_opti_cut_generated()
            add current_opti_cuts to master problem
            trigger on_opti_cut_added()

        else if subproblem is infeasible:
            if converged:
                break

            generate feasibility cut
            save current_feas_cuts
            trigger on_feas_cut_generated()
            add current_feas_cuts cut to master problem
            trigger on_feas_cut_added()

    else:
        // master problem is infeasible or unbounded
        break

    trigger on_iteration_end()

trigger on_benders_end()

Timeline of Branch-and-check Callback Triggers

The following pseudocode (bnc_solve()) illustrates the main stages of the branch-and-check method and the specific points at which each callback event is triggered. Note that the callback events on_before_master_solve() and on_after_master_solve() are not triggered in the Branch-and-check method.

// bnc_solve() method of BendersSolver is called

trigger on_master_build()
trigger on_sub_build()
trigger on_benders_start()

// Master problem is solved using a MIP solver with a callback
// The following events are triggered within the solver's callback at each node

if node is integer and feasible:
    trigger on_iteration_start()
    save current_comp_vals
    trigger on_before_sub_solve()
    solve subproblem with current_comp_vals
    trigger on_after_sub_solve()

    if subproblem is optimal:
        if new lower bound is found:
            trigger on_new_lower_bound()
        if new upper bound is found:
            // new best-known solution found
            trigger on_new_upper_bound()

        generate optimality cut
        save current_opti_cuts
        trigger on_opti_cut_generated()
        add current_opti_cuts to master problem at the current node
        trigger on_opti_cut_added()

    else if subproblem is infeasible:
        generate feasibility cut
        save current_feas_cuts
        trigger on_feas_cut_generated()
        add current_feas_cuts cut to master problem at the current node
        trigger on_feas_cut_added()

    trigger on_iteration_end()

trigger on_benders_end()

How to Use Callbacks?

There are two ways to create callbacks: as a class inheriting from CallbackBase or as a standalone function. Both approaches receive a BendersContext object, which provides access to the master problem, subproblem, and the current state of the decomposition. The class-based callbacks are ideal for complex logic that requires maintaining state between events. By defining a class, you can use instance attributes to store information across different callback calls. The function-based callbacks is a simpler, more direct way to respond to events when you don not need to maintain state. Each callback function is independent.

The following example demonstrates how to define and register both types of callbacks.

Defining and registering callbacks in BendersLib

# Class-based callback
class MyCallback(CallbackBase):
    some_persistent_data = ">>>>>>>> Hi there! >>>>>>>>>"

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")
        print(self.some_persistent_data)

# Function-based callback
def on_iteration_end(context: BendersContext):
    print(f"Starting iteration: {context.state.n_iter} ...")

    if context.state.n_iter == 1:
        print("Reached maximum iterations, terminating...")
        return CST.TERMINATE

master_model, complicating_vars = make_master_problem()
sub_model = make_sub_problem()

benders = ClassicalBenders.from_models(
    master_model, Gurobi,
    sub_model, Gurobi,
    complicating_vars=complicating_vars
)

# Register the callback
benders.register(MyCallback)
benders.register(on_iteration_end)

benders.solve()

Example

More examples of callbacks can be found in the Expert Examples.

Registering Multiple Callbacks

BendersLib supports registering multiple callbacks for the same event. When multiple callbacks are registered for a single event, they are executed sequentially in the order they were registered in that event. This allows for modular design, where different callbacks can handle different aspects of the same event without interfering with each other. For example, one callback could be responsible for logging the progress of the algorithm, while another could be responsible for implementing a custom stopping criterion.

Warning

Use caution when registering multiple callbacks, especially for the same event, as they may interact unexpectedly, particularly if they modify the same attributes in the BendersContext.

Attributes & Methods

The class CallbackBase is the abstract base class for creating CustomCallback. It provides a set of methods that are triggered at specific events during the Benders decomposition process. Each callback method has a BendersContext object, which contains the attributes listed below, providing access to the current state of the solver. During the iterations, callbacks are triggered by BendersSolver at the appropriate times.

        flowchart LR
    BendersSolver -- triggers --> CustomCallback
    CustomCallback -- has --> BendersContext
    CustomCallback -- inherits --> CallbackBase

    style BendersSolver fill:#f2f2f2,stroke:#333,stroke-width:1px
    style CustomCallback fill:white,stroke:#333,stroke-width:1px
    

Callback System Inheritance Diagram

BendersContext - Attributes

benders	The Benders decomposition solver instance (BendersSolver).
master_problem	The current master problem instance (MasterProblem).
sub_problem	The current subproblem instance (SubProblem, SubProblems, LogicBasedSubProblem).
state	The current state of the Benders decomposition process (BendersResult).
current_comp_vals	A dictionary mapping complicating variable names to their current values in the master problem solution.
current_opti_cuts	A List of optimality cuts generated in the current iteration (OptimalityCut).
current_feas_cuts	A List of feasibility cuts generated in the current iteration (FeasibilityCut).

CallbackBase - Methods

on_benders_start	Called at the start of the Benders decomposition process.
on_benders_end	Called at the end of the Benders decomposition process.
on_iteration_start	Called at the start of each Benders decomposition iteration.
on_iteration_end	Called at the end of each Benders decomposition iteration.
on_master_build	Called after the master problem is built.
on_before_master_solve	Called before solving the master problem.
on_after_master_solve	Called after solving the master problem.
on_sub_build	Called after the subproblem is built.
on_before_sub_solve	Called before solving the subproblem.
on_after_sub_solve	Called after solving the subproblem.
on_opti_cut_generated	Called when an optimality cut is generated.
on_feas_cut_generated	Called when a feasibility cut is generated.
on_opti_cut_added	Called when an optimality cut is added to the master problem.
on_feas_cut_added	Called when a feasibility cut is added to the master problem.
on_new_lower_bound	Called when a higher lower bound is found.
on_new_upper_bound	Called when a lower upper bound is found.