Ringpacking

Author

Benjamin Mueller

This application contains a branch-and-price approach for the Ringpacking problem, also known as recursive circle packing problem, which is realized with the framework SCIP. Therefore, the following plugins are implemented:

• a problem reader which parses the problem out of a 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
• a constraint handler which stores information about which patterns have been verified
• a variable data structure which provides fundamental functions for handling patterns

In the following we introduce the problem, explain the use of the reader plugin and pricer plugin.

1. Problem description
2. Parsing the input format and creating the problem
3. Main problem data
4. Pricing new variables
5. Enumerating circular patterns

Installation

See the Install file