English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Full strong-branching is a well-known variable selection rule that is knownexperimentally to produce significantly smaller branch-and-bound trees incomparison to all other known variable selection rules. In this paper, weattempt an analysis of the performance of the strong-branching rule both from atheoretical and a computational perspective. On the positive side forstrong-branching we identify vertex cover as a class of instances where thisrule provably works well. In particular, for vertex cover we present an upperbound on the size of the branch-and-bound tree using strong-branching as afunction of the additive integrality gap, show how the Nemhauser-Trotterproperty of persistency which can be used as a pre-solve technique for vertexcover is being recursively and consistently used throughout thestrong-branching based branch-and-bound tree, and finally provide an example ofa vertex cover instance where not using strong-branching leads to a tree thathas at least exponentially more nodes than the branch-and-bound tree based onstrong-branching. On the negative side for strong-branching, we identifyanother class of instances where strong-branching based branch-and-bound treehas exponentially larger tree in comparison to another branch-and-bound treefor solving these instances. On the computational side, we conduct experimentson various types of instances to understand how much larger is the size of thestrong-branching based branch-and-bound tree in comparison to the optimalbranch-and-bound tree. The main take-away from these experiments is that forall these instances, the size of the strong-branching based branch-and-boundtree is within a factor of two of the size of the optimal branch-and-boundtree.

A Theoretical and Computational Analysis of Full Strong-Branching