Help Postprocessing Globally Valid Cuts

[spkelle2]

Context

• I want to convert globally valid cuts in CBC from the presolved space where Branch and Cut is performed into the space of the formulation I give to CBC as input.
• I think this may require adding a new feature to the CGL codebase, which I think is worthwhile for developing more generalized MIP solvers given algorithms' frequency of solving series of MILP’s (e.g. MINLP, Bijective MILP, MILP decomposition methods).
• @tkralphs pulled me in on contributing to the next CBC release, so since he’s brought me up to speed on the COIN-OR landscape, I would be happy to create a PR of my proposed changes in CGL.

Why can’t I postprocess globally valid cuts in CBC?

• I can’t find a function that does this in the COIN-OR documentation.

How did I try to work around this?

• I did find CglPreProcess::postProcess, which appears to convert solutions from the presolved space into the original problem space. I figured for this to happen, the method must also convert the LP used in branch and bound from the presolved space back into the original space. As far as I can tell from running the debugger against my test instance (p0201.mps), this happens, as the final modelM has the same objective and constraints as the CglPreProcess.originalModel at the bottom of the preprocessing stack. I thought that if I just appended my cuts to the modelIn argument of CglPreProcess::postProcess then those cuts would get pulled through each postprocessing step and bring them back into the original problem space as well. Then I could make that part of CglPreProcess::postProcess into its own public function returning the model with postsolved cuts, but I again only get an LP that looks like CglPreProcess.originalModel.

Why did that happen?

• So it appears that the postprocessing transformations are happening not on modelIn, but on the OsiPreprocessor.presolvedModel for each preprocessor applied to our CglPreProcess object.

How did I try to resolve this?

• I noticed, at least for my test instance, after the presolved model is postsolved, it matches OsiPreprocessor.originalModel. So this led me to think that I should just append the cuts I added to modelM (via modelIn) to the OsiPreprocessor.presolvedModel at the top of the preprocessing stack, and, once OsiPreprocessor.presolvedModel model is postsolved, copy the extra cuts back to OsiPreprocessor.originalModel. Then this process can be repeated for each preprocessor in the stack, leaving us with the extra cuts appended to the original model formulation when postprocessing completes. I could then wrap this process into a public facing function like mentioned above. But this doesn’t quite work as expected either.

Why not?

• Well I should have known better than to try editing private attributes (e.g. OsiPreprocessor.originalModel and OsiPreprocessor.presolvedModel). They’re private for a reason - you’re liable to break things by editing them directly. However, I don’t really see another way forward. Anyways, after updating the models in each preprocessor I ran up against failed assert statements in the presolve actions because the number of rows in OsiPreprocessor.presolvedModel (after postsolving?) no longer matches OsiPreprocessor.nRows. Now I could increment OsiPreprocessor.nRows in each preprocessor for each extra cut I left on the branch and bound model for postprocessing, but I feel like I’m just trekking further into territory I shouldn’t be stomping around in, at least not without first asking for where the landmines are hiding as I’m not familiar with how much I should expect asserts and unit tests to catch things I break. Thus, I have the following questions.

Questions:

• Am I overthinking my approach here? Is there an easier way to bring global cuts from branch and bound back into the original problem space?
• If not, do I have the right idea by trying to feed the cuts I want brought back to the original space through each postprocessor? Is there another approach I should consider?
• If not, when I add cuts to OsiPreprocessor.presolvedModel and OsiPreprocessor.original, how do I need to modify other attributes of OsiPreprocessor to not break the postprocessing actions applied in each?
• I thought I saw somewhere in the docs that the postprocessors are not guaranteed to work for insufficiently solved models. In some cases, I need only to postprocess cuts created from the first several nodes, or even just the root node. Do I need to worry about cuts being improperly transformed from the presolved space if I’ve only processed a few nodes in branch and cut?

[jjhforrest]

Not sure this will work. First there would be an enormous amount of coding. Presolve is the simplest preprocessing and stores actions for the postsolve. Each CoinPresolve...cpp would have to be modified. But I don't see the use of getting the global cuts. Suppose we have two similar variables x and y (not identical). Presolve may deduce that x dominates y and removes y. A cut is derived and is postsolved back to a cut on the original problem. But any change in costs, rhs or elements may invalidate the original supposition and so the cut is no longer valid.

[spkelle2]

To your point, in most cases resolving the same problem nets nothing, but answering that question gives me good insight as to how postsolve is working.

