Subproblem

Create a Subproblem

To create a master problem, you first need to build a model using one of the supported solvers’ official modeling APIs. The solvers’ official documentation provides detailed instructions on how to create models. Then, you can create a SubProblem instance by passing the model wrapped with its corresponding solver interface in BendersLib.

The complicating variables in the master problem must also appear in the subproblem with exactly the same names. This is crucial for the correct functioning. Internally, BendersLib treats these variables as subproblem parameters, which will be fixed to the values obtained from the master problem’s solution during the Benders decomposition process.

The code snippets below demonstrates how to create master problems using model objects of different solvers. Make sure to install the needed solver before running the code.

COPT

import coptpy
from coptpy import COPT
from benderslib import SubProblem
from benderslib.solvers import Copt

# Create a COPT model
env = coptpy.Envr()
sub_model = env.createModel("Sub")
y = sub_model.addVar(name="y", vtype=COPT.CONTINUOUS)
x = sub_model.addVar(name="x") # complicating variable
sub_model.addConstr(y >= x)
sub_model.setObjective(2 * y)

# Create a SubProblem
sub_problem = SubProblem(Copt(sub_model), complicating_vars=['x'])
print(sub_problem)

CPLEX

import cplex
from benderslib import SubProblem
from benderslib.solvers import Cplex

# Create a CPLEX model
sub_model = cplex.Cplex()
sub_model.variables.add(names=["y"], types=[sub_model.variables.type.continuous])
sub_model.variables.add(names=["x"]) # complicating variable
sub_model.linear_constraints.add(
    lin_expr=[cplex.SparsePair(ind=["y", "x"], val=[1, -1])],
    senses=["G"],
    rhs=[0]
)
sub_model.objective.set_sense(sub_model.objective.sense.minimize)
sub_model.objective.set_linear("y", 2)

# Create a SubProblem
sub_problem = SubProblem(Cplex(sub_model), complicating_vars=['x'])
print(sub_problem)

Gurobi

from gurobipy import Model, GRB
from benderslib import SubProblem
from benderslib.solvers import Gurobi

# Create a Gurobi model
sub_model = Model("Sub")
y = sub_model.addVar(name="y", vtype=GRB.CONTINUOUS)
x = sub_model.addVar(name="x") # complicating variable
sub_model.addConstr(y >= x)
sub_model.setObjective(2 * y)
sub_model.update()

# Create a SubProblem
sub_problem = SubProblem(Gurobi(sub_model), complicating_vars=['x'])
print(sub_problem)

Example

Simple Classical Benders Example

Pyomo

import pyomo.environ as pyo
from benderslib import SubProblem
from benderslib.solvers import Pyomo

# Create a Pyomo model
sub_model = pyo.ConcreteModel("Sub")
sub_model.y = pyo.Var(domain=pyo.NonNegativeReals)
sub_model.x = pyo.Var(domain=pyo.NonNegativeReals) # complicating variable
sub_model.c = pyo.Constraint(expr=sub_model.y >= sub_model.x)
sub_model.obj = pyo.Objective(expr=2 * sub_model.y)

# Create a SubProblem
solver_name = 'gurobi_direct'  # Change to your preferred solver
sub_problem = SubProblem(Pyomo(sub_model, solver=solver_name), complicating_vars=['x'])
print(sub_problem)

Example

Tested solver backends for Pyomo

SCIP

from pyscipopt import Model
from benderslib import SubProblem
from benderslib.solvers import Scip

# Create a SCIP model
sub_model = Model("Sub")
y = sub_model.addVar(vtype="C", name="y")
x = sub_model.addVar(name="x") # complicating variable
sub_model.addCons(y >= x)
sub_model.setObjective(2 * y, "minimize")

# Create a SubProblem
sub_problem = SubProblem(Scip(sub_model), complicating_vars=['x'])
print(sub_problem)

