Workflow¶

Basic Usage¶

In the basic scenario, you can use the built-in Benders decomposition methods provided by BendersLib. This approach is suitable for standard problems that align with one of the predefined Benders decomposition frameworks. BendersLib offers several implementation of the Benders variants and the necessary Benders cuts and cut generators.

         sequenceDiagram
     actor User
     participant BendersLib
     participant Built-in Cut Generator
     participant Solver Interface

     User->>Solver Interface: 1. Define master & subproblems
     User->>BendersLib: 2. Create BendersSolver instance
     User->>BendersLib: 3. Set parameters (optional)
     User->>BendersLib: 4. solve()
     loop Benders Iteration
         Solver Interface-->>BendersLib: Return master/sub solution
         Built-in Cut Generator-->>BendersLib: Generate cuts
         BendersLib->>BendersLib: Check convergence & add cuts
     end
     BendersLib-->>User: 5. Return solution

Basic Usage Workflow¶

The workflow involves modeling the master and subproblems using a supported solver interface, and then passing these models to the Benders class specified for your chosen decomposition method. You can then configure BendersParams such as convergence tolerance and maximum iterations before invoking the BendersSolver.solve() method. The BendersLib handles the iterative process of solving the master problem, passing the solution to the subproblems, and generating the necessary optimality and feasibility cuts automatically.

Advanced Usage¶

For more complex problems that do not fit the standard Benders decomposition patterns, BendersLib offers an advanced usage mode. This mode provides the flexibility to customize subproblem solver and cut generator, which are the key components of the Benders algorithm. This feature is especially useful for implementing Logic-based Benders Decomposition, as it allows the subproblem to be any type of optimization problem without a standard method for formulating Benders cuts.

        sequenceDiagram
    actor User
    participant BendersLib
    participant Custom Cut Generator
    participant Custom Solver
    participant Solver Interface

    User->>Solver Interface: 1. Define master problem
    User->>Custom Solver: 2. Define custom subproblem solver
    User->>Custom Cut Generator: 3. Define custom cut generator
    User->>BendersLib: 4. Create BendersSolver instance
    User->>BendersLib: 5. Set parameters (optional)
    User->>BendersLib: 6. solve()
    loop Benders Iteration
        Solver Interface-->>BendersLib: Return master solution
        Custom Solver-->>BendersLib: Return sub solution
        Custom Cut Generator-->>BendersLib: Generate cuts
        BendersLib->>BendersLib: Check convergence & add cuts
    end
    BendersLib-->>User: 7. Return solution

Advanced Usage Workflow¶

Custom Subproblem Solver: You are not limited to built-in solvers for the subproblems. You can implement a custom solver, which can be any algorithm or method that can solve the subproblem given a solution from the master problem. This is achieved by creating a class that inherits from LogicBasedSubProblem. It is particularly useful for subproblems that have special structure that can be exploited by a specialized algorithm.
Custom Cut Generator: You can define your own logic for generating optimality and feasibility cuts. This is done by creating a class that inherits from CutGenerator, or by simply providing a function that returns a list of Cut objects. When using a class-based approach, you can maintain state between iterations, which is important for cuts management and advanced acceleration techniques. This allows for the implementation of specialized cuts that can improve the convergence of the algorithm.

Expert Usage¶

This section covers expert-level features for fine-tuning the Benders decomposition algorithm, including the use of callbacks for implementing custom acceleration strategies, such as warm start, cut management, and cut selection.

        sequenceDiagram
    actor User
    participant BendersLib
    participant Custom Callbacks
    participant Solver Interface

    User->>Solver Interface: 1. Define master & subproblems
    User->>Custom Callbacks: 2. Define custom callbacks
    User->>BendersLib: 3. Create BendersSolver instance
    User->>BendersLib: 4. Set parameters (optional)
    User->>BendersLib: 5. solve()
    loop Benders Iteration
        Solver Interface-->>BendersLib: Return master/sub solution
        BendersLib-->>Custom Callbacks: Trigger callbacks during various events
        BendersLib->>BendersLib: Check convergence & add cuts
    end
    BendersLib-->>User: 6. Return solution

Expert Usage Workflow¶

Custom Callbacks: Callbacks allow for the injection of custom logic at various stages of the Benders decomposition algorithm. This is achieved by creating a class that inherits from CallbackBase and implementing the desired methods. Callbacks can be used to implement acceleration strategies such as warm-starting the subproblems, managing the cut pool, or implementing custom termination criteria.