Tuesday, December 22, 2009

Presolve

Not every day I see something like:

--- Generating MIP model xxxxx
--- Untitled_18.gms(477) 2726 Mb
--- 11,865,559 rows 11,868,588 columns 25,453,085 non-zeroes
--- Untitled_18.gms(477) 2726 Mb

Starting Cplex...
Presolve has eliminated 10143846 rows and 10138198 columns...
Presolve has eliminated 11845896 rows and 11840248 columns...
Aggregator has done 1 substitutions...
Presolve has eliminated 11845896 rows and 11840314 columns...
Aggregator has done 18762 substitutions...
Tried aggregator 1 time.
LP Presolve eliminated 11846440 rows and 11846708 columns.
Aggregator did 18762 substitutions.
Reduced LP has 357 rows, 3118 columns, and 3726 nonzeros.

I.e. GAMS generates a huge model (it is actually an LP – all integers are relaxed) that is reduced to almost nothing by the presolver in Cplex. Turns out there are many accounting rows in the model. Nowadays these are better formulated outside the model with assignment statements instead of using model equations.

GAMS actually generates this model quite quickly and efficiently. Opposed to what many people think, the larger the LP model, the better the relative performance of a modeling system. They often can create the model in (hopefully) linear time (linear in the number of nonzero elements), while even the best LP solvers don’t have this linear time behavior.