I asked that question because I’m a little confused as to why a cut isn’t useful if the RHS or objective changes. My understanding is that if a cut is valid for a MILP, then changing the objective does not change its validity and in many cases the cut can be parameterized to regain validity when the RHS changes. (Now they may not be that helpful if the change is large, but assume we're only working with small changes between instances.) The way I see it is that either I misunderstand something in my MILP theory, or the global cuts found during branch and cut on the presolved problem are not guaranteed to be valid for the original MILP based on how presolve simplifies the problem. Could you tell me which it is or if there's something else going on here that I'm not considering?

[jjhforrest]

A generated cut is not just a feasibility cut, but is an optimality cut. So if you have two binary variables x and y identical apart from x having a lower cost, then a valid cut is x >= y. If you change the costs then this cut may not be valid.

[spkelle2]

Am I correct in my understanding that an optimality cut is one that is valid for the optimal solution set and a feasibility cut is one that is valid for the feasible solution set? And thus the set of optimality cuts contains the set of feasibility cuts? I apologize for the simple question, but I can't seem to find a published definition for those terms.

Anyways, I think I can see why if presolve adds cuts that are valid for all optimal solution(s) but not necessarily valid for all feasible solutions (like in your example above), then postprocessing globally valid inequalities for the presolved instance does not prevent those inequalities from no longer being valid for the optimal solution sets of new instances where the RHS or objective changes too much. However, would you be able to infer when the RHS or objective changes too much for a postprocessed cut to remain valid for the new optimal solution set by looking at how presolve fixes the original variables? If not, what would you need to do to know before solving a new instance that a postsolved cut is still valid for the new optimal solution set? Additionally, is it possible to parameterize these cuts to make them valid for the new optimal solution set if the changes to the problem invalidate them?

Also, when I've been referring to globally valid inequalities, I've been meaning those available from CbcModel.globalCuts(). I've inferred from the name and a bit of my own testing that these cuts are valid for all feasible solutions to the presolved problem. Is my understanding correct? Is there a difference between globally valid cuts and cuts that are valid for all feasible solutions?

Thank you for continuing to get back to me quickly and helping me better understand how preprocessing is implemented for CBC/CGL.

[jjhforrest]

I am not sure the terms "feasibility cut" and "optimality cut" are well defined - but your understanding is correct. Not all globalCuts() cuts will be valid feasible cuts - it just refers to those valid in whole tree. So if a valid solution has been found by an heuristic then it may not be a feasibility cut.

Overall, I think the best approach would be to create hints. It would be relatively easy to log the Cgl cut which generated a valid cut and most of the variables in original formulation which were involved. You can also see which individual cuts make the biggest difference to the objective (on the preprocessed problem without cuts). I am not sure exactly how a hint would work, but I can half see for some cuts.

[spkelle2]

This is insightful. Thank you. I regrouped with my team, and I think I can simplify my request for the time being then.

For some applications of ours, it is ok to just have the postprocessed global cuts without concern for their validity relative to problem changes, as we just need a tightening of where to search for the optimal solution(s) of the original formulation. That being the case, would you mind walking me through what is involved in the “enormous amount of coding”, including how “each CoinPresolve…cpp would have to be modified”? This would help my team make an informed decision as to if this is an undertaking we want to attempt.

If it would be easier, I’d be happy to coordinate a time over zoom to meet and just post back in this thread what we discuss. The email in my profile is a good contact for me if that’s your preference.

[jjhforrest]

Preprocessing is more complicated than just presolving - but just take presolve. There are about fifteen different types of action. Take one e.g. CoinPresolveImpliedFree.cpp and look through the postsolve and think what would need to be done and the scope for bugs. For each variable in preprocessed problem it is reasonably easy to point back to the corresponding variable in original problem (not always e.g. if x=y, then it might point to x or y). This might give you hints as to where to search.

I don't know enough about your problem, but I would think a more promising approach would be -
First run without any preprocessing and see if looking at cuts is helpful.
If helpful then see what difference in time for first run if you split run
a) run without preprocessing and save root model and all global cuts
b) run initial model + global cuts with preprocessing and also root model with preprocessing and see which works better.

If this is not very much slower then I would think that would be the way to go.

[spkelle2]

I’m happy to go through each presolve and think about what would need to be done - I think that's a great idea. However, I am not sure of your unit test or assertion coverage, so if anything sticks out to you that I should be aware of while doing so, could you please let me know? I did want to add that I am a student of @tkralphs, so the more time you can spend with me on this, the more responsibility Ted and I can take for managing the codebase (as this exercise has been really helpful for learning how everything in CBC "hangs together").

When you say preprocessing is more complicated than just presolving, can you tell me what more would need done to global cuts in the presolved space than running them through post solve in order to use them as optimality cuts for the original formulation?

[jjhforrest]

In pre and postsolve the code needs to carry around information as how to create an optimal basis. One problem that I can see is that if presolve manages to remove an element by deduction and then finds that two variables are duplicate, the postsolve is quite happy to make one of them basic as it knows that may give an alternative optimal solution. Wit cuts having to be manipulated, I am not so sure.
One thing preprocessing does is use probing to fix variables, but it also strengthens constraints. It adds a cut, but then preprocessing just replaces the constraint with the stronger one - so there is no global cut to use. There probably are other cases like that as preprocessing does not care about LP optimality - just wants a method of getting correct integral values on post processing.

Presolve has the idea of prohibited columns, which can't be touched. I am not sure whether this is strictly adhered to - but could be a useful idea. This is used with more exotic branch and bound ideas such as Special Ordered Sets (type 2 or interpolation) and lot sizing variables.

As to unit tests and asserts - that is a hard question. On the whole extra asserts are good as no production code will trigger them. In general, what I do (too extensively) is have a lot of conditional compilation for a long time. So #ifdef SEAN_KELLEY_BRILLIANT_IDEA could come in useful.

[spkelle2]

Sounds good. I'll get to work on sifting through the postprocessing actions then with those tips in mind. Would it be ok if we left this thread open in case I come across more questions on postprocessing in the future?

I've noticed those #ifdefs throughout the code. Thank you for the call out to those. That's a good idea.