Parameter  PreSparsify
AnsweredHello Gurobi team,
Can I know what process the 'PreSparsify == 1' parameter works through during the Presolve process?
I would really appreciate it if you could let me know the documents to reference.
Thanks

You can find a more elaborate description of the PreSparsify parameter in Section 5.3 of Presolve Reduction in Mixed Integer Programming, T. Achterberg et al. (2019). This paper also described other presolve steps utilized in Gurobi.
Best regards,
Jaromił0 
Hi Jaromił,
I would like to take up this topic here.
I looked into section 5.3 of the specified paper and in my applications I have a lot of constraints that fit into the scheme [s * A_qS = A_rS] for the given rows:
A_qS * x_S + A_qT * x_T + A_qU * x_U = b_q
A_rS * x_S + A_rT * x_T + A_rV * x_V <= b_rAm I right, that row q, that is substracted s times from row r, needs to be an equality constraint?
And row r can be an equality constraint or an inequality constraint, doesn't it?It makes sense to me that the transformation shown in the paper should only be applied if S>U, because only in that case the number of nonzeros is reduced:
A_qS * x_S + A_qT * x_T + A_qU * x_U = b_q
(A_rT  s * A_qT) * x_T  s * A_qU * x_U + A_rV * x_V <= b_r  s* b_qIf I add an auxiliary variable x_a, a corresponding equality constraint and apply the following transformation, I think I can reduce the number of nonzeros in case of S>2 independend of U:
A_qS * x_S  x_a = 0
x_a + A_qT * x_T + A_qU * x_U = b_q
s * x_a + A_rT * x_T + A_rV * x_V <= b_rWouldn't that be benificial in case of S≈U, but both beeing >>2?
Of course there is no "free lunch", because I have another variable and another equality constraint.
But would that be so bad (during simplex?)?
Or would other presolveroutines eliminate x_a and the corresponding equality constraint again (for good reasons?)?I ask for the details, because I need to sparsify my applications not only to reduce the memory demand already during the construction of the problem, but also to increase the performance.
Fortunately, in my particular applications, there are several equations r for which [s * A_qS = A_rS] holds.
Furthermore, there are several groups of equations that are "similar to each other" in the described way.Thanks
Thomas
0 
Hi Thomas,
Am I right, that row q, that is substracted s times from row r, needs to be an equality constraint?
And row r can be an equality constraint or an inequality constraint, doesn't it?Yes, you are right. Note that you can always make an equality out of an inequality via a slack variable.
Wouldn't that be benificial in case of S≈U, but both beeing >>2?
Of course there is no "free lunch", because I have another variable and another equality constraint.
But would that be so bad (during simplex?)?It is really hard to say whether this reduction would always be beneficial or not. Intuitively it should be good, but in practice it often turns out to be the other way round. It is often a very subtle tradeoff between number of variables and constraints and the number of nonzeros. Usually, when aggregation or sparsification reductions are performed, the number of rows, columns, or nonzeros is reduced while the number of the nonreduced quantity are increased, e.g., there are less rows and columns after aggregation, but the number of nonzeros increases. This can have many different impacts on the Simplex algorithm, e.g., different Pivot choices, but can also affect Cuts due to different row density.
Or would other presolveroutines eliminate x_a and the corresponding equality constraint again (for good reasons?)?
It is very likely that aggregation would eliminate x_a. However, the decision about aggregation depends on the AggFill parameter which controls how many nonzeros are allowed to be added during aggregation.
I ask for the details, because I need to sparsify my applications not only to reduce the memory demand already during the construction of the problem, but also to increase the performance.
Fortunately, in my particular applications, there are several equations r for which [s * A_qS = A_rS] holds.
Furthermore, there are several groups of equations that are "similar to each other" in the described way.I think that the best way here would be to perform (at least some of) the reductions manually and analyze the impact. In particular, if you have some special reductions as you described. This is the only way to make sure that you do not miss something or not do too much. Additionally, you could experiment with the parameters Presolve, Aggregate, AggFill, and PreSparsify to hopefully further reduce the size of the presolved model.
Best regards,
Jaromił0 
Hi Jaromił Najman,
thanks for your explanations.
I did intensive testing with the parameters, but in the end it was necessary to perform the reductions manually. And I had to set AggFill to zero (sum higher value might have worked as well) to prevent Gurobi from undoing my reductions.
0 
Thank you for the update Thomas. The observation you made and setting AggFill to 0 definitely make sense.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments