Data Structures and Storage

Both the memory required to store the search tree and the time required to process a node are largely dependent on the number of objects (cuts and variables) that are active in each subproblem. Keeping this active set as small as possible is one of the keys to efficiently implementing BCP. For this reason, we chose data structures that enhance our ability to efficiently move objects in and out of the active set. Allowing sets of cuts and variables to move in and out of the linear programs simultaneously is one of the most significant challenges of BCP. We do this by maintaining an abstract representation of each global object that contains information about how to add it to a particular LP relaxation.

In the literature on linear and integer programming, the terms cut and row are typically used interchangeably. Similarly, variable and column are often used with similar meanings. In many situations, this is appropriate and does not cause confusion. However, in object-oriented BCP frameworks, such as SYMPHONY or ABACUS [21], a cut and a row are fundamentally different objects. A cut (also referred to as a constraint) is a user-defined representation of an abstract object which can only be realized as a row in an LP matrix with respect to a particular set of active variables. Similarly, a variable is a representation which can only be realized as a column of an LP matrix with respect to a particular set of cuts. This distinction between the representation and the realization of objects is a crucial design element and is what allows us to effectively address some of the challenges inherent in BCP. In the remainder of this section, we further discuss this distinction and its implications.