Binpacking Example (Branch-and-price): Pricing new variables

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 function SCIPgetDualsolSetppc() which returns the dual solutions for the given set covering constraint.

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().

Note

In case of this binpacking example, the master LP should not get infeasible after branching, because of the way branching is performed. Therefore, the Farkas pricing is not implemented.

In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values of all columns/packings containing both items is fractional. Hence, it exists at least one column/packing which contains both items and also at least one column/packing for each item containing this but not the other item. That means, branching in the "same" direction stays LP feasible since there exists at least one column/packing with both items and branching in the "differ" direction stays LP feasible since there exists at least one column/packing containing one item, but not the other.
In case of variable branching, we only branch on fractional variables. If a variable is fixed to one, there is no issue. If a variable is fixed to zero, then we know that for each item which is part of that column/packing, there exists at least one other column/packing containing this particular item due to the covering constraints.