Back to SYMPHONY Home Page
One of the most important considerations in designing a branch and cut implementation is what data structures to use for storing and accessing cuts, variables, and search tree nodes. As with many decisions, there are two opposing goals to keep in mind--efficiency and memory conservation. Memory is an important issue not only because the search tree can get very large, but also because communications bandwidth is limited. We need to store the tree in as compact a form as possible and yet be able to access the data efficiently. Accessing the data involves building the data structures required by the LP solver to process the node.
SYMPHONY's data structures are designed specifically to deal efficiently with large numbers of cuts and variables. Cuts and variables are treated symmetrically whenever possible. For instance, candidates for strong branching can be either cuts, variables, or both--the implementation is exactly the same. Similarly, both cuts and variables can be generated dynamically as the algorithm proceeds. However, there are also some differences in how cuts and variables are stored and accessed, as discussed below.