Presolver: removing zero rows leads to SLOWER solution time

[Jurre Hanema]

I am solving a series of linear programs using Gurobi 6.5.2 called from Matlab. Each LP is slightly different but has in the order of 1000 variables, 2000 inequality constraints, and 300 equality constraints. I am measuring the runtime (as reported by Gurobi) for solving each of these LP's and computing the average.

It turned out that, due to some manipulations I do after generating the constraint matrix A, there are many rows in A which only contain zeros. Obviously, these can be removed, so that is what I did:

% Construct A, rhs, sense

        Acon_sp = [sparse(Acon_eq(:, mask)); sparse(Acon_ineq(:, mask))];
        bcon_sp = [bcon_eq; bcon_ineq];
        sense_sp = [repmat('=', ncon_eq, 1); repmat('<', ncon_ineq, 1)];

% Eliminate zero rows
% Adding this step unexpectedly increases the solution time of the LP's

        sense_sp = sense_sp(any(Acon_sp, 2));
        bcon_sp = bcon_sp(any(Acon_sp, 2));
        Acon_sp = sparse(Acon_sp(any(Acon_sp, 2), :));

% Solve LP

        optim_mdl = struct;
        optim_mdl.Q = spalloc(sum(mask), sum(mask), 0);
        optim_mdl.obj = obj(mask);
        optim_mdl.A = Acon_sp;
        optim_mdl.rhs = bcon_sp;
        optim_mdl.sense = sense_sp;
        optim_mdl.ub = ub(mask);
        optim_mdl.lb = lb(mask);

        result = gurobi(optim_mdl, struct('OutputFlag', outputflag, 'Presolve', 1, 'Method', 1, 'DualReductions', 0));

Note  I set the 'Method' to dual simplex, 'Presolve' level to conservative, and 'DualReductions' to 0 to match the automatic choices that Gurobi seems to make, and to ensure that each instance of very LP is always solved using the same settings.

I was thinking that Gurobi's presolver would already eliminate zero rows for me, so I expected no measurable difference in runtime after implementing the "eliminate zero rows" step.  However, to my surprise, the runtime reported by Gurobi actually INCREASES if I remove the zero rows myself:

Average runtime (with eliminating zero rows): ~ 5 ms
Average runtime (without eliminating zero rows): ~ 3 ms

Note that this unexpected behaviour is repeatable and independent of the selected presolve level or method. In fact, if I set everything to 'automatic', the same behaviour is observed. Only if I disable the presolver, the problem with eliminated zero rows indeed runs faster, however this can hardly be considered a solution.

I am mainly wondering what exactly the presolver is doing that causes the solution time to be slower whenever I eliminate the zero rows by my own. Does anybody have any suggestions of what could be the cause?

[Daniel Espinoza]

Hi Jurre,

A couple of observations:

1.- when measuring such small run-times, (milliseconds?) then average of several runs is a minimum, but also, other effects such as CPU throttling, may become significative.

2.- Changing the problem (ordering, and data, even slightly) might lead to different solve paths, so averaging running times with different seeds should also be taking into account.

Now, if the above was taken into account, 

3.- Is it that the number of simplex iterations is larger (in average) or the presolved model size actually increase?

If so, could you show me hoy to reproduce it?

Best,

Daniel