Binpacking

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
• a (global) problem data structure which contains all necessary information
• a pricer which generates new variables/columns during the search
• the Ryan/Foster branching rule
• a constraint handler which handles the branching decisions of the Ryan/Foster branching
• a variable data structure which stores information for each variable and is needed to perform the Ryan/Foster branching

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 is realized within the framework SCIP.

1. Problem description
2. Parsing the input format and creating the problem
3. Main problem data
4. Pricing new variables
5. Ryan/Foster branching

Installation

See the Install file