• Gurobi Staff

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ł

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_qA_rS * x_S + A_rT * x_T              + A_rV * x_V <= b_r

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?

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_q

If 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_r

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?)?
Or would other presolve-routines 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

• Gurobi Staff

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 trade-off 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 non-reduced 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 presolve-routines 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ł