[QST] Applying a transaction

[rg20]

In ProblemUpdate::applyTransaction, if one of the reduction is rejected, the function returns rejected flag. However, some of the reductions would have already been applied.

My question is that, if the reductions in a transaction depend on each other, should n't all the previous reductions in the transactions be rejected as well?

[alexhoen]

Yes — you’re right, if a conflict appears, all reductions within the transactions need to be discarded.

To give a bit more context: presolvers in PaPILO return transactions that are applied sequentially. Each transaction contains locks and reductions. Locks describe the preconditions that must hold for the reductions to be applicable. If a lock is rejected, all of the reductions in that transaction are discarded; in code, this is treated as a conflict. In Figure 3 in https://arxiv.org/abs/2206.10709, there is an example for such a transaction.

However, even when the locks are satisfied, PaPILO may still decide not to apply a particular reduction (for example, if substituting a variable would greatly increase the number of non-zeros). In such cases, the reduction itself is rejected individually, even though the locks would allow it.

If you still have questions about how this behaves in specific cases, feel free to ask, and I can clarify further.

[rg20]

@alexhoen thanks for the explanation.

My question was with regards to the second part. Where because of increased fill-in a reduction itself is rejected though there are no conflicts. If a particular reduction is rejected, all the following ones are also rejected because the function simply returns rejected. Can't we just "continue" applying other reductions?

[alexhoen]

Can’t we just continue applying other reductions?

I am quite convinced that this is indeed what happens. The substitution presolver creates exactly one transaction, and the function applyTransaction can simply reject a transaction if it is no longer valid.

To confirm, I debugged the MIPLIB instance ex9 with verbose logging enabled. The relevant output was:

row 2931 col -5 val 0
row -9 col 5501 val 0
row -8 col 5501 val 2931
tsx
canceled
row 18786 col -5 val 0
row -9 col 665 val 0
row -8 col 665 val 18786
tsx
modified rows: 1315,2554,2555,5352,9012,12115,18786,18945,19845,20341,24339,24441,
modified columns: 665,4761,

Here, the transaction attempting to substitute column 5501 with row 2931 was canceled. (Possibly, the “canceled” log message would be clearer if printed a line earlier.) Immediately afterwards, however, another transaction was evaluated: this one successfully substituted column 665 with row 18786. The success is confirmed by the lists of modified rows and columns.

Note also that the cancellation behavior can be influenced by parameter settings.

I hope this matches the behavior you intended to ask about. If I misunderstood your question, please let me know — I’ll be glad to clarify further.