4
$\begingroup$

I'm currently in the process of learning about column generation, so I apologize in advance if I show a gross lack of understanding about it.

Anyways, what I've gathered so far is that Column Generation approaches typically run faster than standard MIP formulation algorithms because you are not calculating the reduced cost of all non-basic variables every iteration of the simplex; rather, you are solving a minimization problem on a polytope to find the non-basic variable with the smallest reduced cost.

The part that is confusing me is that it seems like CG is also advertised to have a "simpler" feasible region in the reformulation which would aid in runtimes. However, aren't we simply doing all the hard work of enumerating the new variables in the beginning? For instance, when reformulating the cutting stock problem, you must enumerate all possible cutting patterns which would itself take time. Are we sure that this doesn't take more time than solving over the original formulation which also guarantees only valid patterns would be cut? In other words, are we sure that the time saved from not calculating every reduced cost, every iteration of the simplex, and solving on a "simpler" feasible region for the reformulation actually saves more time than the time spent enumerating the new variables?

I think I may be missing something here, but every example of CG I've seen so far glosses over how they create the new variables and just how much time that would take.

Improve this question
$\endgroup$
5
  • $\begingroup$ "For instance, when reformulating the cutting stock problem, you must enumerate all possible cutting patterns which would itself take time." this sentence is not clear to me and makes me think that there might be some confusion. When using CG, the point is to not generate all possible patterns because it would take too much time $\endgroup$
    – fontanf
    Jan 27, 2022 at 18:23
  • $\begingroup$ From what I've seen, the decision variables for the CG formulation of the cutting stock problem are the number of times each pattern 'p' (belonging to the set of possible patterns 'P') is used. My issue is that to create the set 'P' and, thus, the decision variables, you have to figure out all of the possible patterns there are that you could cut. This in and of itself could take a long time. $\endgroup$
    – lobstersalesman
    Jan 27, 2022 at 18:34
  • 1
    $\begingroup$ Yes, the set of variables of the formulation is the set of possible patterns. But the point of using CG is that it is not needed to generate them all. Only the ones which are computed at each iteration are generated and added to the model $\endgroup$
    – fontanf
    Jan 27, 2022 at 18:36
  • $\begingroup$ I think you are referring to adding the variables with the lowest reduced cost at each iteration. What I am getting at is the following: for you to even be able to create the sub-problem where you pick which variable to add, you have to know which variables are even possible to exist. If there are only 300 possible ways to cut the stock, you need to know that from the onset before you create the sub-problem and choose which one to add to the RMP. Let me know if I am misunderstanding you, but I think we might be thinking of different things. $\endgroup$
    – lobstersalesman
    Jan 27, 2022 at 18:45
  • 1
    $\begingroup$ "for you to even be able to create the sub-problem where you pick which variable to add, you have to know which variables are even possible to exist": no, you don't. You just need to solve an optimization problem (the pricing problem) which will output one variable with negative reduced cost if there is one $\endgroup$
    – fontanf
    Jan 27, 2022 at 18:47

1 Answer 1

Reset to default
4
$\begingroup$

"are we sure that the time saved from not calculating every reduced cost, every iteration of the simplex, and solving on a "simpler" feasible region for the reformulation actually saves more time than the time spent enumerating the new variables?"

The answer is no. You can come up with, admittedly stupid, column generation procedures, where the subproblem is the problem itself. Hence, nothing would be gained. Loosely speaking, the entire procedure is a careful trade off between strong bounds from the master as a result of difficult subprobelms and not so strong bounds as a result of easier subprolems.

Improve this answer
$\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.