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)?
- 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?