4
$\begingroup$

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?
$\endgroup$
5
  • 2
    $\begingroup$ It's simply not true in general that the set partitioning problem is equivalent to the set covering problem. $\endgroup$ Oct 30, 2023 at 2:51
  • $\begingroup$ On how many problems and instances did you experience this behaviour? Be careful not to generalize from just a few examples $\endgroup$
    – fontanf
    Oct 30, 2023 at 9:38
  • $\begingroup$ @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? $\endgroup$
    – Rom
    Oct 30, 2023 at 10:52
  • $\begingroup$ 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 $\endgroup$
    – fontanf
    Oct 30, 2023 at 13:35
  • $\begingroup$ @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). $\endgroup$
    – Rom
    Oct 30, 2023 at 13:55

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\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.