mtanneau / mathoptpresolve.jl Goto Github PK

Current progress on upgrading legacy code to the new convention (i.e., rules, reductions and apply!-based syntax).

• Empty row (#13)
• Row singleton
• Forcing/Dominated row
• Fixed variable (#7)
• Empty column (#18)
• Free column singleton
• Dominated column

It would be nice to support QP problems as well.

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)

Legend:

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

cc @joehuchette @BochuanBob

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

If we want to be able to use Multifloats.jl, we need to be careful about arithmetic operations with Inf.
Our current implementation relies on conventions like Inf + 1 == Inf and -1 * Inf == -Inf, from which Multifloats.jl deviates.
After taking a quick glance, it shouldn't be too hard for us to add manual checks to avoid arithmetic operations with Inf when possible.

Pointers: here and here.

We can also add Float64x2 to the tests.

The question of how MIP reductions (resp. LP reductions) should handle continuous (resp integer) variables has come up a few times now.

It might make sense to fully separate LP reductions from MIP reductions (incidentally, we already have src/lp and src/mip), at least for now.
We can still have a "meta-main" presolve! function that would check whether a problem is LP/MIP and call the appropriate LP/MIP-specific "main" presolve. Data structures like ProblemData and style conventions can also be shared.

Pros:

• No need to ensure that each reduction handles LP/MIP models satisfactorily
• MIP presolve can completely ignore dual reductions & dual presolve
• Future MIP-specific data structures (e.g. clique tables) can be added directly

Cons:

• We'll inevitably end up with some duplicate code

@joehuchette what do you think?

Is it time?