in MSD, don't terminate before gap is satisfied

[chriscoey]

currently we (should) return suboptimal if MIP solver stops B&C and our gap criterion is not satisfied. but ideally, we should have the MIP solver continue B&C until we tell it to stop (because we check our gap condition) or the time limit is up.

so we could try setting MIP solver's gap to 0, and then perhaps using an info callback to terminate it when our gap condition is satisfied

@mlubin

[chriscoey]

now we are using the info callbacks (#183) and actually returning suboptimal if the MIP solver stops and the gap isn't satisfied.

next step is to try CPLEX incumbent callbacks and actually have the MIP solver properly manage convergence. this is a bit more elegant and should simplify the code. however, it will only work for CPLEX initially, as Gurobi doesn't have incumbent callbacks (though SCIP probably has them), and incumbent callbacks aren't yet recognized in MPB. @joehuchette

i think this will just be a third algorithm in the code, not really exposed to the user until incumbent callbacks appear in MPB.

would be great to be able to do incumbent callbacks with SCIP @leethargo.

[rschwarz]

Could you explain the difference between incumbent callbacks and lazy constraint callbacks? Chances are, SCIP.jl already has them.

[joehuchette]

Incumbent callbacks let you reject an integer feasible incumbent without providing an explicit lazy constraints. So SCIP definitely supports them, it's just a question of whether it's exposed yet in julia.  You could also hack incumbent callbacks in Gurobi using no-good lazy constraints; looking at the CPLEX docs again, this might be what they're doing internally anyway. 

On Mon, Dec 19, 2016 at 2:31 AM -0500, "Robert Schwarz" notifications@github.com wrote:

Could you explain the difference between incumbent callbacks and lazy constraint callbacks? Chances are, SCIP.jl already has them.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[chriscoey]

oh really, is that what CPLEX does? if so, that's kind of shitty. I wonder if SCIP does anything more intelligent.

On Mon, Dec 19, 2016 at 10:32 PM, Joey Huchette notifications@github.com wrote:

Incumbent callbacks let you reject an integer feasible incumbent without providing an explicit lazy constraints. So SCIP definitely supports them, it's just a question of whether it's exposed yet in julia. You could also hack incumbent callbacks in Gurobi using no-good lazy constraints; looking at the CPLEX docs again, this might be what they're doing internally anyway.

On Mon, Dec 19, 2016 at 2:31 AM -0500, "Robert Schwarz" < notifications@github.com> wrote:

Could you explain the difference between incumbent callbacks and lazy constraint callbacks? Chances are, SCIP.jl already has them.

— You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub, or mute the thread.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/mlubin/Pajarito.jl/issues/181#issuecomment-267953618, or mute the thread https://github.com/notifications/unsubscribe-auth/AJq0k2QvMX3FqJxaOet_7Qk7OvGcQxA-ks5rJnl1gaJpZM4LQEBJ .

[rschwarz]

In SCIP, you have to implement this incumbent callback for every constraint handler that you add, via the CONS_CHECK callback. Here, a solution is checked for feasibility, so that it can be rejected.

In SCIP.jl (via CSIP), we implement the CONS_CHECK for the lazy constraint callback, too. We consider a solution candidate rejected, if the user adds a cut. Depending on the solving stage, we try to check whether the user's cut is actually separating. But sometimes, we have to follow the user's judgement.

For the really curious, see here and here.

CC: @fserra

[fserra]

@leethargo so what would this be then? another constraint handler with a higher check priority than the lazy constraint constraint handler??

[mlubin]

The issue we're having with Gurobi is that it's accepting incumbent solutions even when we add constraints (which may have tiny violations). If SCIP will reject the solution in any case then we don't need a specific incumbent callback.

[rschwarz]

@fserra: Priority doesn't matter, I guess. Just an independent, "slim" constraint handler that only implements CONS_CHECK.

@mlubin: Currently, SCIP will check the cut vor violation if possible. But we could change that behavior.

If the MPB interface is extended w.r.t incumbant callbacks, then some solvers could support it directly, but for others, a default implementation based on no-goods would also work, right?

[mlubin]

How would you use no-good cuts if your solution isn't pure binary?

[rschwarz]

I'm not sure, especially if you have continuous, nonlinear constraints.

Somewhat off-topic: In the context of SCIP's initial design, the problem domain (constraint integer programming) was defined in a way, that the variables are partitioned into finite domain and continuous intervals, and once the finite domain variables (which can be enumerated) are fixed, the remaining subproblem is LP.

In the meantime, SCIP was extended to handle nonlinear constraints on continuous variables, to be solved with spatial branching. I guess that enumeration of finite domain was replaced with branching up to the tolerance. But I would bet that if you add a constraint to SCIP that just rejects all candidates, despite the presence of continuous variables, it would branch up to the memory limit and die.

[joehuchette]

Binary expansion in preprocessing?

On Mon, Dec 19, 2016 at 9:52 AM -0500, "Miles Lubin" notifications@github.com wrote:

How would you use no-good cuts if your solution isn't pure binary?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[chriscoey]

The issue is, sometimes due to conic duality failures and nonsmoothness we can't actually derive a numerically stable "dual" or "primal" cut to cut off a point we get from the outer approximation model. I'm not sure how we'd pick a valid cut to add in that situation. So it's easier to just say "No, this point is conic infeasible, so don't let it be an incumbent".

On Tue, Dec 20, 2016 at 12:58 AM, Joey Huchette notifications@github.com wrote:

Binary expansion in preprocessing?

On Mon, Dec 19, 2016 at 9:52 AM -0500, "Miles Lubin" < notifications@github.com> wrote:

How would you use no-good cuts if your solution isn't pure binary?

— You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub, or mute the thread.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/mlubin/Pajarito.jl/issues/181#issuecomment-267984466, or mute the thread https://github.com/notifications/unsubscribe-auth/AJq0k4K56Se0-m0-778tbT7Hf0mpSbN7ks5rJpuTgaJpZM4LQEBJ .

[chriscoey]

for now, until MPB has a standardized incumbent callback documented, I am managing a separate branch https://github.com/mlubin/Pajarito.jl/tree/cplexincumbent which only works with CPLEX.

it implements the "true" / "most elegant" MIP-solver-driven / B&C algorithm using CPLEX's incumbent callback along with the standard lazy and heuristic callbacks.

I need to know whether CPLEX 12.7 is correctly working with CPLEX.jl before proceeding - @joehuchette can you verify this? it seems to build and run fine, but I don't know whether CPLEX is properly accounting for all the callbacks including the incumbent callback.

[fserra]

@chriscoey adding a linearization cut is not possible in your situation (after perturbing the point a little bit if necessary)?

[chriscoey]

@fserra whenever we have to resort to using the incumbent callback to cut off a conic infeasible point, it means we couldn't add linearization cuts for that point because doing so would have required dividing by a number 1e-4 or smaller. such numerically unstable cuts can cause issues for the MIP solver. we don't know how to find more numerically stable cuts, though possibly we could slightly (but not drastically) improve them by projecting the infeasible point in a different way. this is a known problem with primal cutting plane algorithms, and solving it isn't really of academic interest to us. using the incumbent callback at least should guarantee that we have feasibility, within our tolerances.

[ccoffrin]

If I recall correctly, soplex has some features for very high resolution LP. Would that be an option as well?

On Thu, Dec 22, 2016 at 7:15 PM Chris C. notifications@github.com wrote:

@fserra https://github.com/fserra whenever we have to resort to using the incumbent callback to cut off a conic infeasible point, it means we couldn't add linearization cuts for that point because doing so would have required dividing by a number 1e-4 or smaller. such numerically unstable cuts can cause issues for the MIP solver. we don't know how to find more numerically stable cuts, though possibly we could slightly (but not drastically) improve them by projecting the infeasible point in a different way. this is a known problem with primal cutting plane algorithms, and solving it isn't really of academic interest to us. using the incumbent callback at least should guarantee that we have feasibility, within our tolerances.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/mlubin/Pajarito.jl/issues/181#issuecomment-268917991, or mute the thread https://github.com/notifications/unsubscribe-auth/ABDequ6VeXaiaTOiRdbpScwz1QSL0Trxks5rKxB3gaJpZM4LQEBJ .

[chriscoey]

Yes I've seen that SOPLEX has exact (rational) LP features, I think? That could be interesting, but I imagine it also slows down the solver quite a lot to use rationals, and at this point all we are really trying for is to beat a commercial MISOCP solver by a smidgen. It would be a cool idea for someone else to investigate, perhaps in the context of SCIP rather than JuliaOpt. My contributions (except maintenance) to Pajarito are ending.

[chriscoey]

183, #186 fix