Solver Interfaces

Supported Solvers

Attention

BendersLib will NOT install any solver to your environment automatically. You need to install the solvers separately based on your needs.

BendersLib supports the following solvers. The features listed in the table are essential for Benders decomposition. A Benders decomposition variant usually require one or two features to work properly.

• Dual: The solver can provide dual values of constraints. This is essential for generating classical optimality cuts. This feature can be required by Classical Benders Decomposition and L-shaped Method implemented with ClassicalBenders and LShaped, respectively, if the user wants to add optimality cuts.

• Farkas: The solver can provide a Farkas certificate of infeasibility (an extreme ray of the dual). This is used to generate classical feasibility cuts. This feature can be required by Classical Benders Decomposition and L-shaped Method implemented with ClassicalBenders and LShaped, respectively, if the user wants to add feasibility cuts.

• IIS: The solver can find an Irreducible Inconsistent Subsystem (IIS). This helps building stronger no-good cuts. This feature usually works with Combinatorial Benders Decomposition and Logic-based Benders Decomposition implemented with CombinatorialBenders and LogicBasedBenders, respectively, if the user wants to add no-good feasibility cuts.

• BnC: The solver supports branch-and-check, or branch-and-Benders-cut, a modern implementation of Benders decomposition that integrates cut generation into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed. This requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process.

Examples

• See Solver Usage for example code using different solvers with BendersLib.

• See Computing IIS for example code of computing IIS with different solvers.

Supported Solvers’ Features

Solver	Class	Doc	Dual	Farkas	IIS	BnC	License
COPT	Copt	Doc	✅	✅	✅	✅	Commercial
CPLEX	Cplex	Doc	✅	✅	✅	✅	Commercial
CP Optimizer	CplexCP	Doc	❌	❌	✅	❌	Commercial
Gurobi	Gurobi	Doc	✅	✅	✅	✅	Commercial
OR-Tools [1]	Ortools	Doc	❌	❌	✅	❌	Open-source
SCIP	Scip	Doc	🟨 [2]	✅	✅	✅	Open-source
Pyomo [3]:	Pyomo	Doc	-	-	[4]	-	Open-source
CBC	'cbc'	Doc	✅	❌	✅	❌	Open-source
CPLEX	'cplex', 'cplex_direct'	Doc	✅	❌	✅	❌	Commercial
	'cplex_persistent'	Doc	✅	❌	✅	❌	Commercial
GLPK	'glpk'	Doc	✅	❌	✅	❌	Open-source
Gurobi	'gurobi', 'gurobi_direct'	Doc	✅	❌	✅	❌	Commercial
	'gurobi_persistent'	Doc	✅	✅	✅	❌	Commercial
HiGHS	'highs'	Doc	✅	❌	❌	❌	Open-source
MOSEK	'mosek', 'mosek_direct'	Doc	✅	❌	✅	❌	Commercial
SCIP	'scip'	Doc	❌ [2]	❌	✅	❌	Open-source
Xpress	'xpress', 'xpress_direct'	Doc	✅	❌	✅	❌	Commercial
	'xpress_persisitent'	Doc	✅	❌	✅	❌	Commercial

[1]

Here we only use the CP-SAT solver provided by OR-Tools for Constraint Programming (CP).

[2] (1,2)

SCIP may return incorrect dual values (see this discussion and documentation; and this issue). All-zero dual values are returned when using SCIP in Pyomo.

[3]

Pyomo is a modeling language. Supported solvers must be installed separately, see Installing Solvers (by BendersLib), installation instruction (by Pyomo), and supported solvers.

[4]

Using Minimal Intractable System (MIS) Finder.

These solvers can be categorized into two groups: Mathematical Programming solvers (most of the solvers supported) and Constraint Programming solvers (CplexCP and Ortools), which are two different paradigms for solving optimization problems. They have distinct approaches and are suited for different types of problems. A wise choice between the two can lead to more efficient problem-solving.

Mathematical Programming vs Constraint Programming

Feature	Mathematical Programming	Constraint Programming
Origin	Operations Research (OR)	Artificial Intelligence (AI)
Core Idea	Optimize a specific objective function subject to a set of constraints.	Find a feasible solution that satisfies all constraints, without necessarily having an objective function.
Typical Techniques	Simplex method, interior-point methods.	Backtracking, constraint propagation, and local search.
Best Suited For	Problems with quantitative variables and linear/nonlinear relationships.	Problems with combinatorial structures and discrete variables.

There are many successful attempts that combing both paradigms. Specifically in Combinatorial Benders Decomposition and Logic-based Benders Decomposition, master problems are often modeled using Mathematical Programming, while subproblems can be modeled using Constraint Programming to leverage its strengths in handling combinatorial constraints.

