[SCIP] Cutting of an integer feasible solution

[ssriram1992 at icloud.com]

Thank you Felipe. 

 

You are right, I can’t branch y<=3 and y>=5. 

 

I’ll try to process the remaining information in your email. 

 

Thanks a lot again.

 

Best regards

Sriram 

 

From: Felipe Serrano <fserranom5 at gmail.com> 
Sent: Tuesday, September 1, 2020 7:02 AM
To: ssriram1992 at icloud.com
Cc: SCIP mailing list <scip at zib.de>
Subject: Re: [SCIP] Cutting of an integer feasible solution

 

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 <mailto: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 <mailto: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/530efc11/attachment.html>