5
$\begingroup$

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.

$\endgroup$

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 1. From the last paragraph, I don't understand why I should add columns of root node. Aren't the columns from the parent a better choice since "the parent and the child are much closer"? $\endgroup$
    – BD26
    Feb 20, 2023 at 1:20
  • $\begingroup$ 2. From the first paragraph, for n items instance, I should add n trivial columns to the LP for each non-root node to ensure feasibility, will this cause inefficiency? $\endgroup$
    – BD26
    Feb 20, 2023 at 1:31
  • $\begingroup$ 1. Yes, it could be. It means that you need to store the relaxation solution in each node. In general, it shouldn't be an issue. $\endgroup$
    – fontanf
    Feb 20, 2023 at 2:15
  • $\begingroup$ @BD26 2. It shouldn't cause inefficiencies. But do not hesitate to test it. You can also check which constraints are not satisfied and only add the trivial columns for these constraints. You can also run a heuristic for the node subproblem and extract the columns from the heuristic. This way, they will be less trivial. But it's not always better, you need to experiment $\endgroup$
    – fontanf
    Feb 20, 2023 at 2:20
  • $\begingroup$ Thanks a lot! I got it. One more question to ask. Assume a node with branching constraint: say item i and j should be in the same bin. When this node branches, what if i and j are found again for branching according to branching scheme? After all, a branching scheme like "branch on two largest item within the bin whose value in RMP is closest to 0.5" is common, and the scheme doesn't specify how to handle this. $\endgroup$
    – BD26
    Feb 20, 2023 at 3:54
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What does "phase 1" actually mean? Does that mean if the inherited columns don't yield a feasible solution, I need stuff like a heuristic to add some columns to make the RMP feasible, then run column generation? $\endgroup$
    – BD26
    Feb 19, 2023 at 15:19
  • $\begingroup$ Like in the two-phase simplex method, phase 1 introduces slack variables and minimizes their sum to find a feasible solution. Phase 2 then omits the slacks and instead optimizes the original objective. If you have a feasible solution (either from existing columns or from heuristics), you can skip phase 1. $\endgroup$
    – RobPratt
    Feb 19, 2023 at 15:23
  • $\begingroup$ Note that if phase 1 terminates with a positive sum of slacks, you would prune the node by infeasibility. $\endgroup$
    – RobPratt
    Feb 19, 2023 at 15:34
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.