MIP presolve reductions roadmap

[mtanneau]

Coarse roadmap towards implementing the reductions described in this paper (which is, AFAIK, the most comprehensive and recent paper on the subject).

The table below follows the paper's structure, namely:

3. Individual row reduction
4. Individual variable reduction
5. Multiple row reductions
6. Multiple variable reductions
7. Full-problem reduction

The second and third columns indicate whether each reduction is applicable to LP/MIP models (see detailed legend below)

Reduction	LP	MIP	Current progress
3.1 Redundant constraints	✔️	✔️	LP:🚧 📝; MIP: 🙅
3.2 Bound strengthening	✔️	✔️	LP:🚧 📝; MIP: 🙅
3.3 Coefficient strengthening	❌	✔️	🟢 #14
3.4 C-G strengthening	❌	✔️	🙅
3.5 Euclidean and modular inverse	❌	✔️	🙅
3.6 Single-row probing	❌	✔️	🙅
3.7 SOS reductions	❌	✔️	🙅
4.1 Fixed variables	✔️	✔️	🟢 #7
4.2 Rounding integer bounds	❌	✔️	🚧 #8
4.3 Strengthen SC/SI bounds	❌	✔️	🙅
4.4 Dual fixing	✔️	✔️	🙅
4.5 Implied-free variables	✔️	✔️	LP:🚧 📝; MIP: 🙅
5.1 Redundancy detection	✔️	✔️	🙅
5.2. Parallel rows	✔️	✔️	🙅
5.3 Non-zero cancellation	✔️	✔️	🙅
5.4 (multi-row) bound strengthening	✔️	✔️	🙅
5.5 Clique merging	❌	✔️	🙅
6.1 Dual fixing extension	❓	✔️	🙅
6.2 Redundant penalty variables	✔️	✔️	🙅
6.3 Parallel columns	✔️	✔️	🙅
6.4 Dominated columns	✔️	✔️	🙅
7.1 Symmetric variables	❌	✔️	🙅
7.2 Probing	❌	✔️	🙅
7.3 Disconnected components	✔️	✔️	🙅
7.4 Almost disconnected components	✔️	✔️	🙅
7.5 Complementary slackness	❌	✔️	🙅
7.6 Implied integer	❌	✔️	🙅

Legend:

• ✔️/ ❌: applicable / not applicable
• Current progress:
  • 🙅: not implemented
  • 🚧 : basic implementation
  • 📝 : documentation needed
  • 👷 : in progress
  • 🟢: done

cc @joehuchette @BochuanBob

[joehuchette]

cc @Anhtu07

[mtanneau]

After looking at this I'm wondering whether the approach I proposed in #7 may be a bit off-course.

It might make more sense to organize things in a bottom-up approach:

1. Low-level rules that apply a single reduction, e.g., fix a single variable, tighten individual variable bounds, etc.
2. Some middle-level strategies that combine individual rules in a "simple"-ish way, for instance:
   • Eliminate all fixed variables
   • Check all rows for redundancy
   • etc.
3. High-level loop

In the context of #7, this would mean the following modifications:

• Have a FixIndividualVariable with an attribute j, so that it applies only to variable j
• Possibly create an additional EliminateAllFixedVariables (I think the name is self-explanatory). The internal code would become something like

  function apply!(ps::PresolveData, ::EliminateAllFixedVariables, config)
    for j in 1:n
        apply!(ps, FixIndividualVariable(j), config)
    end
    return nothing   
  end

• Documentation:
  • Detailed focs for FixIndividualVariable (see the current docs of FixedVariableRule)
  • Simple description of EliminateAllFixedVariables.

[joehuchette]

In some sense this is kind of already what we have in #7 with the inner loop over remove_fixed_variable! instead of through apply!.

What does this design buy us? Is there utility in applying a FixIndividualVariable reduction to only a subset of the variables at a time? I agree that going through apply! is likely a better design. Just trying to figure out if this buys us anything extra.

[mtanneau]

I'm still brainstorming, since I think this is an important design decision. I like more the idea of a consistent syntax across the code, and of building things on top of individual, self-contained reductions.

