Discovering Branching Rules for Mixed Integer Programming by Computational Intelligence

This thesis introduces two novel search methods for automated design and discovery of heuristic branching rules, employed by the branch-and-bound algorithm for Mixed Integer Programming (MIP). For this experiment, SCIP, an open source MIP solver is used. The rules are specifically designed/trained to be effective at solving the 0-1 Multidimensional Knapsack Problem. A supervised approach is developed, utilizing data collected at the root node of the solution tree, where each instance is solved once for each branching candidate available at the root. Rules are then designed via feature selection with weights inferred through evolutionary search. The resulting branching rules are designed for use at the root node only where the most important branching decisions are made. Another, non-supervised method, assigns weights to heuristic components selected beforehand. Weights are assigned using (1+1)CMA-ES which evaluates performance by solving every training instance with SCIP. For both methods, the branching rules are trained on small randomly generated knapsack instances, and after implementation in SCIP, tested on randomly generated knapsack instances of various sizes and structures. Both methods are shown to generate rules that significantly outperform the state-of-the-art default branching rules of the SCIP solver over most of the groups of test instances