Above are Mathematical Programming solvers. In addition, BendersLib also supports Constraint Programming solvers for subproblems. This feature is useful for Combinatorial Benders Decomposition and Logic-based Benders Decomposition that involve combinatorial subproblems. Below are code snippets using Ortools and CplexCP as subproblem solvers.

OR-Tools (Constraint Programming)

from ortools.sat.python import cp_model
from benderslib.solvers import Ortools
from benderslib import SubProblem

# Create an Ortools model
model = cp_model.CpModel()
y = model.NewIntVar(0, 10, 'y')
x = model.NewIntVar(0, 10, 'x') # complicating variable
model.Add(y >= x)
model.Minimize(2 * y)

vars_map = {'x': x, 'y': y}

# Create a SubProblem
sub_problem = SubProblem(Ortools(model, vars_map=vars_map), complicating_vars=['x'])
print(sub_problem)

Cplex (Constraint Programming)

from benderslib import SubProblem
from benderslib.solvers import CplexCP
from docplex.cp.model import CpoModel

# Create a CplexCP model
model = CpoModel()
y = model.integer_var(0, 10, 'y')
x = model.integer_var(0, 10, 'x')  # complicating variable
model.add(y >= x)
model.minimize(2 * y)

vars_map = {'x': x, 'y': y}

# Create a SubProblem
sub_problem = SubProblem(CplexCP(model, vars_map=vars_map), complicating_vars=['x'])
print(sub_problem)

Please refer to Solver Usage for executable examples of using different solvers.

Create a Subproblem from an Annotated Model

Please refer to Create a Master Problem from an Annotated Model.

Compute Irreducible Infeasible Subsystem (IIS)

In Combinatorial Benders Decomposition and Logic-based Benders Decomposition, the feasibility cut is not derived from dual but is instead formulated based on the IIS of the subproblem. This makes the ability to compute an IIS a key feature for these methods. BendersLib provides a unified interface to compute the IIS for subproblems, regardless of the underlying solver. You can use the compute_iis() method, which will invoke the solver’s IIS computation capabilities. Not all solvers support IIS computation, refer to the Supported Solvers’ Features for details.

# Assuming sub_problem is an infeasible SubProblem instance
iis_vars = sub_problem.compute_iis()
print(f"IIS consists of: {iis_vars}")

This method returns a set of variable names that are part of the IIS.

Example

Computing IIS, Combinatorial Benders Decomposition (IIS), Integer L-shaped Method (IIS)

Create Multiple Subproblems

For stochastic programming problems with multiple scenarios, you can create a SubProblems instance to manage them. This class takes an iterable of SubProblem instances and their corresponding probabilities (if not provided, equal probabilities are assumed).

from gurobipy import Model, GRB
from benderslib import SubProblem, SubProblems
from benderslib.solvers import Gurobi

# Assume we have two scenarios
scenarios = [10, 20]
probs = [0.4, 0.6]

# Create a subproblem for each scenario
sub_models = []
for s in scenarios:
    sub_model = Model(f"Sub_{s}")
    y = sub_model.addVar(name="y", vtype=GRB.CONTINUOUS)
    x = sub_model.addVar(name="x") # complicating variable
    sub_model.addConstr(y >= x + s)
    sub_model.setObjective(2 * y)
    sub_model.update()
    sub_models.append(sub_model)

# Create a SubProblems instance with a list of SubProblem instances
sub_problem_instances = [SubProblem(Gurobi(m)) for m in sub_models]
sub_problems = SubProblems(sub_problem_instances, prob=probs)

Example

L-shaped Method, L-shaped Method by Logic-based Benders Decomposition

Solve and Access Results

Before solving, you can first fix the values of the complicating variables, which are obtained from the master problem’s solution, using the SubProblem.fix_vars() method. To solve the subproblem, use the SubProblem.solve() method.

master_solution = {'x': 5}
sub_problem.fix_vars(master_solution)

sub_problem.solve()

After solving, you can get the values of the decision variables, objective value, and information for Benders cuts.

# Access solution
var_values = sub_problem.get_var_values(['y'])
print(f"Variable values: {var_values}")

