More compact reformulations

[leotac]

I've tried to use JuMPeR to fiddle with some robust models in a quick way, and I really like it.
It's obvious that the reformulation, in some cases, can be written in a more compact way that what JuMPeR General Oracle does, e.g., when an uncertain term is exactly the same in two constraints (if deviations are symmetric, even with opposite directions), etc.

Not sure if you're working on similar ideas (I guess it's not a pressing matter), but it'd be nice if Jumper could maybe identify some of these (more or less) trivial cases and write a more compact reformulation.

[This kind of preprocessing might be esp. useful for a non-expert (or lazy!) user that doesn't know (or doesn't want to think) too much about the reformulation, and just wants its robust model.]

I actually thought solvers would easily get rid of all the unnecessary junk (extra variables, etc) in presolve; it turns out that it's not always the case.

Example: I have a very simple MIP model where some constraints have a number of uncertain parameters, and none of them is related to a variable. The uncertain term can be easily precomputed, instead of dualizing it etc. This makes a significant difference: a simple instance is solved in 1-2 seconds (both Gurobi and Cplex) if I use Jump (with full reformulation), and only 0.1s if I precompute the deviations. (I actually added a couple of line of code to oracle-gen.jl to carry out this simple precomputation when "applying the reformulation", I can open a PR if interested.)

Now, this might be a silly example [but I've read worse things in some papers :)], and you wouldn't really want to "dualize" in that case, but I hope you see my point.

[IainNZ]

I consider this a low priority because solvers can normally pre-solve out these things, and it makes little difference to problems I've encountered. I'd be curious to see your example, because it apparently goes against that observation. If the term doesn't relate to the variables, you should probably try the cutting plane method, I imagine it'd be quicker than reformulation.

(also duplicate of #4)

[leotac]

Using cutting planes doesn't look much better -- actually in CPLEX is significantly worse, while it's more or less equivalent with Gurobi. Disclaimer: I haven't really looked at --or thought about-- how/when/what cutting planes are generated by JuMPeR in this case.
It might be a pretty extreme or pathological case, but for sure it's not the only situation where JuMPeR ends up with unnecessary dual variables. I'm just not sure when/if it makes a difference, I did think "presolve magic" would be enough, too.

My toy model is essentially this, with no backlogging.

[IainNZ]

I mean, its definitely not the only situation where there are unnecessary dual variables, but it doesn't necessarily follow that that would make things worse.

If your uncertainty is not associated with any variable, there is only one cutting plane required per uncertain constraint, which is why I thought it might help. In that paper, there is only right-hand-side uncertainty IIRC, so technically if you just calculated the cutting plane before solving then you'd have the tightest possible reformulation (i.e. no reformulation at all). Maybe I could do that automatically.

[leotac]

Yup, only RHS. You can just precompute it.