<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Mangal;
panose-1:0 0 4 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>Thank you Felipe. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>You are right, I can’t branch y<=3 and y>=5. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I’ll try to process the remaining information in your email. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thanks a lot again.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Best regards<o:p></o:p></p><p class=MsoNormal>Sriram <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b>From:</b> Felipe Serrano <fserranom5@gmail.com> <br><b>Sent:</b> Tuesday, September 1, 2020 7:02 AM<br><b>To:</b> ssriram1992@icloud.com<br><b>Cc:</b> SCIP mailing list <scip@zib.de><br><b>Subject:</b> Re: [SCIP] Cutting of an integer feasible solution<o:p></o:p></p></div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>Hey Sriram<o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>You can add your own constraint handler that, in the check callback, says that the solution is infeasible.<o:p></o:p></p></div><div><p class=MsoNormal>In the check callback you don't have to separate the solution, so no need to worry about that at this point.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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 <a href="https://scipopt.org/doc/html/CONS.php">https://scipopt.org/doc/html/CONS.php</a> <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Regarding the separation of the "infeasible" solutions, SCIP will ask you to take care of an "infeasible" solution in the enforcement callback.<o:p></o:p></p></div><div><p class=MsoNormal>Now, unless there is a problem with the LP relaxation, you will only be dealing with enforcing LP solutions (see <a href="https://scipopt.org/doc/html/CONS.php#CONSENFOLP">https://scipopt.org/doc/html/CONS.php#CONSENFOLP</a>).<o:p></o:p></p></div><div><p class=MsoNormal>Here, you can add bound disjunction constraints (<a href="https://scipopt.org/doc/html/group__CONSHDLRS.php#ga1ef7f5e6f8b325f1b221add96f500ef3" target="_blank">https://scipopt.org/doc/html/group__CONSHDLRS.php#ga1ef7f5e6f8b325f1b221add96f500ef3</a>)<o:p></o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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).<o:p></o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Hope this helps<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Best,<o:p></o:p></p></div><div><p class=MsoNormal>Felipe<o:p></o:p></p></div></div><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal>On Sun, Aug 23, 2020 at 6:16 PM <<a href="mailto:ssriram1992@icloud.com" target="_blank">ssriram1992@icloud.com</a>> wrote:<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Hi all, <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>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. <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>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? <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>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?<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>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?<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Best<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Sriram<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div><p class=MsoNormal>_______________________________________________<br>Scip mailing list<br><a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br><a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><o:p></o:p></p></blockquote></div></div></body></html>