Binpacking Example (Branch-and-price): Overview

Author: Timo Berthold; Stefan Heinz

This example contains a branch-and-price approach for the binpacking problem which is realized with the framework SCIP. Therefore, the following plugins are implemented:

a problem reader which parses the problem out of file and creates the corresponding problem within SCIP (reader_bpa.c)
a (global) problem data structure which contains all necessary information (probdata_binpacking.c)
a pricer which generates new variables/columns during the search (pricer_binpacking.c)
the Ryan/Foster branching rule (branch_ryanfoster.c)
a constraint handler which handles the branching decisions of the Ryan/Foster branching (cons_samediff.c)
a variable data structure which stores information for each variable and is needed to perform the Ryan/Foster branching (vardata_binpacking.c)

In the following we introduce the problem, explain the use of the reader plugin and pricer plugin. Finally, we introduce the Ryan/Foster branching rule and briefly discuss how that specific branching rule can be realized within the framework SCIP.