Overview

This separator finds cuts in the original problem and then transfers them to the master.

Theoretical Background

Consider a general linear program with two sets of constraints:

\begin{align} \min \quad& c^T x &\\ s.t. \quad & Ax &\ge b \\ & Dx &\ge d \\ & x &\ge 0 \\ \end{align}

As-su-me that GCG chose the constraints \( Dx \ge d \) to derive the decomposition from. Set \( X = \{x \colon Dx \ge d, x \ge 0\} \) and let \(P\) be the set of extreme points of \( X \). Then the restricted master problem has the form

\begin{align} \min & \sum \limits_{p \in P’} c_p \lambda_p &\\ s.t. & \sum \limits_{p \in P’} a_p\lambda_p &\ge b & [\pi] \\ & \sum \limits_{p \in P’} \lambda_p&= 1& [\pi_0] \\ & \lambda &\ge 0 \\ \end{align}

with \( P‘ \subseteq P , a_p = A p, c_p = c^T p \). The corresponding pricing problem look like this:

\begin{align} \min \quad & (c^T -\pi^TA) x - \pi_0&\\ s.t. \quad & Dx &\ge d \\ & x &\ge 0 \\ \end{align}

In our setting we find additional constraints \( Fx\ge g\) for the original problem which now has the form:

\begin{align} \min \quad& c^T x &\\ s.t. \quad& Ax &\ge b \\ & Dx &\ge d \\ & Fx & \ge g \\ & x &\ge 0 \\ \end{align}

If we transfer them to our restricted master problem, we obtain

\begin{align} \min & \sum \limits_{p \in P’} c_p \lambda_p &\\ s.t. & \sum \limits_{p \in P’} a_p\lambda_p &\ge b & [\pi] \\ & \sum \limits_{p \in P’} \lambda_p&= 1& [\pi_0] \\ & \sum \limits_{p \in P’} a_p\lambda_p &\ge b & [\pi] \\ & \sum \limits_{p \in P’} f_p\lambda_p &\ge g & [\alpha] \\ & \lambda &\ge 0 \\ \end{align}

where \( f_p = F_p \). At last, we need to correct the pricing problem

\begin{align} \min & (c^T -\pi^TA - \alpha^T F) x - \pi_0&\\ s.t. & Dx &\ge d \\ & x &\ge 0 \\ \end{align}

Implementation

The separator ‘master’ does implement exactly the above described procedure. In case we do not have an aggregated pricing problem, the separator calls the intern SCIP separators for the original problem and then transfers the found cuts to the master problems.
This separator can be tuned like any normal SCIP separator, see the SCIP documentation. Please disable this separator if you implemented an own solver for the pricing problems, because it can unintentionally destroy the special structure you want to use.