Using a solver not listed here? No worries! See the next section on how to create a custom solver interface, and see Custom Subproblem for even simpler ways to use custom solvers for subproblems.

---

Customization

BendersLib is designed to be extensible, allowing you to integrate solvers that are not natively supported. This is achieved by creating a custom solver interface.

To add a new solver, you need to create a class that inherits from SolverBase (for Mathematical Programming, or SolverCPBase for Constraint Programming). This base class serves as a template for all solver interfaces in BendersLib. The SolverBase is an Abstract Base Class (ABC), a feature from Python. ABCs are used to define interfaces, meaning a concrete class that inherits from an ABC must implement all of its abstract methods. This ensures that every solver interface in BendersLib provides a consistent set of functionalities. When you create your custom solver class, you must inherit from SolverBase and provide implementations for all methods decorated with @abstractmethod, and define all attributes defined in SolverBase.

While SolverBase defines several abstract methods that you must implement, two methods, make_master_problem() and make_sub_problem(), have special considerations. These methods are essential for the AnnotatedBenders class, which automates the decomposition process. If you do not intend to use AnnotatedBenders, you might not need to implement the full logic for these methods. However, for a solver interface to be considered for contribution to the official BendersLib repository, a complete and functional implementation of these methods is required to ensure full compatibility with all library features.

To see a practical implementation, you can refer to the source code of the built-in solver interfaces, such as Gurobi. Examining how it inherits from SolverBase and implements the required methods will provide a clear and effective template for creating your own custom solver.

Contributing solver interfaces to BendersLib is welcome! See Contributing for how to contribute your custom solver interface to the official repository.

---

Attributes & Methods

Below are the attributes and methods of the base solver interfaces SolverBase (Mathematical Programming) and SolverCPBase (Constraint Programming). Any built-in solver interface is inherited from one of them, with the attributes and methods properly implemented. Adding a new solver interface requires implementing these attributes and methods, especially the abstract methods. See SolverBase nd SolverCPBase for the comprehensive API reference, and built-in solver interfaces for examples. Note that the solver interfaces are not designed to be used directly by end-users. Use MasterProblem and SubProblem instead, which internally utilize the solver interfaces to interact with the optimization solvers.

        flowchart TB
    subgraph "Mathematical Programming"
        Gurobi
        Copt
        Pyomo
        Scip
        Cplex
    end

    subgraph "Constraint Programming"
        Ortools
        CplexCP
    end

    Gurobi -- inherits --> SolverBase
    Copt -- inherits --> SolverBase
    Pyomo -- inherits --> SolverBase
    Scip -- inherits --> SolverBase
    Cplex -- inherits --> SolverBase
    Ortools -- inherits --> SolverCPBase
    CplexCP -- inherits --> SolverCPBase
    

Solver Interface Inheritance Diagram

SolverBase - Attributes

model	A copy of the original solver model instance.
status	The status of the last solve attempt.

Tip

More attributes can be accessed via model, which is the underlying solver model instance.

SolverBase - Methods

add_estimators	Add estimator variable(s) to the objective function of the model.
fix_vars	Fix the values of specified variables in the model.
unfix_vars	Unfix the specified variables in the model by restoring their original bounds.
get_var_values	Get the current values of specified variables in the model.
get_var_coefs	Get the coefficients of specified variables in all the constraints of the model.
get_rhs	Get the right-hand side values of all constraints in the model.
get_dual_values	Get the dual values (shadow prices) of all constraints in the model.
get_extreme_ray	Get the extreme ray of the model.
get_obj	Get the objective value of the model after solving.
add_cut	Add a Benders cut to the solver's model as a constraint.
remove_cut	Remove a constraint from the solver's model by its name.
solve	Solve the optimization model using the solver's built-in optimization method.
compute_iis	Compute the Irreducible Infeasible Subsystem (IIS) of the model if it is infeasible.
make_master_problem	Build the master problem from the original problem.
make_sub_problem	Build the subproblem from the original problem.

SolverCPBase - Attributes

model	A copy of the original solver model instance.
status	The status of the last solve attempt.

SolverCPBase - Methods

fix_vars	Fix the values of specified variables in the model.
unfix_vars	Unfix the specified variables in the model by restoring their original bounds.
get_var_values	Get the current values of specified variables in the model.
get_obj	Get the objective value of the model after solving.
compute_iis	Compute the Irreducible Infeasible Subsystem (IIS) of the model if it is infeasible.
solve	Solve the optimization model using the solver's built-in optimization method.