Parameter - PreSparsify

Answered

Dongyun Kim

• August 17, 2022 02:30

Hello 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

Related to

• Presolve

0

• 

  Jaromił Najman

  Gurobi Staff

  • August 17, 2022 13:31

  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
• 

  Thomas Leveringhaus

  • May 22, 2024 16:15

  

  

  

  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_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

  0
• 

  Jaromił Najman

  Gurobi Staff

  • May 28, 2024 07:24
  • Edited

  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ł

   

  0
• 

  Thomas Leveringhaus

  • August 05, 2024 13:31

  

  

  

  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
• 

  Jaromił Najman

  Gurobi Staff

  • August 06, 2024 06:20

  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.