[SCIP] Cutting of an integer feasible solution

[Felipe Serrano]

Hey Sriram

You can add your own constraint handler that, in the check callback, says
that the solution is infeasible.
In the check callback you don't have to separate the solution, so no need
to worry about that at this point.

You probably want your constraint handler to be the last one to be checked,
and basically, the last one to do anything. So you'll have to set lower
priorities for your conshdlr than all others. To check he different
priorities, open a scip shell and type `display cons`, also see the
fundamental properties of a constraint handler in
https://scipopt.org/doc/html/CONS.php

Regarding the separation of the "infeasible" solutions, SCIP will ask you
to take care of an "infeasible" solution in the enforcement callback.
Now, unless there is a problem with the LP relaxation, you will only be
dealing with enforcing LP solutions (see
https://scipopt.org/doc/html/CONS.php#CONSENFOLP).
Here, you can add bound disjunction constraints (
https://scipopt.org/doc/html/group__CONSHDLRS.php#ga1ef7f5e6f8b325f1b221add96f500ef3
)
Note that your suggestion "but instead I would like the branching to
continue with y <= 3 and y >=5 as the two branches" can be achieved, but
this will cut off any other feasible solution with y = 4.

However, given that SCIP is asking you to deal with "infeasible" solutions
that are also LP solutions, if you use the simplex algorithm, then the
"infeasible" solution is going to be a vertex (you can check whether the
solution is basic with SCIPisLPSolBasic).
As such, it should be possible to separate the solution. I guess there
should be a simple way of deducing a cut, but I don't know at this moment.
An overkill way of building a cut would be to use an intersection cut: a
ball of radius 1 centered at your solution will not contain any other
integer point in its interior.

Hope this helps

Best,
Felipe

On Sun, Aug 23, 2020 at 6:16 PM <ssriram1992 at icloud.com> wrote:

> Hi all,
>
>
>
> I am trying to solve a problem whose relaxation can be solved using
> branch-and-price. The relaxation is a mixed-integer linear program (not
> binary though). Once I get an integer feasible solution – be it through
> heuristics or branching – I have a post-processing routine, which can check
> the feasibility of the solution w.r.t the original problem. There is no
> possibility that the post-processing routine can generate any separating
> hyperplane or so, to permanently cut off this infeasible solution.
>
>
>
> What can I do to ensure that this solution does not show up again, and no
> primal bound information is collected from this “infeasible” solution?
>
>
>
> That said, I don’t want the complete node/subtree to be discarded either.
> For example, let us say that an integer feasible solution  (x,y,z) = (3, 4,
> 5) is obtained, after x and z are fixed, and y turned out to be an integer,
> just by solving the LP relaxation.  Let us say, this solution is deemed
> infeasible through my post-processing routine.  In this I don’t want to
> discard the subtree, but instead I would like the branching to continue
> with y <= 3 and y >=5 as the two branches, for example. Can this be
> achieved?
>
>
>
> There is a long shot of binarizing the integer variables (everything is
> bounded in my case), and then adding no-good cuts. But is there a smarter
> thing that we can do?
>
>
>
> Best
>
> Sriram
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200901/ab4c995e/attachment.html>