The task of the pricer is to search for new variables with negative reduced costs. For this, the following integer program is solved:

\[ \begin{array}[t]{rll} \max & \displaystyle \sum_{i=1}^n (\lambda_S)_i y^\star_i\\ & \\ subject \ to & \displaystyle \sum_{i=0}^n (\lambda_S)_i s_i \leq \kappa \\ & \\ & (\lambda_S)_i \in \{0,1\} & \quad \forall i \in \{ 1, \dots , n \} \\ \end{array} \]

where \( (\lambda_S)_i \) for \(i\in\{1,\dots,n\}\) are binary variables and \(y^\star_i\) given by the dual solution of the restricted master problem. See the problem description for more details.

To solve the above integer program, we create a new SCIP instance within SCIP and use the usual functions to create variables and constraints. Besides, we need the current dual solutions to all set covering constraints (each stands for one item) which are the objective coefficients of the binary variables. Therefore, we use the functions SCIPgetDualsolSetppc() and SCIPgetDualfarkasSetppc() which return the dual solution or ray for the given set covering constraint for a feasible or infeasible restricted master LP.

Since we also want to generate new variables during search, we have to care that we do not generate variables over and over again. For example, if we branched or fixed a certain packing to zero, we have to make sure that we do not generate the corresponding variables at that node again. For this, we have to add constraints forbidding to generate variables which are locally fixed to zero. See the function addFixedVarsConss() for more details. While using the Ryan/Foster branching, we also have to ensure that these branching decisions are respected. This is realized within the function addBranchingDecisionConss().