lazy cuts callbacks: can solutions violate cuts previously added? about scip.jl

[rschwarz]

I'll have to make a guess here:
There are several sources of solution candidates in SCIP. The most common is that of solutions of the relaxation in branch-and-bound nodes. These should also satisfy the constraints added earlier. Of course, if you have several lazy cut callbacks, all of them will be asked about the same candidate (from the same node).
But other than that, a solution candidate could also come from some heuristic. I think that linear constraints are checked before the lazy constraints, and that the checking stops as soon as some constraint is violated, but here I'm not so sure.

See also the relevant SCIP documentation. The lazy cut callback is called in all three of the mentioned methods, but if the user adds a cut within a call of CONSCHECK, it is not added to the problem. So this makes it possible that a solution is violating a cut that was apparently (but not actually) added earlier.

[rschwarz]

An important detail in this respect is the priority that is given to SCIP to check this constraint. In CSIP, we set a priority of 1, which is the lowest value larger than 0 (to check integrality). Interestingly, the default priority of linear constraints is negative.

@fserra : Is it right to follow that LP-feasibility is not checked prior to calling our CONSCHECK for solutions from heuristics?

[chriscoey]

Thank you! I will look at the documentation. This is causing issues for us
in pajarito, where we have a very expensive subproblem that takes the
integer subvector only and adds conic cuts based on this subvector. We want
to avoid solving this conic subproblem on the same integer subvector more
than once.

On Sep 23, 2016 11:45 AM, "Robert Schwarz" [email protected] wrote:

An important detail in this respect is the priority that is given to SCIP
to check this constraint. In CSIP, we set a priority of 1
https://github.com/SCIP-Interfaces/CSIP/blob/master/src/csip.c#L1242,
which is the lowest value larger than 0 (to check integrality).
Interestingly, the default priority of linear constraints is negative.

@fserra https://github.com/fserra : Is it right to follow that
LP-feasibility is not checked prior to calling our CONSCHECK for
solutions from heuristics?

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#22 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AJq0kw2TsDofHPY7XLgp2T5VCxr5V9_uks5qs_P5gaJpZM4KFGo-
.

[rschwarz]

We were required to set the priority to a positive value in order to fully support the fractional parameter in JuMP. If you know that you want your callback be called only for integral candidates, you could in principal set the priority to a "large" negative value. But this is currently not implemented.

Also, I don't think it will solve the issue with CONSCHECK.

Maybe (but this not a simple fix), we could store the lazy cuts added from CONSCHECK in a special cut pool and add them later, when appropriate?

[fserra]

@leethargo yes, I guess it is correct to assume that the solution has not been checked for LP feasibility in our CONSCHECK... However, only our enfopriority is positive, which means that we get LP solutions that might not be integer to enforce. Our checkpriority is -1, which we setted without further consideration. The checkpriority of linear constraints is -1000000, but still, we should probably be even smaller than nonlinear constraints' checkpriority (-4000010)
So I am missing the big picture right now, but to correctly handle this, we should

• Add the linear constraints generated in CONSCHECK
• Set the checkpriority to be very small

Would that be ok??

I also think that we can just add the constraints generated in CONSCHECK, we don't need to store them.

@chriscoey is it easy to reproduce this behaviour??

[rschwarz]

@fserra, that sounds good to me. I thought that adding constraints from CONSCHECK was not allowed.

[fserra]

well, the stage will not forbid adding a constraint, so I wouldn't know who
will. We just can't inform via result that a constraint was added.

Of course, I am not a 100% sure ;)

On Sat, Sep 24, 2016 at 10:16 AM, Robert Schwarz [email protected]
wrote:

@fserra https://github.com/fserra, that sounds good to me. I thought
that adding constraints from CONSCHECK was not allowed.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#22 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AFNG9muRZzHTaP77X6nxODJYJsUpwwvyks5qtNxfgaJpZM4KFGo-
.

[rschwarz]

We made the change in CSIP.

@chriscoey: Can you check whether the callback is still called twice on the same solution, by using the CSIP master?

CC: @mlubin

[chriscoey]

Thanks for the help here. Miles and I have been talking about what is going on in the lazy cuts in Pajarito and I think we understand what the MIP solvers do and don't do a bit better now.

The change you made should help reduce the number of redundant solutions we get from the solver. We are going to start running computational tests soon and that will give us a better idea. But ultimately there aren't currently any options we can give any MIP solver to make it to do what we want for Pajarito. We only care about getting different integer subvectors of the full mixed-integer vector (we reformulate to only have continuous variables in nonlinear cones). It's pretty specific.

[rschwarz]

Sounds good, the updated code will be merged with #23.

Given that several MIP solvers are "misbehaving" in this respect, it might help to keep a pool of already handled (partial) solution candidates on the Pajarito side, right?

[chriscoey]

@leethargo Yeah over the past few days I have implemented a few new ideas and now Pajarito is cacheing dual cuts and has an option for fast primal cuts, so it is doing as much as it can to avoid wasting time on repeated integer solutions. Ultimately I guess the goal is for MIP solvers to re-implement the ideas behind Pajarito internally, and they will be able to do it better because they have a level of control that we don't.