Benders cut generation

Coluna provides an interface and generic functions to implement a Benders cut generation algorithm.

In this section, we are first going to present the generic functions, the implementation with some theory backgrounds and then give the references of the interface. The default implementation is based on the paper of

You can find the generic functions and the interface in the Benders submodule and the default implementation in the Algorithm submodule at src/Algorithm/benders.

Context

The Benders submodule provides an interface and generic functions to implement a benders cut generation algorithm. The implementation depends on an object called context.

Benders provides two types of context:

BendersContext(reformulation, algo_params) -> BendersContext

BendersPrinterContext(reformulation, algo_params) -> BendersPrinterContext

Generic functions

Generic functions are the core of the Benders cut generation algorithm. There are three generic functions:

See ...

See ...

These functions are independent of any other submodule of Coluna. You can use them to implement your own Benders cut generation algorithm.

Reformulation

The default implementation works with a reformulated problem contained in MathProg.Reformulation where master and subproblems are MathProg.Formulation objects.

The master has the following form:

\[\begin{aligned} \min \quad& cx + \sum_{k \in K} \eta_k & &\\ \text{s.t.} \quad& Ax \geq a & & (1) \\ & \text{< benders cuts>} & & (2) \\ & l_1 \leq x \leq u_1 & & (3) \\ & \eta_k \in \mathbb{R} & \forall k \in K \quad& (4) \end{aligned}\]

where $x$ are first-stage variables, $\eta_k$ is the second-stage cost variable for the subproblem $k$, constraints $(1)$ are the first-stage constraints, constraints $(2)$ are the Benders cuts, constraints $(3)$ are the bounds on the first-stage variables, and expression $(4)$ shows that second-stage variables are free.

The subproblems have the following form:

\[\begin{aligned} \min \quad& fy + {\color{gray} \mathbf{1}z' + \mathbf{1}z''} &&& \\ \text{s.t.} \quad& Dy {\color{gray} + z'} \geq d - B\bar{x} && (5) \quad& {\color{blue}(\pi)} \\ & Ey {\color{gray} + z''} \geq e && (6) \quad& {\color{blue}(\rho)} \\ & l_2 \leq y \leq u_2 && (7) \quad& {\color{blue}(\sigma)} \end{aligned}\]

where $y$ are second-stage variables, $z'$ and $z''$ are artificial variables (in grey because they are deactivated by default), constraints (5) are the reformulation of linking constraints using the first-stage solution $\bar{x}$, constraints (6) are the second-stage constraints, and constraints (7) are the bounds on the second-stage variables. In blue, we define the dual variables associated to these constraints.

References:

Main loop

This is a description of how the Coluna.Benders.run_benders_loop! generic function behaves with the default implementation.

The loop stops if one of the following conditions is met:

• the master is infeasible
• a separation subproblem is infeasible
• the time limit is reached
• the maximum number of iterations is reached
• no new cut is generated

The default implementation returns:

References:

benders_output_type(context) -> Type{<:AbstractBendersOutput}

Benders cut generation iteration

This is a description of how the Coluna.Benders.run_benders_iteration! generic function behaves with the default implementation.

These are the main steps of a Benders cut generation iteration without stabilization. Click on the step to go to the corresponding section.

In the default implementation, some sections may have different behaviors depending on the result of previous steps.

Master optimization

This operation consists in optimizing the master problem in order to find a first-level solution $\bar{x}$.

In the default implementation, master optimization can be performed using SolveLpForm (LP solver) or SolveIpForm (MILP solver). When getting the solution, we store the current value of second stage variables $\bar{\eta}_k$ as incumbent value (see Coluna.MathProg.getcurincval).

It returns an object of the following type:

References:

optimize_master_problem!(master, context, env) -> MasterResult

Go back to the cut generation iteration diagram.

Unbounded master case

Second stage cost $\eta_k$ variables are free. As a consequence, the master problem is unbounded when there is no optimality Benders cuts.

In this case, Coluna.Benders.treat_unbounded_master_problem_case! is called. The main goal of the default implementation of this method is to get the dual infeasibility certificate of the master problem.

If the master has been solved with a MIP solver at the previous step, we need to relax the integrality constraints to get a dual infeasibility certificate.

If the solver does not provide a dual infeasibility certificate, the implementation has an "emergency" routine to provide a first-stage feasible solution by solving the master LP with cost of second stage variables set to zero. We recommend using a solver that provides a dual infeasibility certificate and avoiding the "emergency" routine.

References:

