[SCIP] Optimal MIP branching

[Pierre Le Bodic]

Hi Hanan,

We give an example in the paper "How important are branching decisions:
Fooling MIP solvers" ( https://doi.org/10.1016/j.orl.2015.03.003 ). The
instances are available here: http://miplib.zib.de/contrib/PierreLeBodic/ .

The paper "An abstract model for branching and its application to mixed
integer programming" ( https://doi.org/10.1007/s10107-016-1101-8 ) 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.

Kind regards,
Pierre

On 24 December 2017 at 10:56, Hanan Rosemarin <h.rosemarin at gmail.com> wrote:

> Hi
>
> I am interested in evaluating variable branching heuristics in MIP
> solvers, using SCIP.
>
> Are there problems for which the *optimal* integer branching is known?
> 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 that their result would be meaningful and indicative of the
> solver's performance?
>
> I'd appreciate any suggestion regarding available data and implementation
> tips
>
> Thanks
>
> Hanan
>
>
> _______________________________________________
> 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/20180102/576cf76e/attachment.html>