Odd behavior in the branch bound and price algorithm with column generation

Question

I have two questions on branch-bound-and-price.

1. Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not explain why it fails. Is it because of the time limit? Or is there any other reason the branch-bound-and-price fail for some problems?

2. An odd behavior of the branch-bound-and-price algorithm:

I am implementing a branch-bound-and-price algorithm with column generation for an electric vehicle routing problem to minimize a certain cost. I am modifying two software - vrpy and cspy for implementation.

My column generation currently works fine using the labeling algorithm. I know this because when I calculate the duality gap, it converges to 0 in the last iteration when there is no route found with a negative reduced cost.

I have a problem during the branch and bound though. I find that sometimes the parent node in the branch-and-bound search tree has a lower bound on the objective function value that is WORSE than the child node. This means that an additional constraint on the master problem (more bounding) has IMPROVED the objective function value for the child node.

I have double and triple-checked the master problem formulation with bounding but I don't see where it went wrong. It seems to happen when I have a larger network. It also seems to happen more when I have some negative edge costs in the network.

Does anyone know why this would be?

Answer 1

1. There can be many reasons why a branch-cut-and-price algorithm fails to solve an instance to optimality in a reasonable time.

• A large primal-dual gap because a heuristic solution is absent or of a pure quality. One needs to improve the quality of the heuristic algorithm to obtain the primal bound.
• A large primal-dual gap because the relaxation is not tight. One needs to add known cutting planes or devise new families of cutting planes. Sometimes, strong cutting planes are non-robust, i.e., they modify the structure of the pricing problem. Sometimes, quality of cut separation algorithm is not sufficient, i.e., it misses good cuts. Sometimes, the cut separation algorithm is too slow. One may also try a different decomposition to improve the strength of the relaxation.
• A large number of branch-and-bound nodes may come not only from a large primal-dual gap, but also because good branching candidates are not found. Strong branching may be a remedy in this case. Sometimes it is possible to enumerate all columns and solve the corresponding MIP directly.
• A difficult pricing problem. One needs here to devise a heuristic for the pricing problem, or work with a relaxation of the pricing problem (for example, well-known ng-path relaxation). Sometimes the pricing problem becomes hard because there are many active non-robust cuts. One may stop generating new cuts and go to branching. Or one may develop a weaker variant of non-robust cuts to speed-up pricing (search for "limited-memory cuts"). Reduced cost fixing may also be an approach to reduce the pricing problem solution time.
• Slow column generation convergence (especially after adding cutting planes). One should use a dual stabilization technique. There are several available, one may search or.stackexchange.com, there were already questions about dual stabilization. There is also the primal stabilization, i.e. generation of many columns in every iteration, not just the one with the smallest reduced cost.
• A large restricted master problem solution time by an LP algorithm. One may change the LP solver (open source -> commercial one, primal simplex -> dual simplex, etc.). Or one can use another decomposition to make the master problem lighter. One may use the column and cut clean-up techniques, i.e., remove from the master columns or cuts which do not participate in the primal or dual solution.

There can also be memory issues, not only the time limit ones. Memory usage can be decreased by using the depth-first search branch-and-bound tree exploration. See also clean-up techniques above.

2. As it was already indicated in other answers, your "odd behaviour" is definitely a bug. You should take the columns generated after branching, and calculate their reduced cost using the optimal dual master solution at the root. The reduced cost of at least one of such columns should be negative. This column is then missed by your pricing algorithm. This can give you a clue where to search a bug in your pricing algorithm.