# Column generation: set partitioning vs set covering

I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($$Ax\ge 1$$) compared to when it is a set partitioning problem ($$Ax= 1$$). Since it is a minimization problem, both formulations are equivalent and yield the same solution, only the convergence rate differs.

Is there a reason for that (the dual space is reduced ?), and is this a general observation (the fact that using a covering formulation is more efficient), or does it depend on the nature of the subproblem (or anything else)?

#### EDIT

• I agree that covering and partitioning problems are not equivalent in general. However in this context, if minimizing, both formulations do work so I do believe this is quite a general case.
• When I say that convergence is faster, I mean that less iterations are required to reach optimality. The time taken PER iteration is more or less the same.
• I understand using a set covering formulation reduces the dual space. But how exactly does this impact the quality of the columns?
• It's simply not true in general that the set partitioning problem is equivalent to the set covering problem. Commented Oct 30, 2023 at 2:51
• On how many problems and instances did you experience this behaviour? Be careful not to generalize from just a few examples Commented Oct 30, 2023 at 9:38
• @fontanf I have observed this on the different random instances I have generated (a dozen of them). I totally agree this cannot be generalized, in fact this is my question :) is there a good reason to continue observing this on other instances, and other problems?
– Rom
Commented Oct 30, 2023 at 10:52
• I'm not aware of any such comparison. I have a couple of examples at hand I could experiment with. I'll see if I find some motivation and time Commented Oct 30, 2023 at 13:35
• @fontanf interesting. the problem I am dealing with is a simple bin packing problem (minimize the number of bins, all bins are identical, one bin per item).
– Rom
Commented Oct 30, 2023 at 13:55