Puzzles of branch and price algorithm

Question

I'm new to the branch and price algorithm. Though I have some knowledge about how branch & bound and column generation work, there're still some details making me confused.

In short, my problem is:

1. After branching, where do the columns of child node come from before new column being added by sub-problem?
2. Are they obtained by inheritance of the columns in restricted master problem of parent node which is solved to optimality?
3. If so, there must be some inherited columns violating the branching rule, what should we do with these columns in conflict? Are they directly removed?
4. What if the model becomes infeasible after the removal of these conflicting columns?

Take bin packing problem as an example:

Suppose we have $4$ items need to be packed. And the formulation based on Dantzig-Wolfe decomposition should be a set covering model: $$\min \sum_j x_j$$ $$s.t.\, \sum_j a_{ij}x_j \geq 1, \,\,\,\,i=1,2,3,4$$ where $a_{ij}$ is a binary indicator specifying whether item $i$ is packed in bin $j$, and $x_j$ is the decision variable to indicate whether bin $j$ appears in the solution.

Let's say we are in a situation where the RMP(restricted master problem) of Node 0 is solved to optimality by column generation. At this time, say the RMP is: $$\begin{pmatrix}1\\0\\1\\1\end{pmatrix}x_1+\begin{pmatrix}1\\1\\0\\0\end{pmatrix}x_2+\begin{pmatrix}0\\0\\0\\1\end{pmatrix}x_3 \geq \begin{pmatrix}1\\1\\1\\1\end{pmatrix}$$ Then Node 0 is branching to two nodes:

• Node 1 with constraint: let's say item $1$ and item $2$ cannot be in the same bin.
• Node 2 with constraint: let's say item $1$ and item $2$ should be in the same bin.

Then, in Node 1, if the answers to my problem 2,3 are yes, the RMP of Node 1 should be $$\begin{pmatrix}1\\0\\1\\1\end{pmatrix}x_1+\begin{pmatrix}0\\0\\0\\1\end{pmatrix}x_3 \geq \begin{pmatrix}1\\1\\1\\1\end{pmatrix}$$ since the coefficients of $x_2$ put item $1$ and item $2$ together, thus should be removed.

However, the RMP of Node 1 is infeasible now, which means it cannot be iterated by column generation.

And I'm at a loss what to do at this stage.

Answer 1

At each node, you need to ensure that the initial LP is feasible. For example, for the Bin Packing problem, you can add a column for each item or group of items that must be in the same bin corresponding to packing these items alone in a bin.

It is possible to speed up the column generation at the non-root nodes by adding previously computed columns which are still feasible for the node subproblem.

In general, the bottleneck of a branch-and-price is the pricing problem, and not the LP solves. But for the Bin Packing problem, it might not be the case, since the subproblem is quite easy. If the bottleneck is the LP solves, it might not be worth adding all the previously computed columns which are feasible, but only a subset of those. For example, only those found at the root node, or only the last ones found at the root node, or only the ones which are active in the root node solution.

Answer 2

The columns of the child can be initialized by the subset of columns of the parent that also satisfy the branching conditions. For each child node, you would perform column generation to solve the node to optimality. If the inherited columns already yield a feasible solution to the restricted master for that node, you can skip phase 1. Otherwise, you need to do both phases. In short, each node has its own column generation problem, and you can initialize with any set of columns that are feasible to that node.

Answer 3

After branching, where do the columns of child node come from before new column being added by sub-problem?

It is very common to use previously generated columns because they could both be of high quality and not in violation of any branching rule at the child node.

Are they obtained by inheritance of the columns in restricted master problem of parent node which is solved to optimality?

This is one possibility, but not the only one. Indeed, columns generated in a completely different part of the branch-and-bound tree could still prove useful in your child node, and you don't want to generate them again. A common approach is to keep a global column pool. All explored nodes add new columns to this column pool. Each node keeps a list of column indices which are not compatible with it because they violate some branching constraint. A new child node would inherit this list from its parent node, and add new indices which are not compatible with the new branching rule which generated the child node.

If so, there must be some inherited columns violating the branching rule, what should we do with these columns in conflict? Are they directly removed?

In the approach I propose above, the columns are not removed but rather "blacklisted" from that particular child node because they violate the branching rule. Depending on many considerations (how fast it is to solve the pricing problem vs. the master problem, how many columns you are generating, etc.) you might decide that your column pool is growing too big. A big column pool means that the LP solved at each node might be slow to solve. In that case, you can establish rules for columns to exit the column pool. For example, for each column, you could store the sequential B&B node id of the last node in which the column was active. If the column has been inactive for too long, then you might want to remove it from the column pool. However, I would only implement such an exit criterion if I had proof or a strong suspicion that the column pool size is becoming a hindrance to the performance of the algorithm. I would start without such a mechanism.

What if the model becomes infeasible after the removal of these conflicting columns?

This could happen. Even at the root node, how do you initialise the restricted set of columns to ensure feasibility? There is no universal answer to this because finding a feasible set of columns could be trivial for some problems and extremely hard for others. A possible approach is to initialise the column pool with a single "dummy" column. Such a column should have a huge penalty in the objective function, but its coefficients in the constraints matrix should be such that this single column makes all constraints satisfied. For example, in your bin packing problem, you could add an initial column with index $j=0$. You would give this column a large cost in the objective function (something like $\min \; 10^9 x_0 + \sum_{j > 0} x_j$). You would also set the coefficients $a_{i0} = 1 \; \forall i$. If $x_0$ was a "real" column, it would correspond to a single knapsack in which you pack all objects. (Unless your problem is trivial, this solution will violate the knapsack capacity constraint.) Adding $x_0$ to the column pool ensures that the problem is always feasible.

However, there are a few things you should keep in mind. First, column $x_0$ shall never be removed from the column pool and shall never be blacklisted by any branching rule. Second, any optimal solution to the continuous relaxation of your problem which selects column $0$ with $x_0 > 0$ is, in reality, an infeasible solution. Therefore, if a child node has $x_0 > 0$ in its optimal solution, then that child node is infeasible. If $x_0 > 0$ at the root node, then the entire problem is infeasible.

Even when you use a dummy column because you cannot ensure that you will have a feasible set of columns, you should strive to add as many good columns as possible to your initial column pool. If you don't, it is likely that the dual of the continuous relaxation of your problem will be degenerate. In such a case, LP solvers will most likely return dual values corresponding to an optimal vertex of the dual polytope. In this case, you have all the duals "accumulate" in one of the dual variables and be 0 in all others. This leads to pricing subproblems which will yield new columns of "low quality", in the sense that they are unlikely to be selected in the optimal integer solution of the master problem. In your bin packing example, if you call $\lambda_i$ your dual variables, you might have $\lambda_1 = M$ (where $M$ is a large number) and $\lambda_i = 0$ for all $i > 1$. Such dual values are quite uninformative when it comes to generating good columns in the subproblem.