What does this design buy us?

Feature-wise, nothing. It's more a matter of consistency across the code.

• As you noted, there is the syntax discrepancy between apply! and remove_fixed_variable!. I don't see a reason not to unify these. The code will be more flexible, since options can be passed through config rather than having to track the signature of various functions.
• In its current form, the process of fixing a variable happens in remove_fixed_variable!, but is documented in FixVariableRule
• Building higher-level rules becomes much easier by just doing recursive calls to apply!

Is there utility in applying a FixIndividualVariable reduction to only a subset of the variables at a time?

If you're inside a loop that fixes all variables, then no :) But this reduction may be called from somewhere else.

[joehuchette]

+1 to unifying them through the apply! interface. Conceivably you might want to call FixIndividualVariable in a separate presolve routine.

[mtanneau]

This will leave one last thing to discuss/validate: the implementation of pre- and post-crush.

Currently, this is done through PresolveTransformations as follows:

• Each time a reduction is applied, e.g., a variable is fixed or a constraint is removed, a corresponding transformation t, where typeof(t)<:PresolveTransformation is appended to a list. (PresolveTransformation is an abstract type). ⚠️ Note the distinction between a rule (e.g., "remove a variable if its lower and upper bounds are equal") and a transformation ("variable x1 was fixed to value 1"). ⚠️ Different rules may result in the same transformation, and a given rule may trigger several transformations (a forcing constraint allows to fix variables and remove the corresponding row).
• A transformation t may hold additional information for post-solve. This is most important for continuous models, since we must perform primal and dual presolve.

• Pre- and post-crush go through that list in either order and apply each transformation or its reverse. For illustrative purposes:

  function precrush!(x, Ts::Vector{PresolveTransformation})
    for t in Ts
        precrush!(x, t)
    end
    return x
  end
  
  function postcrush!(x, Ts::Vector{PresolveTransformation})
    for t in reverse(Ts)
        postcrush!(x, t)
    end
    return x
  end

  (obviously it's slightly more complicated, but it shows the spirit)

Some low-level rules will inevitably be intrinsically tied to certain transformations (a.k.a reductions), but I think we should keep the distinction between the two. Naming-wise, we currently have the rule FixIndividualVariable and the transformation FixedVariable, which can be confusing. I'm trying to think of a less ambiguous naming convention (preferably without appending Rule or Reduction everywhere), suggestions are welcome.

[joehuchette]

FWIW I don't find the distinction between FixIndividualVariable (or FixVariable) and FixedVariable. After thinking for a few minutes, I'm not sure I can come up with a better naming scheme.

[mtanneau]

I don't find the distinction between FixIndividualVariable (or FixVariable) and FixedVariable

The former is a rule: "If variable j has its lower and upper bound equal, eliminate it". The latter is a reduction: "Variable j has been fixed to its lower bound".

I make the distinction for 2 reasons:

• You may apply a rule but get no reduction. Example: applying the above rule to a variable 0 <= x <= 1 will not reduce anything. CG-based coefficient strengthening technically does not eliminate any variable/constraint either.
• Different rules may yield identical reductions. I'm think of scaling: there are several ways of scaling a problem, all resulting in row- and column-wise scaling vectors. Here we have different scaling rules but only need one type of reduction (which would store the scaling factors).
• Extra information may be needed for post-solve, which is currently stored in the Reduction. For instance, if we fix a variable x, we need to know the value to which it was fixed in order to preform post-solve. We also need its column coefficients to compute its reduce cost in post-solve. (BTW, this is why Reductions are templated by the numeric type T. Rules are not.)

Agreed, in the case of FixVariable and FixedVariable, these are fairly low-level components, and they are very closely related. The least-worst naming convention I can come up with is:

• Rules should have a declarative name, e.g., "FixVariable", "StrengthenBounds" or "RemoveRedundantRow".
• Reductions should have a passive name, e.g., "FixedVariable", "RedundantRow", etc...

[joehuchette]

Sorry, omitted some crucial words in my response: I don't find it all that confusing that the names are close. I actually guessed your naming convention from the single example, so I think it's not all that bad :)