# Access objective
obj_val = sub_problem.get_obj()
print(f"Objective value: {obj_val}")

# For optimality cuts
if sub_problem.status == 'OPTIMAL':
    dual_values = sub_problem.get_dual_values()
    print(f"Dual values: {dual_values}")

# For feasibility cuts
elif sub_problem.status == 'INFEASIBLE':
    extreme_ray = sub_problem.get_extreme_ray()
    print(f"Extreme ray: {extreme_ray}")

The process is similar for a SubProblems instance, which manages multiple subproblems. When you call methods like fix_vars(), solve(), get_var_values(), or get_obj() on a SubProblems instance, the action is applied to all subproblems it contains. The results are aggregated (e.g., objective values are summed with probabilities). To access information for each individual subproblem, you can iterate through the sub_problems attribute.

---

Customization

For certain problems, especially Logic-based Benders Decomposition, the subproblem may not be a standard optimization model that can be handled by a conventional solver. Instead, it might be solved by a combinatorial algorithm, a heuristic, or some other custom logic. BendersLib provides a flexible way to handle such cases through custom subproblem implementations.

Custom Subproblem (class-based)

You can create a custom subproblem solver by defining a class that inherits from the abstract base class LogicBasedSubProblem. You must implement the LogicBasedSubProblem.solve() method, where you define the logic for solving the subproblem. Inside this method, you should update the attributes status, obj, and var_values.

• status: BendersConsts.OPTIMAL or BendersConsts.INFEASIBLE.

• obj: The objective value of the subproblem solution.

• var_values: A dictionary mapping variable names to their values in the subproblem solution.

When doing so, you can assume that the values of the complicating variables from the master problem are available in the complicating_var_values attribute.

from benderslib import LogicBasedSubProblem, CST

class MyCustomSubproblem(LogicBasedSubProblem):
    def solve(self):
        # Access master variables' values
        x_val = self.complicating_var_values['x']

        # Implement your custom solving logic here
        # and set the status, obj, and var_values attributes
        if x_val > 5:
            self.status = CST.INFEASIBLE
            self.obj = None
            self.var_values = {}
        else:
            self.status = CST.OPTIMAL
            self.obj = 10 - x_val
            self.var_values = {'y': 2 * x_val}

custom_subproblem = MyCustomSubproblem(complicating_vars=['x'])

Custom Subproblem (function-based)

For simpler, stateless subproblems, you can define a function instead of a class. The function must accept a dictionary of the complicating variables’ values and return a tuple containing the attributes status, obj, and var_values. This function can be passed directly to LogicBasedBenders as a subproblem.

from benderslib import CST

def subproblem_solver(master_vars: dict[str, float]) -> tuple[str, float, dict[str, float]]:
    # Access master variables' values
    x_val = master_vars['x']

    # Implement your custom solving logic here
    if x_val > 5:
        status = CST.INFEASIBLE
        obj = None
        var_values = {}
    else:
        status = CST.OPTIMAL
        obj = 10 - x_val
        var_values = {'y': 2 * x_val}

    # Return status, objective value, and variable values (as a dict)
    return status, obj, var_values

Using a function is convenient for simple cases. However, for more complex subproblems that require maintaining state across iterations (e.g., caching results), a class-based approach is recommended.

Example

• See Facility Location (Gurobi) for how to implement a custom subproblem solver with a function, using logic-based Benders decomposition.

Multiple Custom Subproblems (class-based)

When your problem involves multiple scenarios that are solved with custom logic (e.g., stochastic programming with a combinatorial subproblem), you can manage them using the SubProblems class. Simply create instances of your custom subproblem class for each scenario and pass them to SubProblems.

from benderslib import SubProblems, LogicBasedSubProblem, CST

