2
$\begingroup$

I have read several times now that with a column generation approach in the subproblem you do not necessarily have to look for the column with the lowest negative reduced cost, but only one with negative reduced costs. And that it is often worthwhile to add several columns with negative reduced costs to the master problem. I am now wondering if there is a guideline on how many to add and how to find several of these reduced columns at once

$\endgroup$

1 Answer 1

2
$\begingroup$

Usually, you should add as many columns as you can generate. It is better if columns are diversified, i.e., "cover" different constraints in the master. The best is to add sets of columns forming a complete solution of your problem, but this may be tricky to do and/or more time-consuming. Also, when you add many columns, you should definitely clean up master from non-promising columns, for example those with a high reduced cost.

The question how to generate many columns is problem-dependent, and this may be a research question for new problems. For example, if your pricing problem is solved by dynamic programming (DP), one way is to apply bidirectional search, thus you will have a lot of candidates when you perform the concatenation phase of the DP algorithm. In this view, solving the pricing problem by a MIP solver is not usually a good choice, partly because MIP solvers will not give you a lot of solutions.

$\endgroup$
3
  • $\begingroup$ Probably, "add as many as you can generation" is an overestimation. Usually, it depends on the time it takes to solve the pricing problem. If it is fast, then several dozens would be enough, if it is very slow then you can generate up to one thousand (if it does not hurt much the solution of the restricted master LP). $\endgroup$ Commented Mar 13 at 13:34
  • $\begingroup$ I would also note that in the '00s and '10s, it was common to have a fixed-size column pool, and you would add columns to it, but when it was full, you would remove columns. Common criteria were poor reduced cost (as Ruslan says) or removing columns that had not been basic for a large number of iterations. I don't see this used much nowadays, possibly because RAM is aplenty and solvers are better at disregarding bad columns without the user intervening. $\endgroup$ Commented Mar 17 at 5:19
  • $\begingroup$ Yes, the column pool may be used if adding all your columns to the master make it much slower. So, you can use the column pool to add more columns on each col.gen. iteration. It is important however, to use it only as a complement for running the pricing problem. If you add only columns from the column pool, this may hurt the convergence. $\endgroup$ Commented Mar 19 at 12:25

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.