<div dir="ltr"><div><div>Hi Hanan,<br><br></div>We give an example in the paper "How important are branching decisions: Fooling MIP solvers" ( <a href="https://doi.org/10.1016/j.orl.2015.03.003">https://doi.org/10.1016/j.orl.2015.03.003</a> ). The instances are available here: <a href="http://miplib.zib.de/contrib/PierreLeBodic/">http://miplib.zib.de/contrib/PierreLeBodic/</a> .<br></div><div><br></div><div>The paper "An abstract model for branching and its application to mixed integer programming" ( <a href="https://doi.org/10.1007/s10107-016-1101-8">https://doi.org/10.1007/s10107-016-1101-8</a> ) shows that determining the optimal branching strategy  in an abstract model of the MIP B&B is at least #P-hard, thus it may be impossible to obtain in practice  the optimal branching strategy for what you call "interesting" instances.</div><div><br></div><div>Kind regards,</div><div>Pierre<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 24 December 2017 at 10:56, Hanan Rosemarin <span dir="ltr"><<a href="mailto:h.rosemarin@gmail.com" target="_blank">h.rosemarin@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hi</div><div><br></div><div>I am interested in evaluating variable branching heuristics in MIP solvers, using SCIP.</div><div><br></div><div>Are there problems for which the <u>optimal</u> integer branching is known?</div><div>If not, are there problems that are small enough so that it is possible to evaluate all possible variable branching yet still be "interesting" in the sense <span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent">that their result would be meaningful and indicative of the solver's performance?</span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent"><br></span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent">I'd appreciate any suggestion regarding available data and implementation tips</span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent"><br></span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent">Thanks</span></div><span class="HOEnZb"><font color="#888888"><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent"><br></span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent">Hanan</span></div><div><span style="text-align:left;color:rgb(34,34,34);text-transform:none;text-indent:0px;letter-spacing:normal;font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant:normal;font-weight:400;text-decoration:none;word-spacing:0px;display:inline;white-space:normal;direction:ltr;float:none;background-color:transparent"><br></span></div></font></span></div>
<br>______________________________<wbr>_________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/<wbr>mailman/listinfo/scip</a><br>
<br></blockquote></div><br></div>