Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question.

I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have $m$ variables, and $n$ constraints.

From practical point of view, which of these cases (Dual or Primal), is easier (faster) to be solved with commercial packages (say Gurobi) ?

Solution 1:

Commercial solvers like Gurobi analyze the structure of a problem and decide whether the problem is best suited for solving in primal or dual form.

As a general rule, users should not worry about this. In fact, it can often be counterproductive for a user to attempt to coax the problem into a particular standard form---for example, by splitting free variables, converting equality constraints into equations, etc. After all, the solver may have made a different choice than you did.

Each solver is different, and we do not necessarily know what internal standard form each uses. So let's consider a prototypical example, a solver called GuroPlex built around the following internal standard form: $$ \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x = b \\ & x \geq 0 \end{array} $$ The dual of this model is the inequality constrained form: $$ \begin{array}{ll} \text{maximize} & b^T y \\ \text{subject to} & A^T y \leq c \end{array} $$ As you probably know, in all but the most degenerate cases, solving the primal problem readily leads to a solution to the dual problem, and vice versa. In effect, GuroPlex solves both problems at the same time.

Now, suppose we've constructed an LP to solve, and it happens to look like the inequality form. Knowing GuroPlex's internal standard form, we could convert it ourselves by creating slack variables $z \geq 0$ and splitting the free variables $y$ into the difference of nonnegatives $y_+-y_-$: $$ \begin{array}{ll} \text{maximize} & b^T ( y_+ - y_- ) \\ \text{subject to} & A^T ( y_+ - y_- ) + z = c \\ & y_+,y_-,z\geq 0 \end{array} $$ The result is a form that fits GuroPlex's standard form perfectly---well, save the maximize/minimize difference, but that is readily fixed by negating the objective. It's also larger than it was before, with over twice as many variables (two for each $y_i$ and one for each inequality).

You could do this, but you shouldn't. Just feed GuroPlex the original problem. GuroPlex will detect that your problem matches the dual of its standard form, and will construct and solve the dual of your problem instead. The solution to your problem will be extracted from the internal Lagrange multipliers. (One could argue that because it is solving both the primal and dual problems simultaneously, there's nothing to "extract". So be it! The point is the same.)

What if your problem is not in either of these above forms? For instance, what if it contains a mixture of equations and inequalities? What if it looks like the primal form, except some of the variables are unconstrained? What if it has lower and upper bounds? It can be difficult for you to decide whether GuroPlex would be more efficient solving the primal or dual form of your problem.

So don't decide. Let the software do that.

And certainly do not split free variables, split equations, or add slack variables. That can make it more difficult for the solver to make the correct determination. In fact, some of the better solvers know that people do these kinds of tricks, because they were taught to do so in school---and may reverse those changes. But no presolver is perfect.

Certainly, every once in awhile, there will be a problem that fools the solver, and manually feeding it the dual or making other model changes improves performance. But in general, you will be best served by leaving your problem in the natural form that it presents itself.