I spent a large amount of time wasting my eyes while staring at solver progress logs. Sometimes they provide some surprises:
Starting Cplex...
Tried aggregator 3 times.
MIP Presolve eliminated 3345 rows and 3344 columns.
MIP Presolve modified 173 coefficients.
Aggregator did 15474 substitutions.
Reduced MIP has 159835 rows, 159743 columns, and 479200 nonzeros.
Reduced MIP has 58059 binaries, 8 generals, 0 SOSs, and 0 indicators.
Probing time = 1.17 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 601 rows and 428 columns.
MIP Presolve modified 261 coefficients.
Reduced MIP has 159234 rows, 159315 columns, and 477828 nonzeros.
Reduced MIP has 101497 binaries, 15 generals, 0 SOSs, and 0 indicators.
Looks like the preprocessor is making this problem much more difficult!
For another example of a Cplex log puzzle see: http://yetanothermathprogrammingconsultant.blogspot.com/2009/01/cplex-log-number-of-integer-variables.html.
In general as LP/MIP solvers become more sophisticated often their logs become more unfathomable. E.g. back in the old days when primal Simplex LP solvers, the sum of infeasibilities and the objective were good indicators of progress. Nowadays with dual simplex being the default algorithm, numbers just go up and down. With the MIP log, the columns I pay attention to most are lower- and upper-bound and the gap.
More info:
The generated model has 178,654 rows, 178,561 columns (59,520 discrete) and 637,386 nz.
The model has many binary variables that are automatically integer. Basically:
investmentdone(i,j,k,t) = investmentdone(i,j,k,t−1) + newinvestment(i,j,k,t)
sum(t, newinvestment(i,j,k,t)) ≤ 1 (optional)
newinvestment(i,j,k,t) ∈ {0,1}
investmentdone(i,j,k,t) ∈ [0,1]
I have the feeling that the Cplex presolver makes both integer.
When using aggind=0 I see almost the same:
Starting Cplex...
Tried aggregator 0 times.
MIP Presolve eliminated 2069 rows and 2069 columns.
Reduced MIP has 176585 rows, 176492 columns, and 513380 nonzeros.
Reduced MIP has 58824 binaries, 8 generals, 0 SOSs, and 0 indicators.
Probing time = 1.44 sec.
Tried aggregator 0 times.
MIP Presolve eliminated 17180 rows and 16837 columns.
MIP Presolve modified 348 coefficients.
Reduced MIP has 159405 rows, 159655 columns, and 478396 nonzeros.
Reduced MIP has 101835 binaries, 16 generals, 0 SOSs, and 0 indicators.
(The number of generals is still increasing). It is somewhat difficult to say (the performance of Cplex – and probably other MIP solvers – is a little bit erratic on this model) but it seems that doubling the number of integer variable does not have a major effect.
Does it solve faster with the aggregator turned off than with it on?
ReplyDeleteI sometimes find that with certain formulations, more binaries doesn't necessarily mean more difficult. A notable example is when using convex hull formulations for disjunctive programming.
ReplyDeleteThis does look interesting indeed. But the size of the problem in terms of rows, columns and nonzeros is reduced after the second aggregator run. Could it be that cplex was able to restrict 50k integer variables to binaries due to their domain?
ReplyDeleteI would be interested in more details about the model you are running. Can you provide for example a summary of variables and their types before and after presolve?
As far as i can see from the additional info your feeling is spot on and the presolver redeclares the variables investmentdone(i,j,k,t) from continous on [0,1] to binary as they cannot take any values other than 0 and 1.
ReplyDeleteThis does give the Solver more information about the model and variables which does make sense - once we know that those variables are in fact binary we dont need to worry about rounding errors for example, branching strategies might be adjusted as well (speculation).
You could try to disable presolving (or just MIP presolve, if that is an option?) alltogether and compare performance if you have time to spare.