4
$\begingroup$

I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My question is, in general, is it a more usual approach to solve the dual problem with column-generation? If yes, can you please help me with a good reference of column-generation for LP (not integer or nonconvex optimization, please).

Moreover, I implemented a cutting-plane approach to the primal problem. Namely, in order to avoid exponentially many constraints, I found a way of solving the problem with one constraint, then 'finding' the most violated constraint in linear time, adding this constraint, re-optimizing the problem, and iterating the whole procedure until the most violated constraint is still feasible. Of course there is no guarantee of termination quickly, but my initial experiments show this is working well! Hence, I don't know whether or not the dual column-generation approach will be better than this approach. However, my second question is, is there any known primal-dual method, where I can use my primal cutting-plane approach and also use the dual column-generation approach simultaneously to beat both methods?

So the questions can be summarized as:

  1. Is column-generation on the dual LP problem a usual way to solve LP problems with exponentially many constraints?
  2. Is there a good source on column-generation for LP?
  3. If we can find the most-violated primal constraint for any primal solution, does this somehow improve the performance of dual column-generation?
$\endgroup$

1 Answer 1

13
$\begingroup$

TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem.

Equivalence between primal and dual form

Consider the (primal) LP problem \begin{align} (P) \ \ \ \min_{x \in \mathbb{R}^{n}} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & \sum_{j=1}^{n} a_{i, j} x_{j} \geq b_{i}, & i = 1, ..., M, \end{align} with $M$ very large (thereby motivating a cutting-plane approach). The corresponding dual problem is \begin{align} (D) \ \ \ \max_{y \in \mathbb{R}^{M}} \ \ \ & b^{T}y\\ \text{s.t.} \ \ \ & \sum_{i=1}^{M} a_{i, j} y_{i} = c_{j}, & j = 1, ..., n,\\ & y \geq 0. \end{align}

It is straightforward to see that adding the constraint $a_{i, .}^{T} x \geq b_{i}$ in the primal is equivalent to adding the corresponding variable $y_{i}$ (and associated column) in the dual. Thus, any cutting plane oracle for the primal is a pricing oracle for the dual, i.e., whether you look for violated cuts in the primal, or positive reduced cost variables in dual, the procedure is the same.

(to view this, start from the complementarity slackness condition and show that the reduced cost of variable $y_{i}$ is the slack of constraint $a_{i}^{T}x \geq b_{i}$)

Consequently, there is no theoretical argument for using one form over the other: the differences are purely computational.

Computational & implementation differences

Should one use the primal or dual form? The only universally valid answer can be: "it depends".

Primal vs dual simplex

In a cutting plane-based approach, you iteratively add constraint to your LP formulation. This is best done with a dual simplex algorithm (just like in branch-and-cut).

It happens that (i) dual simplex tends to be more efficient than primal simplex, and that (ii) most LP solvers provide a nice API for doing this constraint generation (via so-called "lazy constraints").

In a column-generation approach, you iteratively add variables to your LP formulation; this is best done using the primal simplex. Furthermore, column generation requires dual information (recall that we're solving $D$, so we're talking about dual solutions for $D$): if you're using simplex that's OK, but if you have something more exotic this information may not always be available.

Unfortunately, most LP solvers do not have any column-generation API. This means you must manually solve the current LP, get the current solution, call your pricing oracle, add new variables if any, and re-solve. This means more work (and more opportunities for bugs).

Overall: if you can try both, great. If not, I'd recommend sticking with a primal cutting plane-based approach.

Primal-dual column generation

One way to implicitly use both primal and dual forms is the so-called primal-dual column generation method (this paper also provides some background on column-generation in the LP case). It has been found to outperform simplex-based implementations on some large-scale problems. However, software tools for doing so are very scarce: this is the only one I know of. It's not too hard to implement yourself, but it requires some familiarity with interior-point algorithms.

For completeness, a closely related method is the Analytic Center Cutting-Plane Method (ACCPM), which is one of the most effective approach for, e.g., multi-commodity network flow problems.

One reason why the primal-dual column generation is so effective is because it implicitly provides a stabilization effect, which I discuss next.

Acceleration & stabilization techniques

So-called stabilization techniques help speedup column-generation (or, equivalently, cutting-plane) algorithms. From a primal (cutting-plane) perspective, the idea is that the point to separate should not move "too much" between successive iterations. Most of the time, there is little theoretical justification (like a proof of faster convergence) for them, but they generally work well.

For background:

$\endgroup$
4
  • $\begingroup$ Thank you so much for such a well-organized & helpful answer. Do you think what I have, namely finding the most violated constraint without enumerating them at all, can be a nice feature in the primal-dual algorithm? $\endgroup$ Jan 17, 2021 at 21:27
  • 1
    $\begingroup$ I'm not sure I fully understand. All these techniques rely on an oracle that, given a point to separate, provides a violated cut or proves that none exists. If said oracle runs in polynomial time, then there exist algorithms that can solve the (exponentially large) LP in polynomial time, e.g., the ellipsoid method. In practice, whether you enumerate all constraints or not is more about efficiency, IMO. $\endgroup$
    – mtanneau
    Jan 18, 2021 at 14:47
  • $\begingroup$ thanks for your answer! To be honest, I think your answer above is more than perfect for me. I am just curious about this new idea: My point was that, I can find the "best" cut in linear time, i.e., for any solution, I have an algorithm which finds the single constraint that is violated the most among all the constraints. So not 'a' violated constraint, but 'most' violated constraint. Maybe this knowledge is of help for the dual column-generation approach.. $\endgroup$ Jan 18, 2021 at 19:48
  • 1
    $\begingroup$ It's reasonable to expect that "most violated" will work better (faster convergence) that "any violated constraint", but... it is not needed for convergence: as long as you're generating violated constraints, the algorithm will make progress. Besides, cut violation is not the only criterion; there's a vast literature on this, e.g. this paper $\endgroup$
    – mtanneau
    Jan 18, 2021 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.