treat_unbounded_master_problem_case!(master, context, env) -> MasterResult

Go back to the cut generation iteration diagram.

Setup separation subproblems

Default implementation of Coluna.Benders.update_sp_rhs! updates the right-hand side of the linking constraints (5).

Reference:

update_sp_rhs!(context, sp, mast_primal_sol)

Default implementation of Coluna.Benders.setup_separation_for_unbounded_master_case! gives rise to the formulation proposed in Lemma 2 of Bonami et al:

\[\begin{aligned} (SepB) \equiv \min \quad& fy + {\color{gray} \mathbf{1}z' + \mathbf{1}z''} &&& \\ \text{s.t.} \quad& Dy {\color{gray} + z'} \geq -B\bar{x} && (5a) \quad& {\color{blue}(\pi)} \\ & Ey {\color{gray} + z''} \geq 0 && (6a) \quad& {\color{blue}(\rho)} \\ & y \geq 0 && (7a) \quad& {\color{blue}(\sigma)} \end{aligned}\]

where $y$ are second-stage variables, $z'$ and $z''$ are artificial variables (in grey because they are deactivated by default), and $\bar{x}$ is an unbounded ray of the restricted master.

Reference:

setup_separation_for_unbounded_master_case!(context, sp, mast_primal_sol)

Subproblem iterator

Not implemented yet.

Separation subproblem optimization

The default implementation first optimize the subproblem without the artificial variables $z'$ and $z''$. In the case where it finds $(\bar{\pi}, \bar{\rho}, \bar{\sigma})$ an optimal dual solution to the subproblem, the following cut is generated:

\[\eta_k + \bar{\pi}Bx \geq d\bar{\pi} + \bar{\rho}e + \bar{\sigma_{\leq}} l_2 + \bar{\sigma_{\geq}} u_2\]

with $\bar{\sigma_{\leq}} l_2$ (respectively $\bar{\sigma_{\geq}} u_2$) the dual of the left part (respectively the right part) of constraint $l_2 \leq y \leq u_2$ of the subproblem.

In the case where it finds the subproblem infeasible, it calls Coluna.Benders.treat_infeasible_separation_problem_case!. The default implementation of this method activates the artificial variables $z'$ and $z''$, sets the cost of second stage variables to 0, and optimizes the subproblem again.

If a solution with no artificial variables is found, the following cut is generated:

\[\bar{\pi}Bx \geq d\bar{\pi} + \bar{\rho}e + \bar{\sigma_{\leq}} l_2 + \bar{\sigma_{\geq}} u_2\]

Both methods return an object of the following type:

References:

optimize_separation_problem!(context, sp_to_solve, env, unbounded_master) -> SeparationResult

treat_infeasible_separation_problem_case!(context, sp_to_solve, env, unbounded_master) -> SeparationResult

Go back to the cut generation iteration diagram.

Set of generated cuts

You can define your data structure to manage the cuts generated at a given iteration. Columns are inserted after the optimization of all the separation subproblems to allow the parallelization of the latter.

In the default implementation, cuts are represented by the following data structure:

We use the following data structures to store the cuts and the primal solutions to the subproblems:

The default implementation of push_in_set! has the responsibility to check if the cut is violated. Given $\bar{\eta}_k$ solution to the restricted master and $\bar{y}$ solution to the separation problem, the cut is considered as violated when:

• the separation subproblem was infeasible
• or $\bar{\eta}_k \geq f\bar{y}$

References:

push_in_set!(context, cut_pool, sep_result) -> Bool

push_in_set!(context, sep_sp_sols, sep_result) -> Bool

Go back to the cut generation iteration diagram.

Unboundedness check

To perform this check, we need a solution to each separation problem.

Let $(\bar{\eta}_k)_{k \in K}$ be the value of second stage variables in the dual infeasibility certificate of the restricted master. Let $\bar{y}$ be an optimal solution to the separation problem (SepB).

As indicated by Bonami et al., if $f\bar{y} \leq \sum\limits_{k \in K} \bar{\eta}_k$, then the original problem is unbounded (by definition of an unbounded ray of the original problem).

References:

Cuts insertion

The default implementation inserts into the master all the cuts stored in the CutsSet object.

Reference:

Go back to the cut generation iteration diagram.

Current primal solution

Lorem ipsum.

References:

Iteration output

References:

benders_iteration_output_type(context) -> Type{<:AbstractBendersIterationOutput}

Go back to the cut generation iteration diagram.

Getters for Result data structures

Go back to the cut generation iteration diagram.

Stabilization

Not implemented yet.