Column generation: set partitioning vs set covering

Question

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?

Answer 1

First of all, you need to note @BrianBorchers' comment: the set partitioning problem and the set covering problem are not equivalent in general when you are minimizing.

If I assume that you can verify that your models are equivalent in your case, then one reason for faster convergence for the set covering model may be due to the fact that you have a much smaller dual space. By going from equality constraints to inequality constraints, you add sign restrictions to your dual variables.

However, in practice, you need to specify what you mean by "faster convergence". Is it faster in terms of seconds, or faster in terms of iterations. If it is faster in terms of time, then the effect may come from solving the LP relaxations of a covering problem faster than solving the LP relaxation of the set partitioning problem. If you converge faster in terms of iterations, you should look into what columns you are generating in the pricing problems.

Answer 2

Relaxing the equality constraint to an inequality constraint (when the problem allows!) should generally speed up convergence, and I have seen this many times in practice.

You can understand this as follows: column generation in the primal is equivalent to adding cuts in the dual. Bad duals (very suboptimal for the full problem) lead to dual cuts (primal columns) that cut off points in the dual space that we do not really care about in the first place.

For your specific problem, you have information that the solver does not have: you actually do not require an equality constraint! This translates to: the dual multipliers are non-negative/non-positive instead of unbounded. Adding this information (relaxing the constraint in the primal) then leads to an easier problem in the dual, and faster convergence.