8
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ "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": how do you calculate the duality gap? $\endgroup$
    – fontanf
    Mar 15 at 21:13
  • 3
    $\begingroup$ Hi @Dr. Soomin Woo PhD and welcome to or.stackexchange. I'm sorry to say this, but it very much sounds as if you have a bug in your code. If you have a decreasing LP value after branching, it means that you are creating some good columns (maybe not feasible?) that you did not create before branching. That is, suddenly you find columns that are either "too good to be feasible" or which should have been found before branching. $\endgroup$
    – Sune
    Mar 16 at 7:41
  • 1
    $\begingroup$ @Dr.SoominWooPhD I think I would take a very close look at the routes/columns you generate after branching. It is rather hard to diagnose a code-bug at a distance, but from what you are writing, it sounds as if you create some columns, which are actually not feasible, or maybe you calculate a too low cost for these new columns, so that they are "too good to be feasible". So, inspect your newly generated columns (after branching) and calculate by hand the true cost and validate feasibility. $\endgroup$
    – Sune
    Mar 17 at 7:23
  • 1
    $\begingroup$ "assign a cost of 10e10 (big M" > what are the costs of the other routes? If they are too far from 10e10, you'll likely have numerical issues. If these routes are feasible, set them their real cost; otherwise try a to find a better bound $\endgroup$
    – fontanf
    Mar 17 at 9:27
  • 1
    $\begingroup$ Considering how you compute the duality gap, it would be 0 even if the pricing algorithm is wrong $\endgroup$
    – fontanf
    Mar 17 at 9:28

1 Answer 1

8
$\begingroup$
  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.

  1. 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.
$\endgroup$
5
  • $\begingroup$ Wow, thank you very much for your comment. I realize there are many aspects of this algorithm that I have not considered. I will try the debugging method you suggested. $\endgroup$ Mar 31 at 2:26
  • $\begingroup$ Hi @Ruslan, I wonder if you can explain why the debugging method you suggested under 2. works. Do you mean that I can find my bug when the columns generated after branching has a negative column w.r.t the root's dual, because it shouldn't happen? $\endgroup$ Apr 5 at 19:24
  • $\begingroup$ You should find any column with negative reduced cost with respect to the root dual solution. On the other side, you are sure to have such a column in a primal solution which provides a worse lower bound than the root lower bound. $\endgroup$ Apr 7 at 7:02
  • $\begingroup$ Hi @Ruslan, I did indeed find a column with a negative reduced cost with respect to the root dual values at a child node AFTER branching. At that child node, I also had a BETTER lower bound than the root. So I have a bug in my pricing problem. However, that negative column wasn't used in the solution of the child node. Does this make sense..? $\endgroup$ Apr 8 at 19:02
  • $\begingroup$ Does not matter whether it was used in the solution or not. $\endgroup$ Apr 9 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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