class MyScenarioSubproblem(LogicBasedSubProblem):
    def __init__(self, complicating_vars, scenario_data):
        super().__init__(complicating_vars)
        self.scenario_data = scenario_data

    def solve(self):
        # Access master variables' values
        x_val = self.complicating_var_values['x']

        # Use ``self.scenario_data`` in the solving logic
        if x_val > self.scenario_data:
            self.status = CST.INFEASIBLE
            self.obj = None
            self.var_values = {}
        else:
            self.status = CST.OPTIMAL
            self.obj = self.scenario_data - x_val
            self.var_values = {'y': 2 * x_val}

scenarios = [1, 2, 3]
probs = [0.3, 0.4, 0.3]
subproblem_instances = [MyScenarioSubproblem(['x'], s) for s in scenarios]
sub_problems = SubProblems(subproblem_instances, prob=probs)

Example

See L-shaped Method by Logic-based Benders Decomposition for how to implement the L-shaped method, which involves multiple subproblems, using logic-based Benders decomposition with custom subproblem classes.

Multiple Custom Subproblems (function-based)

Currently, BendersLib does not support function-based custom subproblems. But you can define the logic of solving multiple subproblems within a function, then using that function as a subproblem in a Benders decomposition algorithm.

Example

See Stochastic Logic-Based Benders Decomposition for how to solve multiple subproblems with a function, using logic-based Benders decomposition.

---

Attributes & Methods

The class SubProblem is inherited from the base class ProblemBase, but tailored for subproblems in Benders Decomposition. ProblemBase takes an instance that inherits from SolverBase or SolverCPBase as an argument to handle the underlying optimization solver. For stochastic programming with multiple scenarios, the class SubProblems manages multiple subproblem instances.

We also provide a LogicBasedSubProblem template for custom subproblem, especially for Logic-based Benders Decomposition that do not rely on traditional optimization solvers. Users can inherit from LogicBasedSubProblem and implement the required abstract methods for custom subproblem logic.

        flowchart LR
    SubProblem -- inherits --> ProblemBase
    ProblemBase -. uses .-> SolverBase
    ProblemBase -. uses .-> SolverCPBase
    SubProblems -. contains .-> SubProblem
    SubProblems -. contains .-> LogicBasedSubProblem

style SolverBase fill:#f2f2f2,stroke:#333,stroke-width:1px
style SolverCPBase fill:#f2f2f2,stroke:#333,stroke-width:1px
    

Subproblem Inheritance Diagram

*Note: Dashed arrows indicate optional relationships, from which exactly one must be selected for each usage.

Below are the attributes and methods SubProblem, SubProblems, and LogicBasedSubProblem.

SubProblem - Attributes

solver	An instance of the solver backend (see classes in Solver Interfaces).
model	A copy of the original solver model instance.
status	The status of the problem (see BendersConsts for possible values).
params	The parameters that can be set by the user (see BendersParams).
complicating_vars	A list of names of the complicating variables.

Tip

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

SubProblem - 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.
solve	Solve the problem and update the status attribute.

LogicBasedSubProblem - Attributes

complicating_vars	A list of names of the complicating variables.
complicating_var_values	The values of complicating variables provided by the master problem.
obj	The objective value of the subproblem after solving.
var_values	The values of variables in the subproblem after solving.
status	The status of the problem (see BendersConsts for possible values).
params	The parameters that can be set by the user (see BendersParams).

LogicBasedSubProblem - Methods

solve	Solve the subproblem and update the status, obj, and var_values attributes.
fix_vars	Fix the values of specified variables in the model (do not override it).
get_var_values	Get the current values of specified variables in the model (do not override it).
get_obj	Get the objective value of the model after solving (do not override it).

SubProblems - Attributes

sub_problems	A list of SubProblem or LogicBasedSubProblem instances.
prob	A list of probabilities or weights associated with each subproblem.
params	The parameters that can be set by the user (see BendersParams).
status	The status of the problem (see BendersConsts for possible values).

SubProblems - Methods

solve	Solve all subproblems and update the status attribute.
fix_vars	Fix the values of specified variables in all subproblems.
get_var_values	Get the current values of specified variables in all subproblems.
get_obj	Get the prob weighted objective value of all subproblems.